Candidat naturel contre la conjecture d'isomorphisme?

18

La célèbre conjecture d'isomorphisme de Berman et Hartmanis dit que tous langages complets sont isomorphes en temps polynomiaux (p-isomorphes) les uns aux autres. La signification clé de la conjecture est qu'elle implique . Il a été publié en 1977, et une preuve à l'appui était que tous problèmes de complets connus à l'époque étaient en effet p-isomorphes. En fait, ils étaient tous rembourrables , ce qui est une belle propriété naturelle et implique le p-isomorphisme de manière non triviale.P ≠ N P N PNPP≠NPNP

Depuis lors, la confiance dans la conjecture s'est détériorée, car des langages candidats NP complets ont été découverts qui ne sont pas susceptibles d'être p-isomorphes à SUNET , bien que le problème soit toujours ouvert. Pour autant que je sache, aucun de ces candidats ne représente des problèmes naturels ; ils sont construits par diagonalisation dans le but de réfuter la conjecture d'isomorphisme.

Est-il toujours vrai, après près de quatre décennies, que tous les problèmes naturels connus de NP complétés sont p-isomorphes à SUNET ? Ou, existe-t-il un candidat naturel conjecturé contraire?

cc.complexity-theory complexity-classes p-vs-np np-complete Andras Farago
la source
2
Je m'abstiendrai de voter, mais je suis personnellement contre toutes les questions qui demandent l'existence de quelque chose de "naturel" sans définir ce qui est naturel. Je ne dis pas que je suis contre toutes les notions "floues", mais je pense que le naturel est trop large et une propriété souhaitable / indésirable plus concrète devrait être précisée davantage.
Sasho Nikolov
2
+1 Belle question. @SashoNikolov, avant l'invention des machines de Turing, la définition formelle des algorithmes, la notion intuitive était connue et utilisée depuis des milliers d'années. L'absence de définition formelle du problème naturel ne devrait pas nous dissuader de l'utiliser de manière informelle. Le problème naturel est un concept que vous connaissez quand vous le voyez.
Mohammad Al-Turkistany
4
Je suis d'accord avec Mohammad que vous connaissez généralement un problème naturel lorsque vous le voyez. Cependant, «naturel» dépend également du contexte, et dans certains contextes, il existe une notion plus claire - ou peut-être simplement un ensemble plus large et plus largement accepté d'exemples clairement naturels - que dans d'autres. Je pense que ce cas particulier (NP-complet) relève de l'ancienne classe. Par exemple, l'application d'une fonction unidirectionnelle à SAT pour obtenir un autre problème NP-complet (l'idée de base derrière certains des candidats violant Berman-Hartmanis) entraîne clairement un problème "contre nature".
Joshua Grochow
4
Le problème avec «naturel» dans la pratique ici sur cstheory.SE est que la question se traduit généralement par une tempête «pas de véritable écossais» où chaque réponse que le PO n'aime pas est considérée comme «contre nature» pour un ensemble évolutif / changeant de raisons.
Suresh Venkat
6
@Sasho, j'ai personnellement lu "naturel" sans autre précision comme signifiant: ce n'est pas un problème artificiel pour répondre à la question (ou similaire), les gens sont intéressés par le problème indépendamment.
Kaveh

Réponses:

17

Je pense que la réponse est oui, même aujourd'hui, il n'y a pas de problème naturel connu qui est un candidat pour violer la conjecture d'isomorphisme.

La raison principale est que les problèmes typiquement NP-complets naturels sont très facilement considérés comme pouvant être remplis, ce que Berman et Hartmanis ont montré être suffisants pour être isomorphes à SAT. Pour les problèmes naturels liés aux graphes, cela implique généralement l'ajout de sommets supplémentaires qui sont, par exemple, déconnectés du graphe ou connectés d'une manière très particulière (mais généralement évidente). Pour la version de décision des problèmes d'optimisation, cela implique généralement l'ajout de nouvelles variables factices sans aucune contrainte. Etc.

Joshua Grochow
la source
1
Oui, dans la plupart des problèmes graphiques, le remplissage est facile. Mais cela ne tient pas toujours. Un exemple: est-il vrai que le graphe est sans triangle et a un chemin hamiltonien? Ici, pour préserver la propriété, un nouveau sommet de remplissage doit se connecter à un ancien (pour permettre un chemin hamiltonien), il doit se connecter à un ensemble indépendant (pour éviter de créer un triangle), et cet ensemble indépendant doit être tel qu'il contient un point d'extrémité d'au moins un chemin hamiltonien (pour le rendre extensible au nouveau sommet). Il ne me semble pas évident comment y parvenir. Bien sûr, on pourrait trouver un autre moyen de rembourrer, je ne suis pas sûr.
Andras Farago
4
Pour Hamiltonian Path, voir l'article original de Berman-Hartmanis (Thm 7 (5) dans la version STOC, Thm 8 (5) dans la version journal: dx.doi.org/10.1137/0206023 ). Leur construction n'introduit aucun nouveau 3 cycles dirigés. Si vous voulez éviter même les triangles non orientés , vous pouvez subdiviser certaines des arêtes dans leur construction avec de nouveaux sommets. Vous pourriez également trouver leur article de suivi intéressant, dans lequel ils montrent que les équations diophantiennes quadratiques sont p-iso à SAT: dx.doi.org/10.1016/0022-0000(78)90027-2
Joshua Grochow
1
@JoshuaGrochow Existe-t-il un exemple non naturel candidat contre la conjecture BH?
T ....
2
@Turbo: Oui, les ensembles k-creative ("ensembles complets chiffrés") de Joseph et Young 1985: dx.doi.org/10.1016/0304-3975(85)90140-9
Joshua Grochow