Problèmes conjecturés mais non avérés faciles

Nous avons beaucoup de problèmes, comme factorisation, qui sont fortement conjecturé, mais non prouvé, à l'extérieur P. Y a-t- il des questions avec la propriété opposée, à savoir qu'ils sont fortement conjecturé mais pas prouvé être à l' intérieur de P?

complexity-theory polynomial-time Elliot Gorokhovsky
la source

Une demande de référence comme la vôtre est trop large pour Stack Exchange - vous demandez une enquête sur tout un domaine de recherche! Vous devez affiner considérablement votre objectif avant qu'une question de portée raisonnable n'apparaisse. Essayez de parler à votre (vos) conseiller (s), effectuez une recherche avec Google Scholar et consultez ce guide pour de meilleures (re) recherches sur Academia .

Raphael

Nous n'avons pas de politique stricte pour les questions de liste, mais il y a une aversion générale . Veuillez noter également ceci et cette discussion; vous voudrez peut-être améliorer votre question afin d'éviter les problèmes qui y sont expliqués. Si vous ne savez pas comment améliorer votre question, nous pouvons peut-être vous aider dans le chat informatique ?

Raphael

Vous voulez dire des problèmes où personne ne sait s'ils sont à l'intérieur ou à l'extérieur de P?

Trilarion

Il existe de tels problèmes sur certaines sous-classes de graphiques; J'essaierai d'ajouter une réponse plus tard.

Juho

@Juho Je serais intéressé de voir votre réponse

Elliot Gorokhovsky

Réponses:

Il y a deux décennies, l'une des réponses plausibles serait le test de primalité : il y avait des algorithmes qui fonctionnaient en temps polynomial aléatoire, et des algorithmes qui fonctionnaient en temps polynomial déterministe sous une conjecture théorique théorique plausible, mais aucun algorithme déterministe en temps polynomial déterministe. En 2002, cela a changé avec un résultat révolutionnaire par Agrawal, Kayal et Saxena que le test de primalité est en P. Donc, nous ne pouvons plus utiliser cet exemple.

Je mettrais le test d'identité polynomiale comme exemple d'un problème qui a de bonnes chances d'être en P, mais où personne n'a pu le prouver. Nous connaissons des algorithmes à temps polynomial randomisés pour les tests d'identité polynomiale, mais aucun algorithme déterministe. Cependant, il existe des raisons plausibles de croire que les algorithmes randomisés peuvent être dérandomisés.

Par exemple, en cryptographie, il est fortement admis qu'il existe des générateurs pseudo-aléatoires hautement sécurisés (par exemple, AES-CTR est un candidat raisonnable). Et si cela est vrai, alors le test d'identité polynomiale devrait être en P. (Par exemple, utilisez une graine fixe, appliquez le générateur pseudo-aléatoire et utilisez sa sortie au lieu de bits aléatoires; il faudrait une conspiration énorme pour que cela échoue. ) Cela peut être officialisé en utilisant le modèle d'oracle aléatoire; si nous avons des fonctions de hachage qui peuvent être modélisées de manière appropriée par le modèle d'oracle aléatoire, il s'ensuit qu'il existe un algorithme déterministe en temps polynomial pour les tests d'identité polynomiale.

Pour plus de détails sur cet argument, voir aussi ma réponse sur un sujet connexe et mes commentaires sur une question connexe .

DW
la source

$P=NP$

$P$

Mais, encore une fois, personne ne sait vraiment.

$P$ $P$ $P$

jmite
la source

Je pensais que l'isomorphisme du graphe était bien assis dans le voisinage proche de NP-C?

John Dvorak

@JanDvorak mathoverflow.net/questions/223420/…

xavierm02

P

$\mathsf P$

$\sf NP\cap coNP$ $e^{O(\sqrt{n})}$ $n$ $\sf P$

Wojowu
la source

\cap

$\cap$

e^{\sqrt{n}}

$e^{\sqrt{n}}$

@DW Pourriez-vous donner un exemple d'un tel problème qui serait extérieur à P? Je n'en connais aucun.

Wojowu

Bien sûr: factorisation, journal discret. Ou, trouver un équilibre Nash approximatif d'un jeu à deux joueurs, et d'autres (voir ce commentaire de Scott Aaronson ). Ou, GapCVP , la version d'espace du problème du vecteur le plus proche pour les réseaux, avec les paramètres appropriés.

en.wikipedia.org/wiki/… : "Il est connu qu'il soit à la fois NP et co-NP. C'est parce que [...]"

@DW Ah, c'est vrai. Je vois maintenant comment cela invalide ma réponse. Je pense que je vais le laisser quand même, mais merci d'avoir clarifié les choses!

Wojowu