Klasa złożoności syntaktycznej

Wiadomo, że niektóre (nie relatywizowane) klasy złożoności składniowej między i mają następującą właściwość, . Zastanawiam się, czy istnieje (nierelatywizowana) klasa złożoności składniowej taka, że ${\bf P}$ ${\bf PSPACE}$ ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$ ${\bf X}$ ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$ ? Jakie są implikacje istnienia lub nieistnienia klasy złożoności ? ${\bf X}$

cc.complexity-theory complexity-classes

— Tayfun Pay
źródło

Po pierwsze, przypuszczalnie chcesz klasę, o której uważa się, że ściśle leży pomiędzy PP a PSPACE? W przeciwnym razie sam PP działa, podobnie jak PSPACE. Po drugie, trudno jest mówić o implikacjach istnienia takiej klasy złożoności, chyba że podasz, co jest liczone jako klasa złożoności. Na przykład, jeśli PP \ neq PSPACE, to przez Ladnera jest język L w PSPACE, który jest trudny dla PP i nie jest kompletny dla PSPACE. Jeśli weźmiemy zamknięcie L w ramach redukcji wielokrotnych jeden, wynikowa „klasa” spełni twoje pytanie. Ale najwyraźniej nie ma to żadnych dodatkowych konsekwencji poza PP \ neq PSPACE ...

— Joshua Grochow

@JoshuaGrochow Thanks! Jak o tym, czy

. Czy możemy uzyskać kolejną klasę od Ladnera?

P = P P

${\bf P} = {\bf PP}$

P \neq P S P A C E

${\bf P} \neq {PSPACE}$

— Tayfun Zapłać

A ⪇_{m}^{p} B

$A \lneq_m^p B$

A ⪇_{m}^{p} C ⪇_{m}^{p} B

$A \lneq_m^p C \lneq_m^p B$

Jedną z takich klas jest hierarchia zliczania . Jest zdefiniowany jako połączenie hierarchii, która jest zdefiniowana podobnie do hierarchii wielomianowej: $\mathsf{CH}$

$\mathsf{C}_{0}\mathsf{P} := \mathsf{PP}$ ,
$\mathsf{C}_{i+1}\mathsf{P} := \mathsf{PP}^{\mathsf{C}_{i}\mathsf{P}}$
$\mathsf{CH} := \bigcup_i \mathsf{C}_{i}\mathsf{P}$

Hierarchia liczenia ma niezłą charakterystykę składniową dzięki H. Vollmerowi i K. Wagnerowi „Teoretyczne charakterystyki rekurencji klas złożoności funkcji zliczających”, Theoretical Computer Science 163: 245-258, 1996 : jest zbiorem - - funkcje wartościowane w zamknięciu podstawowych funkcji arytmetycznych w składzie i ograniczonych sumach. $\mathsf{CH}$ $0$ $1$ $0,1,+,-,\cdot$

— Jan Johannsen
źródło

Mówię konkretnie o braku relatywizacji ... Jest też

# P \cup # N P \cup . . .

${\bf\#P} \cup {\bf \#NP} \cup ...$

— Tayfun Pay

@TayfunPay: Ostatni akapit pokazuje, że można nadać charakterystykę bez użycia wyroczni ... co dokładnie rozumiesz przez „nie relatywizowany”? Czy chcesz mieć charakterystykę „maszyny innej niż wyrocznia”? Charakterystykę języka liścia?

C H

$CH$

— Joshua Grochow

To jest rzeczywiście poprawne. Ok

— Tayfun Zapłać