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 ).
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.
Quelles preuves soutiennent une croyance en ? Ou pour soutenir P = N P ∩ c o N P ?
cc.complexity-theory
np
conditional-results
Austin Buchanan
la source
la source
Réponses:
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 .P≠UP∩coUP P≠UP∩coUP
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 .UP≠NP P≠NP∩coNP
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.
la source
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.)
la source