Преимущества для синтаксических и семантических классов

Этот пост отделен от Последствия UP равно NP , а также является дополнительным вопросом к классам семантической и синтаксической сложности .

В вышеприведенном посте мы узнали о семантических и синтаксических классах. Вкратце, если класс можно охарактеризовать как листовой класс языка , то класс является синтаксическим, если , то есть принятие языка является дополнением отвергая язык ; в противном случае мы назвали это семантическим классом. Можно видеть, что , и являются синтаксическими классами, а такие классы, как и являются семантическими классами.$\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}$

Классический результат, такой как и гипотеза можно просматривать, поскольку семантические классы имеют синтаксические характеристики. Мне кажется, что с синтаксическими классами легче обращаться, поскольку они имеют естественные полные проблемы. Также такие методы, как диагонализация, легче применять к синтаксическим классам, поскольку они имеют естественное машинное перечисление. Но все же как семантический класс, похоже, обладает гораздо более приятными свойствами, чем синтаксический класс .$\mathsf{PSPACE} = \mathsf{IP}$$\mathsf{P} \stackrel{?}{=} \mathsf{BPP}$$\mathsf{BPP}$$\mathsf{PP}$

Какие преимущества мы имеем, если у нас есть синтаксическое представление семантического класса, или наоборот? Существуют ли результаты или методы проверки, применимые только к синтаксическим / семантическим классам?

Вот несколько преимуществ.

1. Синтаксические классы дают вам временную иерархию. Доказательство Зака о недетерминированной иерархии времени работает для любого синтаксического класса. Для семантических классов (например, UPTIME ($n^3$)?$=$UTPIME ($n^2$)) это открытые вопросы.
2. Легче создавать оракулы, которые разделяют синтаксические классы, поскольку вам нужно только диагонализировать бесконечно часто, и вам все равно, что происходит с другими длинами ввода. И наоборот, проще свернуть семантические классы, поскольку вы можете исключить машины, которые не выполняют обещание.

Я думаю, что на этом уровне общности вы уже выделили некоторые из основных значений синтаксических классов в вопросе: у них есть перечисление машин, и, как следствие, у них есть естественные полные проблемы, и диагонализацию легче выполнить. Конечно, определенные семантические классы (такие как UP) могут иметь другие преимущества, но для всего «синтаксический против семантического» в целом, я думаю, что машинное перечисление и его последствия являются основным преимуществом.

Я считаю, что выгода от создания семантического класса состоит в том, чтобы иметь возможность выделить ответы, которые вы на самом деле хотите. Например, в UP нас интересует, есть ли одно решение или ноль решений, и нам не важно, есть ли более одного решения. Я считаю, что семантический класс - это способ тонкой настройки синтаксических классов.