Vous cherchez un joli problème à l'intérieur de SC mais pas dans les deux premiers niveaux

Le zoo de complexité n'a pas grand-chose sur . Je recherche un joli problème qui se situe aux niveaux supérieurs de la hiérarchie, c'est-à-dire un problème dans mais dans . $\mathsf{SC}$ $^\dagger$ $\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ $\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$

Comme question secondaire, existe-t-il une raison connue pour laquelle trouver des exemples de problèmes intéressants dans les niveaux supérieurs de hiérarchies ( , , , , etc.) est plus difficile que les premiers niveaux? $\mathsf{AC}$ $\mathsf{NC}$ $\mathsf{SC}$ $\mathsf{PH}$

$\dagger$ bien que nice ne soit pas un terme mathématique, je pense que nous comprenons intuitivement ce que cela signifie, par exemple accepter un problème pour les MNT est un problème artificiel que les gens ne sont pas intéressés à part le fait qu'il soit complet pour , tandis que la coloration du graphique Le problème était intéressant avant d'être connu dans / complet pour et il est toujours intéressant à part la classe de complexité à laquelle il appartient. $\mathsf{NP}$ $\mathsf{NP}$

cc.complexity-theory complexity-classes Kaveh
la source

(1) «l'acceptation d'un problème pour les MNT n'est pas un problème artificiel que les gens ne sont pas intéressés à part le fait qu'il soit complet pour le NP»: il semble que vous ayez un «pas» excessif ici.

Tsuyoshi Ito

(2) "En guise de question secondaire, existe-t-il une raison connue pour laquelle il est plus difficile de trouver des exemples de bons problèmes dans les niveaux supérieurs de hiérarchie (AC, NC, SC, PH, etc.)?" Avez-vous besoin d'un une raison plus profonde que «Les niveaux inférieurs sont plus simples et donc il y a beaucoup de bons exemples en eux»?

Tsuyoshi Ito

@Tsuyoshi, merci, j'ai supprimé le supplément non. À propos de 2, oui, j'ai besoin d'une raison plus profonde pour que de beaux problèmes tombent dans les bas niveaux de hiérarchies. Je ne vois pas de grande différence de définition entre et dire .

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

Bien sûr, la définition est la même. La différence est que log ^ 2 est plus simple que log ^ 4. Le même argument s'applique pour demander pourquoi il y a beaucoup plus d'algorithmes qui s'exécutent dans le temps O (n ^ 2) que ceux qui s'exécutent dans le temps O (n ^ 4).

Tsuyoshi Ito

@Tsuyoshi, je ne sais pas trop ce que vous entendez par étant plus simple que . La question s'applique également à .

\lg^{4}

$\lg^4$

\lg^{2}

$\lg^2$

P

$\mathsf{P}$

Kaveh

Réponses:

Je n'ai pas une suggestion pour un problème naturel dans , mais j'ai une suggestion pour votre question de côté, pourquoi trouver un tel problème semble difficile. Je pense que cela a quelque chose à voir avec l'idée populaire selon laquelle les gens ne peuvent vraiment comprendre (ou ne sont peut-être intéressés que? Ou les deux?) Que les mathématiques sont profondes. Par exemple, la définition de limite est profonde de deux quantificateurs (pour tout epsilon il existe un delta ...); la définition de " $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$ $L \in \mathsf{NP}$ "est deux quantificateurs (il existe une machine telle que pour toutes les entrées ...), et la déclaration" "est profonde de trois quantificateurs. $\mathsf{P} \neq \mathsf{NP}$

En ce qui concerne , cela est quelque peu confirmé par le fait qu'il y a beaucoup de problèmes naturels qui sont complets, de nombreux problèmes naturels qui sont complets, et seulement quelques problèmes naturels connus qui sont -complet (voir le recueil de Schaefer et Umans ). Les problèmes les plus naturels connus pour être complets pour des niveaux plus élevés de proviennent de la logique elle-même, ce qui est moins surprenant car dans une logique donnée, on a souvent la notion de " $\mathsf{PH}$ $\mathsf{NP}$ $\mathsf{\Sigma_2 P}$ $\mathsf{\Sigma_3 P}$ $\mathsf{PH}$ $k$ -nombreuses alternances de quantificateurs ", ou du moins une manière naturelle de le simuler. Celles-ci entrent peut-être dans la même catégorie que" l'acceptation de problèmes pour les MNT ", que vous avez déclaré" pas assez sympa "pour cette question.

Il convient également de mentionner que la même chose se produit dans le monde de la calculabilité, ce qui suggère peut-être qu'elle a plus à voir avec notre compréhension des quantificateurs alternés et moins avec la complexité en soi. Beaucoup de problèmes naturels sont connus pour être -complets (équivalent au problème d'arrêt), et de nombreux problèmes naturels sont connus pour être complets pour les deuxième et troisième niveaux de la hiérarchie arithmétique. Mais à mesure que vous accédez à des niveaux supérieurs de la hiérarchie arithmétique, de moins en moins de problèmes naturels sont connus pour être complets pour ces niveaux. Je ne suis pas sûr de connaître un problème naturel complet pour , et je n'ai jamais entendu parler d'un problème naturel complet pour $\mathsf{\Sigma^0_1}$ $\mathsf{\Sigma^0_4}$ $\mathsf{\Sigma^0_5}$ (bien qu'il y en ait peut-être).

En ce qui concerne les limites spatiales polylogarithmiques, je pense qu'un raisonnement similaire s'applique, mais plus encore. Puisque , même les problèmes qui se trouvent dans les "premiers" niveaux de la " hiérarchie " sont tous en fait dans (la hiérarchie s'effondre ), qui est contenu dans un espace logarithmique. $\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$ $\mathsf{NL}$ $\mathsf{NL}$

Joshua Grochow
la source

Ceci est une réponse très intéressante.

Suresh Venkat

Merci Joshua, c'est en effet une belle observation. Cela suggère en quelque sorte une perspective épistémologique: ce qui semble naturel aux humains est d'une complexité quantifiante limitée.

Kaveh