Auf der Suche nach einem netten Problem in SC, aber nicht in den ersten beiden Levels

Der Komplexitätszoo hat nicht viel mit dem $\mathsf{SC}$ . Ich suche ein nettes Problem, das in höheren Hierarchieebenen liegt, dh ein Problem in aber nicht bekannt ist in $^\dagger$ $\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ . $\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$

Als es einen bekannten Grund, warum das Finden von Beispielen für nette Probleme in höheren Hierarchieebenen ( , , , usw.) so ist schwieriger als die ersten Levels? $\mathsf{AC}$ $\mathsf{NC}$ $\mathsf{SC}$ $\mathsf{PH}$

$\dagger$ obwohl schön ist kein mathematischer Begriff Ich denke, wir verstehen intuitiv, was es bedeutet, z. B. das Akzeptieren von Problemen für NTMs ist ein künstliches Problem, das die Leute nicht interessiert, abgesehen davon, dass es für vollständig ist , während das Diagramm Das Problem war interessant, bevor bekannt wurde, dass es für in / complete ist, und es ist immer noch interessant, abgesehen von der Komplexitätsklasse, zu der es gehört. $\mathsf{NP}$ $\mathsf{NP}$

cc.complexity-theory complexity-classes Kaveh
quelle

(1) „Das Akzeptieren von Problemen für NTMs ist kein künstliches Problem, das die Leute nicht interessieren, abgesehen davon, dass es für NP vollständig ist“: Anscheinend haben Sie hier ein exzessives „Nicht“.

Tsuyoshi Ito

(2) „Gibt es als Nebenfrage einen bekannten Grund, warum es schwieriger ist, Beispiele für nette Probleme in höheren Hierarchieebenen (AC, NC, SC, PH usw.) zu finden als in den ersten Ebenen?“ Benötigen Sie eine Ein tieferer Grund als "Niedrigere Ebenen sind einfacher und daher gibt es viele schöne Beispiele in ihnen"?

Tsuyoshi Ito

@ Tsuyoshi, danke, ich habe das extra nicht entfernt. Über 2, ja, ich brauche einen tieferen Grund für nette Probleme, die in die niedrigen Hierarchiestufen fallen. Ich sehe keinen großen Definitionsunterschied zwischen

und sage

D T i m e S p a c e (n^{O (1)}, \lg^{2} n)

$\mathsf{DTimeSpace}(n^{O(1)},\lg^2 n)$

D T i m e S p a c e (n^{O (1)}, \lg^{4} n)

$\mathsf{DTimeSpace}(n^{O(1)},\lg^4 n)$

Kaveh

Natürlich ist die Definition dieselbe. Der Unterschied besteht darin, dass log ^ 2 einfacher ist als log ^ 4. Dasselbe Argument gilt für die Frage, warum es viel mehr Algorithmen gibt, die zur Zeit O (n ^ 2) ausgeführt werden als diejenigen, die zur Zeit O (n ^ 4) ausgeführt werden.

Tsuyoshi Ito

@ Tsuyoshi, ich bin mir nicht sicher, was du damit meinst, dass

einfacher ist als

. Die Frage gilt auch für

\lg^{4}

$\lg^4$

\lg^{2}

$\lg^2$

P

$\mathsf{P}$

Kaveh

Antworten:

Ich habe keinen Vorschlag für ein natürliches Problem in , aber ich habe einen Vorschlag für Ihre Nebenfrage, warum ein solches gefunden wird Problem scheint schwierig. Ich denke, das hat etwas mit der Volksidee zu tun, dass die Leute nur Mathe wirklich verstehen können (oder vielleicht nur interessiert sind? Oder beides?), Die ein paar Quantifizierer-Abwechslungen tief ist. Zum Beispiel ist die Definition der Grenze zwei Quantifizierer tief (für alle epsilon gibt es ein Delta ...); die Definition von " $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$ $L \in \mathsf{NP}$ "ist zwei Quantifizierer (es gibt eine Maschine, die für alle Eingaben ...), und die Aussage" "ist drei Quantifizierer tief. $\mathsf{P} \neq \mathsf{NP}$

In Bezug auf , ist dies etwas durch die Tatsache bestätigt , dass es viele Probleme , die von natürlichen sind -komplette, viele natürliche Probleme, die -komplette, und nur wenige bekannte natürliche Probleme, die vollständig (siehe das Kompendium von Schaefer und Umans ). Die natürlichsten Probleme, von denen bekannt ist, dass sie für höhere -Niveaus vollständig sind, kommen von der Logik selbst, was weniger überraschend ist, da man innerhalb einer gegebenen Logik häufig den Begriff " " hat $\mathsf{PH}$ $\mathsf{NP}$ $\mathsf{\Sigma_2 P}$ $\mathsf{\Sigma_3 P}$ $\mathsf{PH}$ $k$ -many quantifier alternations "oder zumindest auf eine natürliche Art und Weise zu simulieren. Diese fallen möglicherweise in dieselbe Kategorie wie" Akzeptieren von Problemen für NTMs ", die Sie für diese Frage als" nicht nett genug "deklariert haben.

$\mathsf{\Sigma^0_1}$ $\mathsf{\Sigma^0_4}$ $\mathsf{\Sigma^0_5}$ (obwohl vielleicht gibt es).

$\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$ $\mathsf{NL}$ $\mathsf{NL}$

Joshua Grochow
quelle

Dies ist eine sehr interessante Antwort.

Suresh Venkat

Danke Joshua, das ist in der Tat eine schöne Beobachtung. Es deutet auf eine erkenntnistheoretische Perspektive hin: Was für den Menschen natürlich aussieht, ist von begrenzter Quantifiziererkomplexität.

Kaveh