Сертификат (сложность)
-
Определение сертификата в теории сложности вычислений
- Сертификат — это строка, подтверждающая ответ на вычисление или принадлежность строки к языку.
- Используется для проверки правильности решения в процессе проверки.
-
Сложность сертификата в дереве решений
- Минимальное количество входных переменных, необходимых для точного определения значения логической функции.
-
Использование в определениях классов сложности
- Сертификат используется для определения полуразрешимости и принадлежности языка к классам NP, co-NP и NL.
- Для определения NP требуется многочлен и полиномиальная машина Тьюринга, принимающая пары (x, c), где c — сертификат.
- Для определения co-NP требуется сертификат для слов, не входящих в язык.
- Для определения NL требуется сертификат, который может быть проверен детерминированной машиной Тьюринга с ограниченным логарифмическим пространством.
-
Примеры задач с сертификатами
- Задача определения наличия независимого набора размера k в графе G находится в NP.
- Сертификат для задачи определения количества шагов, необходимых для принятия машиной Тьюринга входных данных, представляет собой набор из k вершин.
-
Дополнительные сведения
- В статье упоминается аналогичное понятие свидетеля в математической логике.
- Ссылки на книгу «Вычислительная сложность: современный подход» Санджива Ароры и Боаза Барака.