Сертификат (сложность)
В теории сложности вычислений сертификат свидетелем (также называемый ) — это строка , которая удостоверяет ответ на вычисление или удостоверяет принадлежность некоторой строки к языку. Сертификат часто рассматривается как путь решения в процессе проверки, который используется для проверки того, дает ли проблема ответ «Да» или «Нет».
В модели вычислений в виде дерева решений сложность сертификата — это минимальное количество входные переменные дерева решений , которым необходимо присвоить значение, чтобы однозначно установить значение булевой функции .
Использование в определениях [ править ]
Понятие сертификата используется для определения полуразрешимости : [1] формальный язык L является полуразрешимым, если существует двухместное отношение предикатов R ⊆ Σ∗ × Σ∗ такое, что R вычислимо , и такое, что для всех x ∈ Σ∗:
x ∈ L ⇔ there exists y such that R(x, y)
Сертификаты также дают определения некоторых классов сложности, которые альтернативно могут быть охарактеризованы в терминах недетерминированных машин Тьюринга . Язык L находится в NP тогда и только тогда, когда существуют полином p и полиномиальное время ограниченная за машина Тьюринга M, , такие, что каждое слово x находится в языке L в точности, если существует сертификат c длины не более p(|x| ) такой, что M принимает пару ( x , c ). [2] Класс co-NP имеет аналогичное определение, за исключением того, что имеются сертификаты для слов, отсутствующих в языке.
Класс NL имеет определение сертификата: проблема в языке имеет сертификат полиномиальной длины, который может быть проверен детерминированной машиной Тьюринга, ограниченной логарифмическим пространством, которая может прочитать каждый бит сертификата только один раз. [3] В качестве альтернативы детерминированную машину Тьюринга с логарифмическим пространством в приведенном выше утверждении можно заменить вероятностной машиной Тьюринга с ограниченной ошибкой в постоянном пространстве, которой разрешено использовать только постоянное количество случайных битов. [4]
Примеры [ править ]
Проблема определения для данного графа G и числа k , содержит ли граф независимый набор размера k, находится в NP . Учитывая пару ( G , k ) в языке, сертификат представляет собой набор из k вершин, которые попарно несмежны (и, следовательно, являются независимым набором размера k ). [5]
Более общий пример проблемы определения того, принимает ли данная машина Тьюринга входные данные за определенное количество шагов, выглядит следующим образом:
L = {<<M>, x, w> | does <M> accept x in |w| steps?}
Show L ∈ NP.
verifier:
gets string c = <M>, x, w such that |c| <= P(|w|)
check if c is an accepting computation of M on x with at most |w| steps
|c| <= O(|w|3)
if we have a computation of a TM with k steps the total size of the computation string is k2
Thus, <<M>, x, w> ∈ L ⇔ there exists c <= a|w|3 such that <<M>, x, w, c> ∈ V ∈ P
См. также [ править ]
- Свидетель (математика) — аналогичное понятие в математической логике.
Ссылки [ править ]
- ^ Кук, Стивен. «Вычислимость и невычислимость» (PDF) . Проверено 7 февраля 2013 г.
- ^ Арора, Санджив; Барак, Вооз (2009). «Определение 2.1». Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4 .
- ^ Арора, Санджив; Барак, Вооз (2009). «Определение 4.19». Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4 .
- ^ AC Cem Say, Абузер Якарылмаз, «Проверщики конечных состояний с постоянной случайностью», Логические методы в информатике , Vol. 10(3:6)2014, стр. 1–17.
- ^ Арора, Санджив; Барак, Вооз (2009). «Пример 2.2». Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4 .
Внешние ссылки [ править ]
- Бурман, Гарри; де Вольф, Рональд (2002), Меры сложности и сложность дерева решений: исследование .
- Вычислительная сложность: современный подход Санджив Арора и Боаз Барак