Klasy złożoności semantycznej a składniowej

W swojej książce „Computational Complexity” Papadimitriou pisze:

RP jest w pewnym sensie nową i niezwykłą klasą złożoności. Żadna żadna wieloznacznie niedeterministyczna maszyna Turinga nie może być podstawą do zdefiniowania języka w RP. Aby maszyna N mogła zdefiniować język w RP , musi mieć niezwykłą właściwość, która na wszystkich wejściach albo odrzuca jednogłośnie , albo przyjmuje większością głosów . Większość niedeterministycznych maszyn zachowuje się w inny sposób, przynajmniej dla niektórych danych wejściowych ... Nie ma łatwego sposobu na stwierdzenie, czy maszyna zawsze zatrzymuje się z certyfikowanym wyjściem. Nieformalnie nazywamy takie klasy klasami semantycznymi , w przeciwieństwie do klas składniowych, takich jak P i NP, gdzie możemy natychmiast stwierdzić poprzez powierzchowne sprawdzenie, czy odpowiednio ustandaryzowana maszyna rzeczywiście definiuje język w klasie.

Kilka stron później zauważa, że:

język L należy do klasy PP, jeśli istnieje niedeterministyczna wielomianowo ograniczona maszyna Turinga N, taka że dla wszystkich danych wejściowych x, i więcej niż połowa obliczeń N na wejściu x kończy się akceptacją. Mówimy, że N decyduje L większością głosów .$x \in L$

Pytanie 1: Dlaczego Papadimitriou stwierdza, że PP jest klasą składniową, podczas gdy jej definicja różni się tylko nieznacznie od definicji RP ?

Pytanie 2: Czy bycie „semantycznym” dla klasy złożoności jest równoznaczne z NIE posiadaniem kompletnych problemów, czy też brak kompletnych problemów jest uważany za właściwość, którą, jak sądzimy, mają klasy semantyczne?

Edycja: Zobacz powiązany temat Czy wszystkie klasy złożoności mają charakterystykę języka liścia?

$x \in L$$x \notin L$$\geq 1/2$$< 1/2$

$x$$x \in L$$x \notin L$

$x$$L$

Jeśli chodzi o twoje drugie pytanie, w przypadku klas składniowych zwykle występuje oczywisty pełny problem, który przypomina: „Biorąc pod uwagę maszynę M, zdecyduj, czy akceptuje ona w czasie T na wejściu x”. Jeśli otrzymujesz maszynę niedeterministyczną, problem ten jest NP-zupełny, jeśli jest to PP-komputer, to jest PP-zupełny itp. Oczywisty kompletny problem dla klas semantycznych jest nierozstrzygalny, jak wspomniałem. Więc nie otrzymujemy pełnego problemu za darmo dla klas semantycznych. Ale klasa semantyczna może mieć kompletny problem. Na przykład, jeśli P = BPP (jak się powszechnie uważa), to BPP ma charakterystykę składniową.

EDYCJA : Ponieważ trwa dyskusja na temat definiowania klas semantycznych i składniowych, chciałbym zauważyć, że Papadimitriou podaje definicję w swojej książce, mówiąc o językach liściastych. (Zobacz moje pytanie dotyczące języków liścia dla niektórych odniesień).

Mówi, że klasy składniowe to te, dla których istnieje język, który definiuje klasę za pomocą techniki języka liścia. Klasy semantyczne to te, dla których wszystkie takie charakterystyki wymagają obiecujących problemów. Jest to ścisła definicja, ale działa tylko dla tych języków, które mają charakterystykę języka liścia.

$PP$$RP$ $PP$$> 1/2$$x$

$P$$NP$$PP$$RP$$RP$$> 1/2$$RP$$Promise-RP$

$P=BPP$$P=BPP$

Jeśli tak naprawdę jest tak, że po prostu nie ma łatwo obliczalnej listy maszyn (dowolnego rozsądnego rodzaju), które akceptują dokładnie twoją klasę, to tak, nie sądzę, aby twoja klasa mogła mieć kompletny język. Ale wydaje się to bardzo trudne do sformalizowania, nie mówiąc już o udowodnieniu.