Сертификат (сложность)

• Определение сертификата в теории сложности вычислений

  • Сертификат – это строка, подтверждающая ответ на вычисление или принадлежность строки к языку. 
  • Используется для проверки правильности решения в процессе проверки. 

• Сложность сертификата в дереве решений

  • Минимальное количество входных переменных, необходимых для точного определения значения логической функции. 

• Использование в определениях классов сложности

  • Сертификат используется для определения полуразрешимости и принадлежности языка к классам NP, co-NP и NL. 
  • Для определения NP требуется многочлен и полиномиальная машина Тьюринга, принимающая пары (x, c), где c – сертификат. 
  • Для определения co-NP требуется сертификат для слов, не входящих в язык. 
  • Для определения NL требуется сертификат, который может быть проверен детерминированной машиной Тьюринга с ограниченным логарифмическим пространством. 

• Примеры задач с сертификатами

  • Задача определения наличия независимого набора размера k в графе G находится в NP. 
  • Сертификат для задачи определения количества шагов, необходимых для принятия машиной Тьюринга входных данных, представляет собой набор из k вершин. 

• Дополнительные сведения

  • В статье упоминается аналогичное понятие свидетеля в математической логике. 
  • Ссылки на книгу “Вычислительная сложность: современный подход” Санджива Ароры и Боаза Барака.