Certyfikat (złożoność)
W teorii złożoności obliczeniowej certyfikat (zwany także świadkiem ) to ciąg, który poświadcza odpowiedź na obliczenie lub poświadcza przynależność do jakiegoś ciągu w języku . Certyfikat jest często traktowany jako ścieżka rozwiązania w ramach procesu weryfikacji, która służy do sprawdzenia, czy dany problem daje odpowiedź „tak” lub „nie”.
W modelu obliczeniowym drzewa decyzyjnego złożoność certyfikatu to minimalna liczba zmiennych wejściowych drzewa decyzyjnego , którym należy przypisać wartość aby ostatecznie ustalić wartość funkcji boolowskiej .
Użyj w definicjach
Pojęcie certyfikatu jest używane do określenia półrozstrzygalności : język formalny L jest półrozstrzygalny, jeśli istnieje dwumiejscowa relacja predykatowa R ⊆ Σ∗ × Σ∗ taka, że R jest obliczalna i taka, że dla wszystkich x ∈ Σ ∗:
x ∈ L ⇔ istnieje y takie, że R(x, y)
Certyfikaty zawierają również definicje niektórych klas złożoności, które alternatywnie można scharakteryzować w kategoriach niedeterministycznych maszyn Turinga . Język L jest w NP wtedy i tylko wtedy, gdy istnieje wielomian p i ograniczona czasowo wielomianowa maszyna Turinga M taka, że każde słowo x jest w języku L dokładnie wtedy, gdy istnieje certyfikat c o długości co najwyżej p (|x| ) takie, że M akceptuje parę ( x , c ). Klasa co-NP ma podobną definicję, z tą różnicą, że istnieją certyfikaty dla słów nie występujących w języku.
Klasa NL ma definicję certyfikatu: problem w języku ma certyfikat o długości wielomianu, który może zostać zweryfikowany przez deterministyczną maszynę Turinga ograniczoną przestrzenią logarytmiczną, która może odczytać każdy bit certyfikatu tylko raz. Alternatywnie, deterministyczną maszynę Turinga w przestrzeni logarytmicznej w powyższym stwierdzeniu można zastąpić probabilistyczną maszyną Turinga o stałej przestrzeni ograniczonego błędu, która może używać tylko stałej liczby losowych bitów.
Przykłady
Problem określenia, dla danego grafu G i liczby k , czy graf zawiera niezależny zbiór o rozmiarze k jest w NP . Biorąc pod uwagę parę ( G , k ) w języku, certyfikat jest zbiorem k wierzchołków, które parami nie sąsiadują ze sobą (a zatem są niezależnym zbiorem o rozmiarze k ).
Bardziej ogólny przykład problemu określenia, czy dana maszyna Turinga akceptuje dane wejściowe w określonej liczbie kroków, jest następujący:
L = {<<M>, x, w> | czy <M> akceptuje x w |w| kroki?} Pokaż L ∈ NP. weryfikator: pobiera ciąg znaków c = <M>, x, w taki, że |c| <= P(|w|) sprawdź, czy c jest akceptującym obliczeniem M na x z co najwyżej |w| kroki |c| <= O(|w| 3 ) jeśli mamy obliczenie TM z k krokami, całkowity rozmiar łańcucha obliczeniowego wynosi k 2 Zatem <<M>, x, w> ∈ L ⇔ istnieje c <= a |w| 3 takie, że <<M>, x, w, c> ∈ V ∈ P
Zobacz też
- Świadek (matematyka) , analogiczne pojęcie w logice matematycznej
Linki zewnętrzne
- Buhrman, Harry; de Wolf, Ronald (2002), Miary złożoności i złożoność drzewa decyzyjnego: ankieta .
- Złożoność obliczeniowa: nowoczesne podejście Sanjeev Arora i Boaz Barak