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

35

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 .xL

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?

MS Dousti
źródło
2
powiązane ostatnie przemówienie Anuj Davara w INI: O klasach złożoności syntaktycznej i semantycznej
Kaveh
@Kaveh: Wielkie dzięki! Rzucę na to okiem.
MS Dousti

Odpowiedzi:

31

xLxL1/2<1/2

xxLxL

xL

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.

Robin Kothari
źródło
3
Cóż, nie zmarnowałbym ostatnich 20 minut, pisząc moją odpowiedź, gdybym tylko ponownie załadował stronę ... :) Zostawię ją na wypadek, gdyby była pomocna.
Ryan Williams,
Tak, nienawidzę tego, kiedy to się dzieje. Chociaż czasami otrzymuję powiadomienie „nowe odpowiedzi zostały opublikowane” w trakcie tworzenia odpowiedzi.
Robin Kothari,
6
@Robin: Nie musiałeś odwoływać się do niesprawdzonego, ale powszechnie uznawanego twierdzenia „P = BPP”, na przykład intencjonalnie semantycznej klasy, która okazuje się składniowa: IP = PSPACE. (A teraz także QIP.)
Joshua
3
@Joshua: Masz rację, IP = PSPACE działa.
Robin Kothari,
1
@Joshua: Dziękujemy za podanie wyniku IP = PSPACE. Nigdy nie patrzyłem na to z tego punktu widzenia!
MS Dousti
28

PPRP PP>1/2x

PNPPPRPRP>1/2RPPromiseRP

P=BPPP=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.

Ryan Williams
źródło
Cześć Ryan. Czy uważasz, że można zdefiniować składnię przyjmując coś w rodzaju tezy Church-Turinga?
Kaveh
1
Zredagowałem teraz swoją odpowiedź, aby odpowiedzieć na pytanie, jak zdefiniować składnię.
Robin Kothari,