Problèmes en dehors de P qui ne sont pas P-dur

En lisant une réponse de Peter Shor et une question précédente d'Adam Crume, j'ai réalisé que j'avais des idées fausses sur ce que signifie être -hard. $\mathsf{P}$

Un problème est -hard si un problème dans est réductible à lui avec des réductions (ou si vous préférez ). Un problème est en dehors de s'il n'existe pas d'algorithme de temps polynomial pour le résoudre. Cela signifie qu'il devrait y avoir un problème qui est en dehors de mais qui n'est pas -hard. Si nous supposons que FACTORING est en dehors de , alors la réponse de Peter Shor suggère que FACTORING pourrait être un tel problème. $\mathsf{P}$ $\mathsf{P}$ $\mathsf{L}$ $\mathsf{NC}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$

Y a-t-il des problèmes connus (naturels ou artificiels) qui sont connus pour se situer en dehors de mais ne pas être -hard? Qu'en est-il des hypothèses plus faibles que l'hypothèse d'affacturage? Y a-t-il un nom pour cette classe de complexité? $\mathsf{P}$ $\mathsf{P}$

cc.complexity-theory complexity-classes Artem Kaznatcheev
la source

Réponses:

Si $\mathsf{P} \neq \mathsf{L}$ aucun ensemble clairsemé (même non calculable) ne peut être $\mathsf{P\text{-}hard}$ .

L'idée fausse vient de la réflexion sur les classes de complexité (et les problèmes de calcul) comme créant un ordre linéaire qui n'est pas vrai. L'utilisation du mot «dureté» pour un problème peut être utilisée pour résoudre d'autres problèmes dans la classe contribue également à l'idée fausse. Une limite inférieure pour un problème (c'est-à-dire ne faisant pas partie d'une classe de complexité) n'implique pas que le problème est difficile pour la classe (c'est-à-dire qu'il peut être utilisé pour résoudre d'autres problèmes dans la classe). Je ne sais pas s'il existe une meilleure terminologie alternative pour la «dureté» qui est utilisée actuellement, celle qui a été utilisée au cours des décennies précédentes est «l'universalité» (qui, à mon humble avis, a exprimé le concept plus fidèlement, et ensuite nous aurions pu utiliser "dureté" pour ne pas être dans la classe, mais changer la terminologie établie est très difficile).

Kaveh
la source

certains des diagrammes d'Euler que j'ai vus sur les classes de complexité ont également alimenté la deuxième idée fausse pour moi, ce qui, selon moi, a causé ma confusion à propos de la dureté X.

Artem Kaznatcheev

@Artem, oui, c'est aussi un facteur. Voici ce que je fais en classe: je mentionne l'incomparabilité des réductions de et sous , en espérant que cela aiderait les élèves à éviter de penser que tout est ordonné linéairement.

\mod p

$\mod p$

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Kaveh

la partie de la commande totale avec laquelle j'ai beaucoup moins de problèmes. En particulier, je pense que NP et coNP sont assez bons pour montrer que nous ne devrions pas penser à des classes de complexité ayant un ordre total.

Artem Kaznatcheev

@Artem, bon point (même si nous ne pouvons pas prouver qu'ils sont différents). Je pense qu'une partie de la raison de la terminologie est le manque de limites inférieures raisonnables, nous n'avons pas une bonne limite inférieure pour SAT, mais nous pensons qu'il est difficile à résoudre parce qu'il est universel, mais le mot "universel" ne le fait pas. donner le même sentiment de difficulté que «dur», en particulier aux non-experts. Mais cela crée le problème parce que, bien que l'on puisse soutenir que l'universalité d'un problème implique que le problème est difficile à résoudre, la difficulté de résoudre un problème n'implique pas que le problème est universel.

Kaveh

c'est-à-dire que les problèmes universels sont difficiles (au moins aussi difficiles que n'importe quel problème de la classe), mais les problèmes difficiles n'ont pas besoin d'être universels.

Kaveh

Je pense que vous pouvez construire un ensemble non en qui n'est pas -hard par un argument de style Ladner. Voici un exemple précis. $P$ $P$

Dans son article "Une approche uniforme pour obtenir des ensembles diagonaux dans les classes de complexité" (Theor. Comp. Sci. 18, 1982), Schöning prouve ce qui suit:

Théorème Supposons que , , et sont des classes de complexité présentables récursivement et sont fermées sous des variations finies. Ensuite, il y a un ensemble tel que , , et si et n'est pas trivial (ensemble vide ou toutes les chaînes), alors est polytime plusieurs-un réductible à . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

Pour appliquer ce, ensemble à l'ensemble vide, et être -complete en réduction des polynomial, ensemble l'ensemble des des ensembles de qui sont , définies . L'ensemble vide ne peut pas être -hard (la définition de -hardness pour une langue nécessite qu'il y ait au moins une instance dans la langue et une instance non dedans). n'est certainement pas dans . Le et le peuvent être vérifiés pour répondre aux conditions ci-dessus (similaire à la façon dont Schoening le fait pour le $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ $C_2$ $NP$ -ensembles complets; voir aussi cette question connexe ). Nous obtenons donc un qui est pas un problème -hard dans , et que est pas dans . Mais comme et n'est pas trivial, est plusieurs réductible à un ensemble complet d' , donc il est dans . Par conséquent, en particulier, ne peut pas non plus être dur. $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ $P$

Dans l'argument ci - dessus, la restriction à problèmes de dans est nécessaire pour assurer présentabilité récursive, puisque les problèmes P dur dans son ensemble sont pas récursive présentable et même pas dénombrable . Maintenant, des exemples "naturels" de cela sont une autre histoire ... $P$ $EXP$

Ryan Williams
la source

Je aime comment cela passe par , même si . Sauf si j'ai mal compris quelque chose.

L = P

$L = P$

Artem Kaznatcheev

@Artem: Si vous considérez la dureté sous la réduction de l'espace logarithmique, alors chaque langue non triviale est L-hard. Par conséquent, si L = P, il n'y a pas de langues en dehors de P qui sont P-hard sous la réductibilité de l'espace logarithmique.

Tsuyoshi Ito

Une autre façon de générer des problèmes qui sont en dehors de P mais pas P-dur est de prendre des problèmes complets pour des classes incomparables avec P. Disons qu'une classe X est incomparable avec P, dans le sens où ni l'un ni l'autre n'est un sous-ensemble de l'autre. Alors un problème X-complet est nécessairement en dehors de P (sinon P inclurait X) et n'est pas P-dur (sinon X inclurait P).

J'ai essayé de penser à certaines classes incomparables avec P, mais P est une classe assez robuste, donc il n'y en a pas trop. Par exemple, RNC et QNC peuvent être incomparables avec P. DSPACE ( ) peuvent également être incomparables avec P. PolyL est incomparable avec P, mais n'a pas de problèmes complets avec les réductions d'espace de journalisation. $\log^2$

Robin Kothari
la source

À mon avis, c'est presque la même question formulée différemment, et ce n'est pas nécessairement un moyen de répondre à la question. En fait, le langage A n'est ni en P ni en P dur si et seulement si la classe des langages réductibles en A est incomparable avec P (prenez votre notion préférée de réductibilité). Tant que la question actuelle est concernée, je pense qu'elle est plus susceptible d'être utile dans le sens opposé; c'est-à-dire que c'est une autre façon d'interpréter les réponses à la question actuelle.

Tsuyoshi Ito