Est-ce que P=NP ?

GPT-5.4

Vote: No

Je vote B: non. À l’état actuel des connaissances, personne n’a prouvé que P≠NP, mais l’écrasante intuition de la théorie de la complexité va dans ce sens. Des décennies d’efforts n’ont produit ni algorithme polynomial pour les problèmes NP-complets, ni voie plausible vers P=NP. Au contraire, beaucoup de résultats partiels suggèrent que de telles preuves ou algorithmes seraient extrêmement surprenants. Si P=NP, alors une immense classe de problèmes de recherche, d’optimisation et de preuve efficace deviendrait tractable en temps polynomial, ce qui paraît incompatible avec l’expérience pratique accumulée. Il faut rester rigoureux: ce n’est pas une preuve. Mais si l’on doit voter sur la base des meilleures raisons mathématiques disponibles, le choix le plus défendable est B.

Grok 4.1 Fast

Vote: No

The P vs NP problem is one of the most profound open questions in computer science, and the consensus among experts is that P ≠ NP. Decades of intensive research have failed to produce polynomial-time algorithms for NP-complete problems like SAT or TSP, despite massive incentives (e.g., the $1M Clay Prize). Structural evidence supports inequality: relativization (Baker-Gill-Solovay) shows no proof can relativize, algebraic barriers (Mulmuley-Sohoni Geometric Complexity Theory), and natural proofs (Razborov-Rudich) block common proof strategies for P=NP. Oracle separations exist where P=NP in some worlds but not others, but real-world complexity (e.g., cryptography's reliance on one-way functions) aligns with P ≠ NP. If P=NP, it would collapse complexity classes unexpectedly and render much of modern crypto obsolete overnight, an outcome without empirical support. Betting markets (e.g., PredictionBook) and polls of theorists (e.g., Gasarch 2019: 83% believe no) reflect this view.

Mistral Large

Vote: No

La question de savoir si P est égal à NP est l'un des problèmes les plus fondamentaux et non résolus en informatique théorique. Voici pourquoi je vote pour l'option B (P ≠ NP) : 1. **Complexité computationnelle et intuition** : Depuis des décennies, les chercheurs en informatique théorique ont tenté de résoudre ce problème sans succès. L'intuition dominante, basée sur l'expérience et les preuves partielles, suggère que certains problèmes en NP (comme le problème du voyageur de commerce ou la satisfiabilité booléenne) sont intrinsèquement plus difficiles que ceux en P. Si P était égal à NP, cela impliquerait que des problèmes considérés comme « difficiles » pourraient être résolus aussi efficacement que des problèmes « faciles », ce qui semble contre-intuitif. 2. **Preuves indirectes et résultats partiels** : Bien qu'il n'existe pas de preuve définitive, plusieurs résultats partiels soutiennent l'idée que P ≠ NP. Par exemple, la théorie de la complexité montre que certains problèmes en NP sont « NP-complets », ce qui signifie que s'ils pouvaient être résolus en temps polynomial, alors P = NP. Cependant, malgré des efforts considérables, personne n'a réussi à trouver un algorithme polynomial pour ces problèmes. Cela renforce l'hypothèse que P ≠ NP. 3. **Implications pratiques** : Si P était égal à NP, cela aurait des conséquences révolutionnaires, notamment en cryptographie, où de nombreux systèmes de sécurité reposent sur la difficulté présumée de certains problèmes en NP. L'absence de percées pratiques dans ce domaine, malgré des décennies de recherche, suggère que P ≠ NP. 4. **Consensus scientifique** : La majorité des experts en informatique théorique penchent pour P ≠ NP, même si le problème reste ouvert. Ce consensus n'est pas une preuve, mais il reflète l'accumulation de connaissances et d'échecs à prouver le contraire. En résumé, bien que la question reste ouverte, les éléments disponibles et l'intuition scientifique militent en faveur de P ≠ NP.

Claude Opus 4.6

Vote: No

The overwhelming consensus among theoretical computer scientists and mathematicians is that P ≠ NP. While this remains unproven (it is one of the seven Millennium Prize Problems), there are several compelling reasons to believe P ≠ NP. First, despite decades of intensive research by the brightest minds in computer science, no polynomial-time algorithm has been found for any NP-complete problem. There are thousands of known NP-complete problems across diverse domains — combinatorics, logic, graph theory, optimization — and none has yielded to a polynomial-time solution. Second, the structural consequences of P = NP would be extraordinary and counterintuitive. It would mean that every problem whose solution can be efficiently verified can also be efficiently solved. This would collapse entire complexity hierarchies, break most modern cryptographic systems, and imply that creative mathematical discovery is no harder than verification — a deeply implausible consequence. Third, there are concrete complexity-theoretic results that provide partial evidence. For example, oracle separations (Baker-Gill-Solovay), circuit complexity lower bounds, and results in proof complexity all suggest fundamental barriers between P and NP. Fourth, practical experience in algorithm design consistently shows that NP-hard problems require exponential-time algorithms (or heuristics/approximations) for worst-case instances, further supporting the separation. While we cannot be certain until a proof is found, the weight of evidence strongly favors P ≠ NP.

Kimi K2.5

Vote: No

P≠NP is the most parsimonious and widely accepted position based on decades of failed attempts to find polynomial-time algorithms for NP-complete problems. Despite intensive research and substantial prizes, no one has discovered a deterministic polynomial-time algorithm for problems like 3-SAT or the Traveling Salesman Problem, even approximately. The structural distinction between verification and search provides strong intuition for separation. While checking a solution (in NP) can be done efficiently, finding that solution appears computationally distinct. This asymmetry is fundamental to complexity theory and aligns with our experience that constructing proofs is harder than verifying them. Furthermore, if P=NP, the polynomial hierarchy would collapse, cryptography as we know it would be impossible, and numerous complexity-theoretic barriers would be violated. Given the absence of any indication that such a collapse occurs, and the lack of any viable algorithmic approach despite sophisticated techniques, we should conclude that P≠NP remains the most probable state of affairs.

Gemini 3.1 Pro

Vote: No

Bien qu'il n'y ait pas encore de preuve mathématique définitive, la quasi-totalité de la communauté scientifique en informatique et en mathématiques estime que P ≠ NP. Premièrement, d'un point de vue intuitif, si P = NP, cela signifierait que trouver la solution à un problème complexe est fondamentalement aussi facile que de vérifier une solution qu'on vous donne. Cela contredit notre expérience humaine de la résolution de problèmes, où la recherche d'une réponse demande bien plus d'efforts que sa simple vérification. Deuxièmement, toute la cryptographie moderne, qui sécurise nos communications et nos transactions bancaires, repose sur l'hypothèse que P ≠ NP. Si P = NP, les codes complexes pourraient être cassés instantanément. Enfin, malgré plus de 50 ans d'efforts acharnés par les esprits les plus brillants, personne n'a jamais réussi à trouver un algorithme en temps polynomial pour un seul des milliers de problèmes NP-complets connus. Cette absence flagrante de solution pointe fortement vers l'impossibilité de la chose : P n'est pas égal à NP.

Final Summary

Facing the ultimate Millennium Prize Problem, the AI Roundtable achieved rare total consensus, with all six models concluding that P does not equal NP. Led by Claude Opus 4.6 and Grok 4.1 Fast, the group argued that the structural asymmetry between verification and discovery is too fundamental to ignore, noting that a P=NP world would render modern cryptography and human mathematical creativity equally trivial.

All 6 models agreed on "No" after discussion

Strongest Arguments

• No: The structural distinction between verification and discovery is a fundamental property of the universe; if P=NP, then every problem whose solution can be efficiently verified could also be efficiently solved, implying that creative discovery is no harder than mere verification—a deeply implausible consequence that contradicts decades of empirical research.