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

В теория сложности вычислений, а свидетельство (также называемый свидетель) - это строка, которая удостоверяет ответ на вычисление или удостоверяет принадлежность некоторой строки к языку. Сертификат часто рассматривается как путь решения в процессе проверки, который используется для проверки того, дает ли проблема ответ «Да» или «Нет».

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

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

Понятие сертификата используется для определения полуразрешимость:[1] L является полуразрешимым тогда и только тогда, когда существует двумерный предикат R ⊆ Σ ∗ × Σ ∗ такой, что R вычислим, и такой, что для всех x ∈ Σ ∗:

   x ∈ L ⇔ существует y такое, что R (x, y)

Сертификаты также дают определения для некоторых классов сложности, которые в качестве альтернативы можно охарактеризовать с точки зрения недетерминированные машины Тьюринга. Язык L в НП тогда и только тогда, когда существует многочлен п и полиномиальное время ограниченный Машина Тьюринга M так что каждое слово Икс находится на языке L именно если существует сертификат c длины не более р (| х |) такой, что M принимает пару (Икс, c).[2] Класс со-НП имеет аналогичное определение, за исключением того, что есть сертификаты для слов нет на языке.

Класс NL имеет определение сертификата: проблема в языке имеет сертификат полиномиальной длины, который может быть проверен с помощью детерминированной машины Тьюринга с ограниченным логарифмическим пространством, которая может прочитать каждый бит сертификата только один раз.[3]

Примеры

Проблема определения для данного графа грамм и номер k, если граф содержит независимый набор размера k в НП. Учитывая пару (грамм, k) на языке сертификат представляет собой набор k вершины, которые попарно несмежны (и, следовательно, являются независимым множеством размера k).[4]

Более общий пример проблемы определения того, принимает ли данная машина Тьюринга ввод за определенное количество шагов, выглядит следующим образом:

 L = {<, x, w> | принимает ли  x в | w | шаги?} Показать L ∈ NP. верификатор:   получает строку c = , x, w такую, что | c | <= P (| w |) проверяет, является ли c допустимым вычислением M на x с не более чем | w | шаги | c | <= O (| w |3), если у нас есть вычисление TM с k шагами, общий размер строки вычислений равен k2   Таким образом, <, x, w> ∈ L ⇔ существует c <= a | w |3 такие, что <, x, w, c> ∈ V ∈ P

Смотрите также

Рекомендации

  1. ^ Повар, Стивен. «Вычислимость и невычислимость» (PDF). Получено 7 февраля 2013.
  2. ^ Арора, Санджив; Варак, Вооз (2009). «Определение 2.1». Теория сложности: современный подход. Издательство Кембриджского университета. ISBN  978-0-521-42426-4.
  3. ^ Арора, Санджив; Варак, Вооз (2009). «Определение 4.19». Теория сложности: современный подход. Издательство Кембриджского университета. ISBN  978-0-521-42426-4.
  4. ^ Арора, Санджив; Варак, Вооз (2009). «Пример 2.2». Теория сложности: современный подход. Издательство Кембриджского университета. ISBN  978-0-521-42426-4.

внешняя ссылка