Problèmes entre P et NPC

128

La factorisation et l'isomorphisme des graphes sont des problèmes dans NP qui ne sont connus ni pour P ni pour NP-Complete. Quels autres problèmes naturels (suffisamment différents) partagent cette propriété? Les exemples artificiels directement issus de la démonstration du théorème de Ladner ne comptent pas.

Est-ce que l'un de ces exemples est un NP-intermédiaire prouvable, en supposant seulement une hypothèse "raisonnable"?

Lev Reyzin
la source
Une question similaire a été posée ici et pourrait être utile: cstheory.stackexchange.com/questions/52/…
Daniel Apon
1
Question connexe auprès de MO, avec plusieurs indications spécifiques pour les problèmes de NP et de co-NP, mais dont on ne sait pas qu'ils sont dans P: mathoverflow.net/questions/31821/…
András Salamon
1
Il existe plusieurs classes de complexité entre P et NP-complete qui sont actuellement considérées comme intéressantes: PPAD, problèmes équivalents à CGU, NP co-NP, BPP, ... Si vous demandez une grande liste, vous pourriez vous en faites un wiki de communauté s'il vous plaît?
András Salamon
Je vous remercie. Je suis conscient du théorème de Ladner. Je suppose que je demandais des "problèmes naturels". Je suppose que le PPAD a un équilibre de Nash, ce qui compte ...
Lev Reyzin

Réponses:

105

Voici une collection de certaines des réponses des problèmes entre P et NPC:

Lev Reyzin
la source
5
Oui, cette procédure fonctionne, en tant que réponse "officielle".
Suresh Venkat
12
Ce serait formidable de pouvoir ajouter une réponse à sa liste de suivi. Ce serait certainement sur le mien.
András Salamon le
9
Je supprime Planar MAX 2-SAT de la liste, Guibas et al. dans "Approximation de polygones et de subdivisions avec des chemins de liaison minimaux" ( springerlink.com/content/y234m35416w043v1 )
Bob Fraser
7
Certains de ces exemples sont-ils manifestement NP-intermédiaires, en supposant seulement une hypothèse "raisonnable" (c'est-à-dire, une hypothèse moins triviale que "ce problème est NP-intermédiaire")? Si tel est le cas, il serait intéressant de le mentionner dans cette liste.
Timothy Chow
3
@ Timothy Chow: L'exemple ci-dessus supposant que est manifestement intermédiaire, c'est-à-dire que si la version un problème complet avec , il est prouvé que ni complète par Mahaney ni celle de ne le contrediraient. . N E X P E X P N E X P N P P N E X P E X PNEXPEXPNEXPEXPNEXPNPPNEXPEXP
Joshua Grochow
45

Mon problème préféré dans cette classe (je vais le formuler comme un problème fonctionnel, mais il est facile de se transformer en un problème de décision de la manière standard): calculer la distance de rotation entre deux arbres binaires (de manière équivalente, la distance de retournement entre deux triangulations de un polygone convexe).

David Eppstein
la source
1
C'est un problème intéressant: je n'avais pas réalisé que c'était dans les limbes.
Suresh Venkat
3
Ouais je ne le savais pas non plus! Pour tous ces problèmes / réponses, je me demande s'ils sont dans les limbes parce que nous pensons qu'ils le sont vraiment ou s'ils ressemblent davantage à PRIMES ...
Lev Reyzin
Ce problème et son statut potentiellement intermédiaire devraient être mieux connus. Pouvez-vous donner une référence à cela? De plus, y a-t-il un résultat indiquant qu'il n'est pas NP-complet, comme il en existe pour l'isomorphisme de graphes et les problèmes connexes?
Joshua Grochow
8
Thurston, Sleator et Tarjan, "Distance de rotation, triangulations et géométrie hyperbolique", STOC'86 et JAMS'88, constituent une référence très jolie et importante, mais plus ancienne. Pour une référence récente qui mentionne explicitement la complexité du problème comme étant toujours ouverte, voir Lucas, " Amélioration de la
David Eppstein
1
Intéressant. Explorer l'espace de rotation est aussi un domaine de recherche actif semble-t-il. "Le graphe de rotation des arbres k-ary est hamiltonien", IPL 2008, dx.doi.org/10.1016/j.ipl.2008.09.013
Chad Brewbaker
38

Un problème qui n'est mentionné ni dans cette liste ni dans la liste de MO est le problème de la déviation. Avec un multiset de n (n-1) / 2 nombres, chaque nombre représentant la distance entre deux points de la ligne, reconstruit les positions des points d'origine.

Notez que ce qui est non négligeable, c’est que, pour un nombre donné d dans le multiset, vous ne savez pas quelle paire de points est séparée de d.

Bien qu'il soit connu que pour un cas donné, il n'y a qu'un nombre polynomial de solutions, on ne sait pas comment en trouver une!

Suresh Venkat
la source
Merci - c'est un bon! Cela me rappelle d'autres problèmes de "localisation". Est-il réellement pensé pour ne pas être en p?
Lev Reyzin
Je ne suis pas conscient du fait que le péage est directement lié aux problèmes de complexité connus. Cependant, il existe une relation de "mauvaise direction" à la factorisation, en ce sens que le problème de la déviation peut être défini comme un problème de factorisation sur un polynôme choisi de manière appropriée.
Suresh Venkat
1
Existe-t-il des conséquences improbables connues de ce problème étant NP-complet, comme il en existe pour l'isomorphisme de graphes (réduction du PH)?
Joshua Grochow
pas que je sache. cela n'a pas été beaucoup étudié, ce qui est dommage, car c'est tellement naturel.
Suresh Venkat
2
Vous rencontrez un problème similaire en bioinformatique: à partir d’un ensemble de sous-chaînes d’une chaîne potentiellement superposées et créées de manière aléatoire, beaucoup plus longues que les éléments individuels; calcule la chaîne d'origine. (séquençage de gènes)
Raphaël
38

Le problème de la somme des racines carrées: Soit deux suites et b 1 , b 2 , , b n d’entiers positifs, vaut A : = i a1,a2,,anb1,b2,,bn inférieur, égal ou supérieur àB:=iA:=iai ?B:=ibi

  • Le problème a un algorithme trivial en temps sur la RAM réelle - calculez simplement les sommes et comparez-les! - mais cela n'implique pas l'appartenance à P.O(n)

  • Il existe un algorithme évident de précision finie, mais on ne sait pas si un nombre polynomial de bits de précision est suffisant pour la correction. (Voir http://maven.smith.edu/~orourke/TOPP/P33.html pour plus de détails.)

  • Le théorème de Pythogorean implique que la longueur de toute courbe polygonale dont les sommets et les extrémités de nombre entier est une somme de racines carrées de nombres entiers. Ainsi, le problème de la somme des racines est inhérent à plusieurs problèmes de géométrie de calcul planaire, notamment les arbres à recouvrement minimaux euclidiens , les chemins les plus courts euclidiens , les triangulations de poids minimal et le problème du voyageur voyageur euclidien . (Le problème MST euclidien peut être résolu en temps polynomial sans résoudre le problème de la somme des racines, grâce à la structure matroïde sous-jacente et au fait que l'EMST est un sous-graphe de la triangulation de Delaunay.)

  • Il est un algorithme aléatoire polynomial, en raison de Johannes Blömer , de décider si les deux sommes sont égales. Cependant, si la réponse est non, l'algorithme de Blömer ne détermine pas quelle somme est la plus grande.

  • La version de décision de ce problème (Est-ce que ?) N'est même pas connue pour être en NP. Cependant, l'algorithme de Blömer implique que si le problème de décision est dans NP, il l'est aussi dans co-NP. Il est donc peu probable que le problème soit NP-complet.A>B

Jeffε
la source
3
Une belle, j'aime ça !!
Hsien-Chih Chang 張顯 之
Eh bien, si nous prenons seulement 1 000 nombres entiers aléatoires, pas trop grands, alors il y a environ façons de les diviser en deux ensembles, donc je m'attendrais à ce que deux de ces sommes se situent dans une plage de 900 bits ou plus (et dans la moitié) de la somme totale). D'autre part, trouver les "pires" deux séquences à comparer parmi ces 2 999 possibilités est également très difficile. 29992999
gnasher729
30

Voici une liste de problèmes qui peuvent ou non être qualifiés de "suffisamment" différents. Selon la même preuve que pour l’isomorphisme de graphe, si l’un d’eux est NP-complet, la hiérarchie polynomiale s’efface au deuxième niveau. Je ne pense pas qu'il y ait un large consensus sur lequel de ces "devrait" être dans P.

  • Automorphisme de graphique (détermine si un graphique a un automorphisme non trivial). Réduit pour représenter graphiquement l'isomorphisme, mais pas connu (pas pensé?) Pour être GI-difficile.
  • Isomorphisme et automorphisme de groupe (où les groupes sont donnés par leurs tables de multiplication). Encore une fois, réduit au graph isomorphisme, mais pas pensé pour être GI-difficile.
  • Isomorphisme en anneau et automorphisme. En un sens, c'est le grand-père de tous les problèmes ci-dessus, car la factorisation d'entiers équivaut à la recherche d'un automorphisme non trivial d'un anneau, et l'isomorphisme des graphes se réduit à l'isomorphisme des anneaux. Voir Neeraj Kayal, Nitin Saxena. Complexité des problèmes de morphisme en anneau. Complexité informatique 15 (4): 342-390 (2006). (Fait intéressant, déterminer si un anneau a un automorphisme non trivial se trouve dans )P
  • Cet article de Bill Gasarch contient quelques autres problèmes avec le goût de la théorie de Ramsey qui semblent pouvoir être intermédiaires.
  • D'après le théorème de Mahaney, aucun ensemble épars ne peut être NP-complet. Mais nous savons aussi qu'il ya des jeux rares dans - P ssi N E X P est pas égal à E X P . Donc , en supposant N E X P E X P , la version rembourrée de toute NNPPNEXPEXPNEXPEXP problème -complete est de complexité intermédiaire. (Un tel ensemble ne peut être en P que si N E X P = E X PNEXPPNEXP=EXP, contredisant notre hypothèse.) Il existe de nombreux problèmes naturels -complets.NEXP
Joshua Grochow
la source
J'aime le dernier exemple. Avez-vous des références à ce sujet?
Marcos Villagra
1
SR Mahaney. Ensembles complets clairsemés pour NP: Solution d'une conjecture de Berman et Hartmanis. Journal of Computer and System Sciences 25: 130-143. 1982. dx.doi.org/10.1016/0022-0000(82)90002-2 Ensembles clairsemés en NP - P siff NEXP neq EXP: J. Hartmanis, N. Immerman, V. Sewelson, ensembles éparses en NP-P: EXPTIME versus NEXPTIME, Information and Control, volume 65, numéros 2 à 3, mai-juin 1985, pages 158-181. dx.doi.org/10.1016/S0019-9958(85)80004-8
Joshua Grochow
C'est une belle liste, bien que les trois premiers soient assez similaires :) J'aime aussi le dernier exemple.
Lev Reyzin
28

Le problème de la taille de circuit minimale (MCSP) est mon problème "naturel" préféré dans NP dont on ne sait pas qu'il est NP-complet: étant donné la table de vérité (de taille n = 2 ^ m) d'une fonction booléenne f étant donné un nombre s, f a-t-il un circuit de taille s? Si MCSP est simple, il n’existe pas de fonction unidirectionnelle cryptographiquement sécurisée. Ce problème et ses variantes ont largement motivé l'étude des algorithmes de "force brute" en Russie, ce qui a conduit les travaux de Levin sur la complétude des NP. Ce problème peut également être considéré en termes de complexité de Kolmogorov liée aux ressources: demander si une chaîne peut être récupérée rapidement à partir d'une courte description. Cette version du problème a été étudiée par Ko; le nom MCSP a été utilisé en premier lieu par Cai et Kabanets, à ma connaissance. Plus de références peuvent être trouvées dans certains de mes articles: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf

Eric Allender
la source
24

Auto-dualité monotone

Pour toute fonction booléenne f=f(x1,x2,...,xn) , il est dual est fd=f¯(x1¯,x2¯,...,xn¯) . Compte tenu de f(x1,x2,...,xn)représenté par une formule CNF, nous devons décider si f=fd .

Ce problème est en co-NP [ log2n ], c’est-à-dire qu’il est décidable avec des étapes non déterministes O(log2n/loglogn) . Ainsi, il a un algorithme de temps quasi-polynomiale ( O(nlogn/loglogn) le temps), et il est donc peu susceptible d'être co-NP-dur.

Il est toujours possible de savoir si ce problème est dans P ou non. On trouvera plus de détails dans l'article de 2008 intitulé " Aspects informatiques de la dualisation monotone: un bref aperçu " de Thomas Eiter, Kazuhisa Makino et Georg Gottlob.

Danu
la source
23

Nœud trivialité: Étant donné une chaîne polygonale fermée dans l'espace à 3, est-il non noué (c'est-à-dire isotopique ambiante à un cercle plat)?

Ceci est connu pour être dans NP par profondeur des résultats dans la théorie des surfaces normales, mais aucun algorithme poly-temps ou preuve de dureté NP n'est connu.

Jeffε
la source
1
Il convient de mentionner que, comme pour beaucoup de problèmes potentiellement intermédiaires NP, une variante légère est connue pour être NP-complète. A savoir, le genre à trois variétés est NP-complet: étant donné une chaîne polygonale fermée dans une variété à 3 triangulé et un entier g, le noeud est-il la limite d'une surface de genre au plus g? (Être dénudé équivaut au genre 0.) doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016
Joshua Grochow
Il est également contenu dans co-AM (Hara, Tani, Yamamoto), donc pas de PNJ à moins que la hiérarchie polynomiale ne s'effondre.
Peter Shor
3
En fait, c'est toujours ouvert. Tasos Sidiropoulos a trouvé un bug dans la preuve Hara-Tani-Yamamoto.
Jeff E
coNPcoNP
19

On ne sait pas s'il est possible de décider en temps polynomial si le joueur 1 a une stratégie gagnante dans une partie à parité (à partir d'une position de départ donnée). Le problème est toutefois contenu dans NP et co-NP et même dans UP et co-UP.

Matthias
la source
Pouvez-vous donner une référence? Ça semble intéressant.
Joshua Grochow
1
M. Jurdzinski. Le choix du gagnant dans les jeux de parité est défini dans UP \ cap co-Up. Lettres de traitement de l'information 68 (3): 119-124. 1998. Devrait au moins être un bon point de départ.
Matthias
Le récent article "Un algorithme de pompage pour les jeux à gains stochastiques stochastiques ergodiques avec information parfaite" montre également que même une généralisation du jeu de parité peut être résolue en temps pseudo-polynomial. En particulier, ils montrent qu'un jeu appelé BWR game possède un algorithme temporel pseudo-polynomial lorsqu'il existe un nombre constant de "nœuds aléatoires". Le jeu de parité est le cas où il n'y a pas de nœuds aléatoires.
Danu
Il a été démontré récemment que les jeux de parité peuvent être résolus en temps quasi-polynomial, voir ici à titre d'exemple.
Thomas Klimpel
18

Vous avez une très longue liste de problèmes si vous êtes prêt à accepter des problèmes d’approximation, tels que l’approximation de Max-Cut dans un facteur de 0,878. Nous ne savons pas si c'est NP-difficile ou en P (connaissons seulement la dureté NP en supposant la conjecture de Uniuqe Games).

Moritz
la source
Oui, c’est un commentaire idiot que j’ai commencé à supprimer dès sa publication. Je vous remercie. :)
Daniel Apon
Merci! Mais je suppose que je ne pensais pas autant aux problèmes d'approximation qu'aux problèmes naturels.
Lev Reyzin
On peut soutenir que ce sont des problèmes naturels, car ils correspondent à ce qui est réalisable par un ensemble naturel de techniques, dans ce cas, une programmation semi-définie.
Moritz
J'imagine que le "naturel" est un critère vague ...
Lev Reyzin
18

Dans une formule CNF monotone, chaque clause ne contient que des littéraux positifs ou uniquement des littéraux négatifs. Dans un formule CNF monotone se croisant, chaque clause positive a une variable en commun avec chaque clause négative.

Le problème de la décision


f
f

no(log n)

  • Thomas Eiter et Georg Gottlob, Calcul transversal hypergraphique et problèmes connexes en logique et intelligence artificielle , JELIA 2002. doi: 10.1007 / 3-540-45757-7_53
András Salamon
la source
17

Une variété 3-triangulée donnée est-elle une 3-sphère? De Joe O'Rourke.

Peter Shor
la source
17

La version en cascade de Subset Sum (ou Egalité de sous-ensemble).

Donné:

akZ>0
k=0n1ak<2n1

S1,S2{1,,n}

jS1aj=kS2ak

Le problème de la somme des sous-groupes de casiers demande une telle solution. Initialement indiqué dans " Algorithmes d'approximation efficaces pour le problème SUBSET-SUMS EQUALITY" de Bazgan, Santha et Tuza.

utilisateur834
la source
16

Il y a beaucoup de problèmes liés à la recherche de sous-groupes cachés. Vous avez parlé de la factorisation, mais il y a aussi le problème de log discret, ainsi que d'autres liés aux courbes elliptiques, etc.

Joe Fitzsimons
la source
15

Voici un problème de choix social de calcul qui n'est pas connu pour être dans P, et qui peut ou non être NP-complet.

Contrôle de l'agenda pour les tournois équilibrés à élimination unique:

Tn=2ka

Question: existe-t-il une permutation des nœuds (une parenthèse ) de sorte que a soit le vainqueur du tournoi à élimination unique induit?

Pk2kVTVPk12k1i>0Pk[2i1]Pk[2i]eTPk1[i]=Pk[2i1]e=(Pk[2i1],Pk[2i])Pk1[i]=Pk[2i]PkTPk12kkPk1,,P02k

Contrôle de l'agenda pour les tournois équilibrés à élimination unique (formulation de graphique):

Tn=2ka

T2ka

2kxa2k1x2k1yxyk=0 , une arborescence binomiale n'est que la racine.) Les arborescences binomiales couvrantes d'un graphique de tournoi capturent exactement les tournois à élimination unique qui peuvent être joués, en fonction des informations sur le résultat du match figurant dans le graphique du tournoi.

Quelques références:

  1. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: Détermination des gagnants lors du vote à la majorité séquentielle. IJCAI 2007: 1372-1377.
  2. N. Hazon, PE Dunne, S. Kraus et M. Wooldridge. Comment truquer les élections et les compétitions. COMSOC 2008.
  3. Thuc Vu, Alon Altman, Yoav Shoham. Sur la complexité des problèmes de contrôle du calendrier pour les tournois à élimination directe. AAMAS (1) 2009: 225-232.
  4. V. Vassilevska Williams. Fixer un tournoi. AAAI 2010.
virgi
la source
13

Jetez un coup d'œil à la classe TFNP . Il a beaucoup de problèmes de recherche avec un statut intermédiaire.

Marcos Villagra
la source
NPcoNP
12

Le problème de l'isomorphisme de sous-graphe induit a des "restrictions de gauche" NP-incomplètes, en supposant que P n'est pas égal à NP. Voir Y. Chen, M. Thurley, M. Weyer: Comprendre la complexité des isomorphismes de sous-graphes induits , ICALP 2008.

Holger
la source
2
Bien que ce résultat soit intéressant, si vous vérifiez le document, il indique même que la preuve de la complexité intermédiaire est essentiellement la même que le théorème de Ladner, à la différence que vous faites la diagonalisation dans le choix de la restriction LHS. Donc, je ne sais pas si cela compte comme un problème "naturel", plutôt que comme un simple encodage du théorème de Ladner.
Joshua Grochow,
Notez également qu'il s'agit de restrictions source-et-cible. La cible (côté droit) doit être de forme spéciale pour imposer l'injectivité.
András Salamon
11

NPNP

Problème de bisection minimum: recherchez une partition de l'ensemble de nœuds en deux parties de taille égale, de manière à minimiser le nombre d'arêtes se croisant.

Karpinski, approximabilité du problème de bisection minimum: un défi algorithmique

Mohammad Al-Turkistany
la source
Avez-vous une référence à la définition du problème?
Lev Reyzin
La référence est ajoutée.
Mohammad Al-Turkistany Le
10

Le problème de stock de coupe avec un nombre constant de longueurs d'objet. Voir cette discussion pour plus d'informations.

Suresh Venkat
la source
10

nv1vβvβ>1

β=nNPcoNPNPPββ=no(1/loglogn)NP

MCH
la source
9

G=(V,E)fvVf(v)e=uvE|f(u)f(v)|f:V{0,1,2,,|E|}{1,2,...,|E|}

  1. JA Gallian. Une enquête dynamique sur l’étiquetage graphique. The Electronic Journal of Combinatorics, 2009.
  2. DS Johnson. La colonne NP-complétude: Un guide en cours. J. Algorithms, 4 (1): 87-100, 1983.
  3. DS Johnson. La colonne NP-complétude. ACM Transactions on Algorithms, 1 (1): 160–176, 2005.
Oleksandr Bondarenko
la source
9

PNPO(nlogn)NPNP

Mohammad Al-Turkistany
la source
LOGNPNP[log2n]
8

abax+1b

γ

Garey et Johnson dans leur séminal "Computers and Intractability" disent (pp. 158-159):

γRMM

RM={x,y:there is a string z such that on input x and guess z M has output y}

L1Σ1γL2Σ2L1γL2MxΣ1yΣ2x,yRMx,yRMxL1yL2MxxxL2xL1

Oleksandr Bondarenko
la source
γ
6

PNPO(nlogn)

Mohammad Al-Turkistany
la source
5

On pense que le problème suivant est NP-Intermédiaire, c’est-à-dire qu’il s’agit de NP mais pas de P ni de NP-complet.

Problème de racine polynomiale (EPRP)

p(x)deg(p)0GF(q)qr

p(x)=rx
p(x)rxrxr

deg(p)=0

Pour plus de détails, voir ma question et la discussion connexe .

Massimo Cafaro
la source
4

Je ne sais pas si le problème de l'isomorphisme hypergraphique pondéré proposé dans la réponse de Thinh D. Nguyen ne peut être simplement démontré qu'il est complet. Cependant, il existe un problème GI-difficile étroitement lié à l'IG, qui n'a pas encore été réduit à l'IG, à savoir le problème de l'isomorphisme de chaîne (également appelé problème d'isomorphisme de couleur ). C'est le problème que László Babai a montré que son époque était quasi polynomiale. Elle présente un intérêt indépendant, car elle équivaut à un certain nombre de problèmes de décision en théorie des groupes (permutation):

Thomas Klimpel
la source
3

Le problème de la recherche d’un arbre de Steiner minimal lorsque l’on promet que les sommets de Steiner tombent sur deux segments de droite se coupant à un angle de 120 ° est un problème qui n’est connu ni dans la PF ni dans le NP-dur. Si l'angle entre les segments de ligne est inférieur à 120 °, le problème est NP-difficile. On suppose que, lorsque l'angle est supérieur à 120 °, le problème se situe en PF.

Par conséquent, le problème de décision suivant semble être actuellement d'une complexité intermédiaire:


q
q

Bien sûr, cela peut en fait être en P ou être NP-complet, mais il semblerait alors que nous aurions une dichotomie intéressante à 120 ° au lieu d’un problème intermédiaire. (La conjecture peut aussi être fausse.)

  • JH Rubinstein, DA Thomas, NC Wormald, Steiner Arbres pour terminaux bornés à des courbes , SIAM J. Discrete Math. 10 (1) 1–17, 1997. doi: 10.1137 / S0895480192241190
András Salamon
la source
2

G1G2nπG1G2NP

utilisateur49753
la source