Korzyści dla klas składniowych i semantycznych

9

To jest post oddzielony od Konsekwencji UP równa się NP , a także pytanie uzupełniające do klas złożoności semantycznej vs. składniowej .

W powyższym poście dowiedzieliśmy się o klasach semantycznych i syntaktycznych . Krótko mówiąc, kiedy klasę można scharakteryzować jako klasę języka liścia , to klasa jest składniowa, jeśli , to znaczy, akceptując język jest uzupełnieniem odrzucenia języka ; inaczej nazwalibyśmy to klasą semantyczną. Widać, że , i są klasami składniowymi, podczas gdy klasy takie jak i są klasami semantycznymi. $\mathsf{L}[L_1|L_2]$ $L_1 \cup L_2 = \Sigma^*$ $L_1$ $L_2$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{PP}$ $\mathsf{BPP}$ $\mathsf{IP}$

Klasyczny wynik, taki jak i przypuszczenie oba można wyświetlić, ponieważ klasy semantyczne okazują się mieć charakterystykę składniową. Wydaje mi się, że łatwiej jest sobie poradzić z klasami składniowymi, ponieważ mają one naturalne kompletne problemy. Również techniki takie jak diagonalizacja są łatwiejsze do zastosowania w klasach składniowych, ponieważ mają one naturalne wyliczenie maszynowe. Ale nadal jako klasa semantyczna wydaje się mieć znacznie lepsze właściwości niż klasa syntaktyczna . $\mathsf{PSPACE} = \mathsf{IP}$ $\mathsf{P} \stackrel{?}{=} \mathsf{BPP}$ $\mathsf{BPP}$ $\mathsf{PP}$

Jakie korzyści mamy, jeśli mamy składniową reprezentację klasy semantycznej lub odwrotnie? Czy istnieją wyniki lub techniki dowodowe stosowane tylko do klas składniowych / semantycznych?

cc.complexity-theory complexity-classes big-picture

— Hsien-Chih Chang 張顯之
źródło

1

Nigdy nie może zaszkodzić syntaktyczna charakterystyka klasy semantycznej. Nie rozumiem, w jaki sposób można porównać korzyści z posiadania składniowej lub semantycznej charakterystyki klasy. Nie wiadomo, że BPP ma charakterystykę składniową, ale powszechnie uważa się, że ma taką charakterystykę (jeśli P = BPP), więc fakt, że BPP ma „ładne właściwości”, nie wydaje się mieć nic wspólnego z tym, że jest klasą semantyczną .

— Robin Kothari,

@Robin: Dzięki za komentarz. Powinniśmy więc rozważyć klasę semantyczną, w której nie uważa się, że ma charakterystykę składniową, powiedzmy o jednoznacznym czasie . Ale nie ma zbyt wiele „ładnych właściwości”. Jakieś inne przykłady?

U P

$\mathsf{UP}$

— Hsien-Chih Chang 張顯之

na „lub vice versa”: czym byłaby semantyczna charakterystyka klasy składniowej? Czy istnieją przykłady klasy semantycznej bez takiej charakterystyki semantycznej?

— Artem Kaznatcheev

1

@Artem: Chyba liczy się klasa ? To ładna klasa składniowa, ale nie istnieje znana charakterystyka semantyczna. (W przeciwieństwie do prawdopodobnej hipotezy , która redukuje klasę składniową w coś, co akceptuje lub odrzuca tylko z określonymi wzorami; tutaj akceptuje tylko wtedy, gdy istnieje unikalna ścieżka akceptacji obliczeń i odrzuca jeśli nie ma.)

N P

$\mathsf{NP}$

N L = U L

$\mathsf{NL} = \mathsf{UL}$

N L

$\mathsf{NL}$

— Hsien-Chih Chang 張顯之

4

Oto kilka zalet.

Klasy składniowe zapewniają hierarchie czasu. Dowód Zaka na niedeterministyczną hierarchię czasu działa dla każdej klasy składniowej. W przypadku klas semantycznych (takich jak UPTIME ( )? UTPIME ( )) są to pytania otwarte. $n^3$ $=$ $n^2$
Łatwiej jest tworzyć wyrocznie, które oddzielają klasy składniowe, ponieważ wystarczy nieskończenie często przekątna i nie obchodzi Cię, co stanie się z innymi długościami wejściowymi. I odwrotnie, łatwiej jest zwinąć klasy semantyczne, ponieważ można wyeliminować maszyny, które nie spełniają obietnicy.

— Lance Fortnow
źródło

3

Myślę, że na tym poziomie ogólności już zwróciłeś uwagę na niektóre z głównych wartości klas składniowych w tym pytaniu: mają one wyliczenie maszyn, aw konsekwencji mają naturalne kompletne problemy i łatwiej jest zrobić przekątną. Oczywiście, określone klasy semantyczne (takie jak UP) mogą mieć inne zalety, ale ogólnie dla samego „syntaktycznego vs semantycznego”, myślę, że główną zaletą jest wyliczenie maszyny i jej konsekwencje.

— Joshua Grochow
źródło

0

Uważam, że korzyścią z utworzenia klasy semantycznej jest możliwość wyizolowania odpowiedzi, których naprawdę pragniesz. Na przykład w UP martwimy się, czy istnieje jedno rozwiązanie, czy zero rozwiązań i nie obchodzi nas, czy istnieje więcej niż jedno rozwiązanie. Uważam, że klasa semantyczna jest sposobem dostrajania klas składniowych.

— Tayfun Pay
źródło