Korzyści dla klas składniowych i semantycznych

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?

Oto kilka zalet.

1. 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$
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.

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.

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.