Comment prouver P

Je suis conscient que cela semble une question très stupide (ou trop évidente à énoncer). Cependant, je suis confus à un moment donné.

Nous pouvons montrer que P NP$=$ si et seulement si nous pouvons concevoir un algorithme qui résout une instance donnée de problème dans NP en temps polynomial.

Cependant, je ne comprends pas comment diable peut-on prouver que P NP . Je vous prie de m'excuser pour la similitude suivante, car cela pourrait ne pas être pertinent, mais dire à quelqu'un de prouver si P n'est pas égal à NP me semble comme dire à quelqu'un de prouver que Dieu n'existe pas.$\neq$

Il y a un ensemble de problèmes, ceux-ci ne peuvent pas être résolus par un automate fini non déterministe (NFA) avec un nombre d'états polynomiaux quelle que soit la technologie actuelle (je sais que c'est une définition bâclée). De plus, nous avons un ensemble d'algorithmes considérablement important qui pose des problèmes cruciaux (chemin le plus court, arbre couvrant minimum et même somme des entiers ) problèmes de temps polynomial.$1 + 2 + \dots + n$

Ma question en bref: si je crois que P NP$=$ , vous diriez "alors montrez votre algorithme qui résout un problème NP en temps polynomial!". Supposons que je crois P NP . Alors que demanderiez-vous exactement? Que voudriez-vous que je montre?$\neq$

La réponse est clairement "votre preuve". Cependant, quel type de preuve montre qu'un algorithme ne peut pas exister? (dans ce cas, un algorithme de temps polynomial pour un problème NP )

Il y a trois façons principales dont je suis conscient qui pourraient prouver que P$\,\neq\,$NP .

1. $\Omega(n\log n)$$n$$O(n^c)$$c$La complexité du circuit en est un autre.

2. Montrant que P et  NP ont des propriétés structurales différentes. Par exemple, P  est fermé sous complémentation. Si vous pouviez montrer que NP$\,\neq\,$co-NP (c'est -à- dire que NP  n'est pas fermé par complémentation), alors doit être que P$\,\neq\,$NP . Bien sûr, cela ne fait que pousser le problème d'un niveau plus profond - comment prouver que NP$\,\neq\,$co-NP ?

   $\exists\mathrm{SO}$

3. Prouver qu'un problème n'est pas complet en NP . Si P$\,=\,$$\emptyset$$\Sigma^*$ $\,\neq\,$NP .

Ma question en bref: si je crois que P = NP , vous diriez "alors montrez votre algorithme qui résout un problème NP en temps polynomial!".

N'oubliez pas que vous devez encore prouver que votre algorithme résout le problème et qu'il fonctionne en temps polynomial.

Supposons que je crois P ≠ NP . Alors que demanderiez-vous exactement? Que voudriez-vous que je montre?

Tout d'abord, essayez d'expliquer "pourquoi" P ≠ NP , et pourquoi cette raison peut être utilisée pour prouver P ≠ NP dans un cadre logique approprié. Esquissez ensuite une preuve et expliquez comment ses parties les plus douteuses peuvent être défendues. Ensuite, décomposez cette preuve en déclarations plus simples, qui peuvent être vérifiées indépendamment.

• Par exemple, le cadre logique fourni par ZFC est bon (même trop bon dans un certain sens) pour prouver l'existence de modèles (d'ensembles d'axiomes explicitement donnés, souvent même satisfaisant à des propriétés métallogiques supplémentaires). Donc, si vous connaissez une raison pour P ≠ NP liée à l'existence d'un modèle avec des propriétés étranges, expliquez d'abord cette raison, puis montrez comment le modèle correspondant peut être construit dans ZFC.
• À titre d'exemple, je crois que l'une des raisons pour lesquelles « P » NP est que les mathématiques peuvent approximer presque tout ce qui se produit dans le monde physique, y compris le hasard. Cependant, il est connu que les systèmes formels sont très limités dans leur capacité à prouver qu'une chaîne, un nombre, un "objet" ou un "artefact" donné sont essentiellement aléatoires, il est donc peu probable que cette raison puisse être utilisée pour une preuve. dans tout système formel déterministe explicitement donné. Peut-être que si vous avez conçu un système de preuve probabiliste (quantique), vous ne pouvez vérifier certaines preuves dans le système que jusqu'à une probabilité finie en fonction de vos ressources physiques disponibles ...
• À titre de non-exemple probable, la loi du milieu exclu reflète fondamentalement une vue statique de l'univers (mathématique), et il est donc très peu probable qu'elle se vérifie dans un univers dynamique. Maintenant NP = coNP (ou tout autre effondrement de la hiérarchie polynomiale) serait fondamentalement une version approximative de la loi du milieu exclu en ce qui concerne la complexité temporelle, mais la complexité temporelle est trop proche d'un univers dynamique pour que cela soit possible. Il existe des cadres logiques comme la logique linéaire de Girard qui sont capables de capturer des aspects dynamiques de l'univers, alors ... Notez cependant que Brouwer était dans une situation similaire et a déjà déclaré l'échec nécessaire du programme de Hilbert comme fait dans son discours inaugural Intuitionisme et formalisme en 1912 (expliquant pourquoi ce serait un raisonnement circulaire), mais n'a toujours pas pu esquisser la preuve d'incomplétude de Gödel de 1930.
• À titre d'exemple approximatif, essayons de capturer certaines des preuves disponibles pour P ≠ NP , à savoir la limite inférieure exponentielle pour le polytope vendeur ambulant , et l'intractable des procédures basées sur la résolution pour la satisfiabilité en raison des principes de trou de pige faible. Le "pourquoi" dans ce cas est qu'une certaine classe de problèmes NP-complets ne peut pas être résolue efficacement par des algorithmes reposant sur certains principes naturels (pour la classe de problèmes NP-complets considérés), comme les formulations de programmation linéaire pour TSP, ou basées sur la résolution méthodes de preuve pour SAT. Différents articles ont donné différentes raisons indépendantes pour lesquelles cela pourrait être utilisé pour prouver quelque chose, le dernier article sur TSP, par exemple, a cité un "lien étroit entre les reformulations de programmation semi-définies des LP et les protocoles de communication quantique à sens unique" comme raison, tandis que le dernier article sur la résolution cité deux raisons indépendantes, à savoir les limites inférieures "pour une classe de formules représentant le principe du pigeonnier et pour les formules générées aléatoirement".
  Vous pouvez également observer qu'il y a eu des tentatives de renforcer les résultats au fil du temps. Les résultats initiaux pour TSP ne concernaient que la formulation de programmation linéaire symétrique, tandis que les derniers résultats n'ont pas une telle restriction, et s'appliquent également aux problèmes de coupe maximale et d'ensemble stable maximal en plus du TSP. Les premiers résultats de la résolution ne considéraient que les procédures de résolution de Davis-Putnam de base et une seule classe de contre-exemples artificiels, tandis que les derniers résultats couvrent de grandes classes de méthodes basées sur la résolution et donnent plusieurs classes de contre-exemples naturels.
  Pour le TSP, je n'ai aucune idée de la façon dont les résultats devraient être renforcés, sauf peut-être en appliquant à plus de problèmes en plus du TSP, de la coupe maximale et de la stabilité maximale. Pour la résolution, j'aurais beaucoup d'idées sur la façon de renforcer les résultats, mais l'article auquel j'ai lié est de 2002, Stephen Cook et Phuong Nguyen ont publié une monographie Logical Foundations of Proof Complexity en 2010 que je n'ai même pas parcourue, et je Je suppose que cela couvrira déjà bon nombre de mes idées. Il est intéressant de noter le peu de différence que cela fait pour la plupart d'entre nous à quel point ces résultats ont été renforcés au fil du temps, malgré notre intérêt pour le P ≠ NPquestion. Même s'il aurait été prouvé entre-temps que les algorithmes reposant sur des systèmes logiques sans équivalent de la règle de coupure ne peuvent pas résoudre efficacement les problèmes de satisfiabilité, nous pensons toujours qu'il n'y a eu pratiquement aucun progrès sur P ≠ NP , que le problème est essentiellement toujours aussi largement ouvert.