Raisons de croire

27

Il semble que beaucoup de gens croient que , en partie parce qu'ils pensent que l'affacturage n'est pas résolu par le polytime. (Shiva Kintali a énuméré quelques autres problèmes potentiels ici ).PNPcoNP

D'un autre côté, Grötschel, Lovász et Schrijver ont écrit que "beaucoup de gens croient que ". Cette citation se trouve dans Algorithmes géométriques et optimisation combinatoire, et Schrijver fait des déclarations similaires dans Optimisation combinatoire: polyèdres et efficacité . Cette image montre clairement où Jack Edmonds se situe sur la question.P=NPcoNP

Quelles preuves soutiennent une croyance en ? Ou pour soutenir P = N P c o N P ?PNPcoNPP=NPcoNP

Austin Buchanan
la source
Définissez la «raison». Il n'y a vraiment aucune preuve dans un sens ou dans l'autre. Ce n'est pas quelque chose qui peut être testé expérimentalement. Jusqu'à ce que nous ayons une preuve dans un sens ou dans l'autre, les seules "raisons de croire" que ce sont les sentiments intestinaux, soit qu'un problème dans n'est pas polynomial, soit un instinct instinctif qu'ils sont tous. NPcoNP
jmite
2
J'espérais des réponses comme ce que Scott Aaronson a donné pour P contre NP .
Austin Buchanan
1
plusieurs des mêmes idées d'Aaronson sont applicables. pas du tout d'accord avec jmite. il existe de nombreuses preuves circonstancielles , y compris des preuves expérimentales, dont certaines sont énumérées par aaronson.
vzn
5
Théorème 3.1 des permutations à sens unique et des langues auto-témoins C. Homan et M. Thakur, Journal of Computer and System Sciences, 67 (3): 608-622, novembre 2003. [ en .pdf ] déclare que P ≠ UP∩ COUP si et seulement si ("le pire des cas") des permutations unidirectionnelles existent. Le théorème 3.2 rappelle 10 autres hypothèses qui se sont avérées équivalentes à P ≠ UP∩coUP.
Thomas Klimpel
9
Je pense que l'affacturage ∈ P est beaucoup plus nombreux que P = NP ∩ coNP, donc ce n'est certainement pas la raison pour laquelle je crois que P = NP ∩ coNP.
Peter Shor

Réponses:

5

Théorème 3.1 des permutations à sens unique et des langues auto-témoins C. Homan et M. Thakur, Journal of Computer and System Sciences, 67 (3): 608-622, novembre 2003. [ en .pdf ] déclare que si et seulement si ("le pire des cas") des permutations unidirectionnelles existent. Théorème 3.2 rappelle 10 hypothèses supplémentaires qui ont été montrés comme étant équivalent à P U P c o U P .PUPcoUPPUPcoUP

De plus, nous avons de fortes raisons de conjecture que . Par conséquent, le théorème ci - dessus et le résultat de la conjecture dans une bonne raison de croire que P N P de la c o N P .UPNPPNPcoNP


Avertissement: J'ai déplacé la modification de ma réponse de Mohammad Al-Turkistany vers cette réponse wiki communautaire. Il pense que cela répond parfaitement à la question car l'existence de permutations unidirectionnelles est largement admise. Je n'ai pas encore suffisamment compris moi-même la différence entre les fonctions unidirectionnelles "pire cas" et "cas moyen" pour affirmer que cela répond vraiment à la question.

Thomas Klimpel
la source
0

Je crois qu'il existe des générateurs de nombres aléatoires de haute qualité très efficaces en termes d'espace. Malgré cette croyance, j'utilise normalement Mersenne twister dans mon code, qui est de haute qualité, mais pas très économe en espace. Il y a un lien manquant entre l'efficacité spatiale et NP∩coNP, c'est juste un sentiment instinctif qu'il y a un lien.


Permettez-moi d'essayer de donner une raison pour laquelle je pense que le "vrai hasard" peut être simulé / approximé très efficacement. Nous savons qu'il est possible de produire des nombres pseudo-aléatoires suffisamment aléatoires à toutes fins pratiques (y compris la cryptographie). Nous savons également que l'utilisation (d'une petite quantité de nombres fixes) de grands nombres premiers dans la construction de générateurs de nombres pseudo-aléatoires est rarement une mauvaise idée. Nous savons par des conjectures comme celle de Riemann que presque tous les nombres premiers contiennent un degré élevé de caractère aléatoire, mais nous savons également que nous ne sommes pas encore en mesure de le prouver rigoureusement.

Y a-t-il une explication intuitive pour laquelle les nombres premiers se comportent comme des nombres aléatoires? Les nombres premiers sont le complément des nombres composites. Le complément d'un ensemble bien comporté est souvent plus compliqué que l'ensemble d'origine. Les nombres composites sont composés de nombres premiers, ce qui donne déjà à cet ensemble une certaine complexité.


Contexte J'ai essayé une fois de comprendre pourquoi P ≠ NP est difficile. Je me suis demandé si l'approximation des groupes de symétrie interne d'une instance de problème par des groupes nilpotents ne pouvait pas conduire à un "algorithme d'abstraction" capable de voir dans la structure interne de l'instance de problème. Mais je me suis alors rendu compte que même le calcul de la structure d'un groupe nilpotent contenait l'affacturage comme cas particulier. La question des sous-groupes simples d'un groupe cyclique d'ordre n revient à déterminer les facteurs premiers de n. Et la classification des groupes nilpotents finiscontient des sous-problèmes encore pires liés à l'isomorphisme des graphes. Cela a suffi à me convaincre que cette approche n'aidera pas. Mais ma prochaine étape était d'essayer de comprendre pourquoi l'affacturage est difficile, et la réponse ci-dessus est ce que j'ai trouvé. C'était suffisant pour me convaincre, alors peut-être que ce sera aussi convaincant pour les autres. (Je ne connaissais pas les groupoïdes ou les semi-groupes inverses à l'époque, qui sont probablement plus adaptés que les groupes nilpotents pour gérer les symétries internes. Pourtant, l'argument selon lequel une telle approche ne sera pas efficace reste le même.)

Thomas Klimpel
la source
2
Je ne sais pas comment cette réponse se rapporte à la question. Pourriez-vous élaborer?
Matthias
@Matthias La réponse est la raison pour laquelle je crois que P ≠ NP∩coNP. Le problème n'est donc probablement pas la relation avec la question, mais comment expliquer le raisonnement. Il existe une forme de platonisme mathématique impliquée, qui suppose que les structures mathématiques sont capables de modéliser ou d'approximer presque tout ce qui peut exister dans ce monde. Le vrai hasard fait partie de ce qui peut exister, et la réponse tente d'expliquer pourquoi il y a un sentiment profond que ce hasard est déjà présent dans des contextes suffisamment limités en espace pour provoquer P ≠ NP∩coNP. (Désolé, je vais peut-être améliorer / supprimer ce commentaire plus tard.)
Thomas Klimpel
2
Merci. Je suppose que je me demandais pourquoi l'existence de générateurs de nombres aléatoires de haute qualité à faible encombrement implique que P NP coNP, parce que je n'ai jamais entendu cela auparavant.
Matthias
@Matthias J'ai écrit "... chaînon manquant entre l'efficacité spatiale et NP∩coNP, c'est juste un instinct ..." dans la réponse. Je pourrais essayer d'élaborer, mais je crains que cela ne soit pas bien reçu. En fait, je suppose que vous préférez des références indépendantes pointant dans cette direction au lieu de mes propres explications. Au Complexity Zoo , j'ai trouvé le résultat cité "Pire cas" des permutations unidirectionnelles existent si et seulement si P n'est pas égal à UP ∩ coUP [ HT03 ]. Le journal est en ligne, mais je ne l'ai pas (encore) lu ...
Thomas Klimpel