Войти
Через теория вычислительной сложности, сертификат (также называемый свидетель ) - это строка, которая удостоверяет ответ на вычисление или удостоверяет принадлежность некоторой строки к языку. Сертификат часто рассматривается как путь решения в процессе проверки, который используется для проверки того, дает ли проблема ответ «Да» или «Нет».
В модели дерева решений вычислений сложность сертификата - это минимальное количество входных переменных 
Понятие сертификата используется для определения полуразрешимости : L полуразрешимо тогда и только тогда, когда существует двумерный предикат R ⊆ Σ ∗ × Σ ∗ такой, что R вычислим, и такой, что для всех x ∈ Σ ∗:
x ∈ L ⇔ существует y таким образом, что R (x, y)
Сертификаты также дают определения для некоторых классов сложности, которые в качестве альтернативы могут быть охарактеризованы в терминах недетерминированных машин Тьюринга. Язык L принадлежит NP тогда и только тогда, когда существует многочлен p и ограниченная с полиномиальным временем машина Тьюринга M такие, что каждое слово x находится в языке L в точности, если существует сертификат c длины не более p (| x |) такой, что M принимает пару (x, c). Класс co-NP имеет аналогичное определение, за исключением того, что есть сертификаты для слов не на языке.
Класс NL имеет определение сертификата: проблема в языке имеет сертификат полиномиальной длины, который может быть проверен с помощью детерминированной машины Тьюринга с ограниченным логарифмическим пространством, которая может прочитать каждый бит сертификата один раз. только.
Проблема определения для данного графа G и числа k, содержит ли граф независимый набор размера k, находится в НП . Для данной пары (G, k) на языке сертификат - это набор из k вершин, которые попарно не смежны (и, следовательно, являются независимым набором размера k).
Более общий пример для проблема определения того, принимает ли данная машина Тьюринга ввод за определенное количество шагов, выглядит следующим образом:
L = {<, x, w>| принимает x в | w | шаги?} Покажем L ∈ NP. проверяющий: получает строку c = , x, w такую, что | c | <= P(|w|) check if c is an accepting computation of M on x with at most |w| steps |c| <= O(|w|) if we have a computation of a TM with k steps the total size of the computation string is k Thus, <, x, w>∈ L ⇔ существует c <= a|w| such that <, x, w, c>∈ V ∈ P 