Problèmes avec de grands écarts de complexité ouverts

32

Cette question concerne les problèmes pour lesquels il existe un grand écart de complexité ouvert entre la borne inférieure connue et la borne supérieure, mais pas en raison de problèmes ouverts sur les classes de complexité elles-mêmes.

Pour être plus précis, disons qu'un problème a des classes d'espaces A,B (avec AB , non défini de manière unique) si A est une classe maximale pour laquelle nous pouvons prouver qu'il est dur, et est une borne supérieure connue minimale , c'est-à-dire que nous avons un algorithme en résolvant le problème. Cela signifie que si nous finissons par découvrir que le problème est complet avec , cela n'aura pas d'impact sur la théorie de la complexité en général, par opposition à la recherche d'un algorithme pour un problème complet.B B C A C B P N PABBCACBPNP

Je ne suis pas intéressé par les problèmes avec et , car c'est déjà l'objet de cette question .B = N PAPB=NP

Je suis à la recherche d'exemples de problèmes avec les classes de lacunes qui sont autant que possible. Pour limiter la portée et préciser la question, je suis particulièrement intéressé par les problèmes avec et , ce qui signifie que l'appartenance à et -complétude sont cohérentes avec les connaissances actuelles, sans faire s'effondrer les classes connues (disons les classes de cette liste ).B E X P T I M E P E X P T I M EAPBEXPTIMEPEXPTIME

Denis
la source
Qu'entendez-vous par classes d'un problème? Supposons que le problème soit SAT, comment définissez-vous les classes?
RB
SAT est NP-complet, nous pouvons donc prendre et il n'y a pas d'espace ici, car la complexité de SAT correspond exactement à une classe déjà bien connue. Montrer tout nouveau résultat sur la complexité de la SAT (à savoir appartenir à une classe plus petite) serait une percée dans la théorie de la complexité. Certes, la question n'est pas complètement bien définie, car elle dépend des classes de complexité considérées comme «grand public», et A , B ne sont pas définies de manière unique. La question spécifique est cependant bien définie: exemples de langages pour lesquels il est cohérent avec les connaissances actuelles qu'ils sont en P ou EXPTIME-complet. A=B=NPA,B
Denis
en fait encore pas complètement bien défini à cause du "non-effondrement", donc il s'appuie sur une notion de "classe bien connue". De toute évidence, un problème PSPACE-complete ne correspond pas à l'exigence, bien qu'être en P ou EXPTIME-complete soit cohérent avec les connaissances actuelles. Par exemple, cette liste peut être utilisée comme référence pour ce qui est une classe «bien connue»: en.wikipedia.org/wiki/List_of_complexity_classes
Denis
13
Cela ne correspond pas tout à fait au projet de loi de votre question spécifique, mais selon toutes les apparences, la théorie existentielle des réels résiste obstinément à toute autre classification au-delà d'être NP-hard et au sein de PSPACE (ce dernier par 1988 résultat de JF Canny). en.wikipedia.org/wiki/Existential_theory_of_the_reals
anemone

Réponses:

28

Le problème d'équivalence de nœuds .

Étant donné deux nœuds tracés dans l'avion, sont-ils topologiquement les mêmes? Ce problème est connu pour être décidable, et il ne semble pas y avoir d'obstacles de complexité informatique à son existence en P. La meilleure borne supérieure actuellement connue sur sa complexité temporelle semble être une tour de s de hauteur c n , où c = 10 10 6 , et n est le nombre de croisements dans les diagrammes de nœuds. Cela vient d'une limite de Coward et Lackenby sur le nombre de mouvements Reidemeister nécessaires pour prendre un nœud à un équivalent. Voir l' article le plus récent de Lackenby2cnc=10106n pour quelques résultats connexes plus récents et pour la forme explicite de la borne que je donne ci-dessus (page 16).

Peter Shor
la source
Merci pour votre réponse. Connaissez-vous les limites actuelles? Pouvez-vous indiquer une référence indiquant l'état actuel de la technique? J'ai du mal à en trouver un clair.
Denis
J'ai essayé d'aller trouver quelque chose de plus récent que le papier de Hass, Lagarias et Pippenger de 1998 ici . Cela indique que le problème d'équivalence de nœuds est connu pour être décidable. Je ne serais pas surpris si quelqu'un avait montré que c'était dans EXPTIME depuis lors, mais je ne crois rien de mieux que cela est connu, et il n'est certainement pas clair que ce n'est pas en P. Je suis assez sûr qu'aucun des résultats montrant que décider si quelque chose est noué est dans NP s'étendent à ce problème plus général.
Peter Shor
Cette question MO est liée: mathoverflow.net/questions/77786/… En particulier, en utilisant les résultats récents annoncés par Lackenby dans people.maths.ox.ac.uk/lackenby/ekt11214.pdf , on obtient que pour tout type de nœud K, déterminer si un nœud donné est équivalent à K est dans NP (notez que cela n'améliore pas le problème d'équivalence de nœud)
Arnaud
@Arnaud: en fait, il me semble que ces résultats prouvent que pour deux diagrammes avec au plus n croisements, le problème d'équivalence de nœuds peut être résolu dans le temps au plus une tour de 2 de hauteur , où c est une constante énorme . Je devrais vérifier cela et modifier ma réponse. cnc
Peter Shor
@PeterShor Oui en effet. Je me concentrais sur le résultat le plus récent, car il peut conduire à une amélioration de la borne lors de sa publication, si le polynôme réel est explicité.
Arnaud
23

Voici une version du problème de taille de circuit minimum (MCSP): étant donné la table de vérité à bits d'une fonction booléenne, a-t-elle un circuit de taille au plus 2 n / 2 ?2n2n/2

Connu pour ne pas être dans . Contenu dans N P . On pense généralement qu'il s'agit de N P- dur, mais c'est ouvert. Je crois que ce n'est même pas connu pour être A C 0 [ 2 ] -hard. En effet, des travaux récents avec Cody Murray (à paraître dans CCC'15) montrent qu'il n'y a pas de réduction uniforme de NC0 de PARITY à MCSP.AC0NPNPAC0[2]

Ryan Williams
la source
23

La complexité du calcul d'un bit (spécifié en binaire) d'un nombre algébrique irrationnel (tel que ) a la borne supérieure la plus connue de P P P P P P P via une réduction du problème B i t S L P qui connaît cette borne supérieure[ABD14]. D'un autre côté, nous ne savons même pas si ce problème est plus difficile que de calculer la parité denbits - pour autant que nous sachions, ce problème pourrait être dansA C 0 . Notez cependant que nous savons qu'aucun automate fini ne peut calculer les bits d'un nombre algébrique irrationnel[AB07]2PPPPPPPBitSLPnAC0

SamiD
la source
21

Un autre problème topologique naturel, similaire dans son esprit à la réponse de Peter Shor, est l' intégration des complexes simpliciaux abstraits à 2 dimensions dans R3 . En général, il est naturel de se demander quand peut-on effectivement / efficacement décider qu'un complexe simplicial de dimension k abstraitek peut être intégré dans . Pour k = 1 et d = 2, c'est le problème de planarité du graphe et il a un algorithme de temps linéaire. Pour k = 2 et d = 2, il existe également un algorithme de temps linéaire . leRdk=1d=2k=2d=2 , d = 3 était ouvert jusqu'à l'année dernière, date à laquelle il a étédémontré qu'il était décidable par Matousek, Sedgwick, Tancer et Wagner. Ils disent que leur algorithme a unelimite de tempsrécursive primitive, maisplus grande qu'une tour d'exponentielles. D'un autre côté, ils spéculent qu'il pourrait être possible de mettre le problème en NP, mais aller au-delà serait difficile. Cependant, il ne semble pas y avoir de preuve solide qu'un algorithme de polytime est impossible.k=2d=3

Ce dernier article contient de nombreuses références pour une lecture plus approfondie.

Sasho Nikolov
la source
16

Les automates à compteurs multiples (MCA) sont des automates finis équipés de compteurs qui peuvent être incrémentés et décrémentés en une seule étape, mais ne prennent que des nombres entiers> = 0. Contrairement aux machines Minsky (alias automates de compteur), les MCA ne sont pas autorisés à tester si un compteur est égal à zéro.

L'un des problèmes algorithmiques avec une énorme lacune liée aux MSC est le problème d'accessibilité. Par exemple, si l'automate peut atteindre, à partir d'une configuration avec l'état initial et tous les compteurs zéro, une configuration avec un état acceptant, et tous les compteurs zéro à nouveau.

Le problème est difficile pour EXPTIME (comme l'a montré Richard Lipton en 1976), décidable (Ernst Mayr, 1981) et résoluble en Fω3 (merci, Sylvain, de l'avoir signalé). Un énorme écart.

Thomas S
la source
3
Salut Thomas, il y a une affirmation d'une limite supérieure de complexité explicite (et probablement pas serrée) dans un récent article arXiv: arxiv.org/abs/1503.00745 . La limite supérieure proposée dans est cependant bien au-delà des classes de complexité qui intéressaient l'affiche originale.Fω3
Sylvain
@Sylvain Cool! Merci de partager cela. :)
Michael Wehar
@Sylvain EXPTIME est-elle la borne inférieure la plus connue?
Michael Wehar
2
@Michael: la meilleure borne inférieure du problème de décision est en fait EXPSPACE (Lipton, 1976, cpsc.yale.edu/sites/default/files/files/tr63.pdf ). Cependant, l'algorithme de Mayr (1981, dx.doi.org/10.1145/800076.802477 ), Kosaraju (1982, dx.doi.org/10.1145/800070.802201 ) et Lambert (1992, dx.doi.org/10.1016/0304- 3975 (92) 90173-D ) analysé dans le papier arXiv mentionné est connu pour nécessiter au moins un temps ackermannien (c'est-à-dire ). Fω
Sylvain
@Sylvain Merci beaucoup pour toutes les informations supplémentaires. J'apprécie vraiment cela. :)
Michael Wehar
11

(Quantum Merlin-Arthur avec deux étalons non enchevêtrées): certainement Q M A -Hard, mais seulement connu pour être en N E X P . QMUNE(2)QMUNENEXP

Martin Schwarz
la source
9

EXPSPUNECEPP

Joshua Grochow
la source
Pouvez-vous fournir plus d'informations à ce sujet sous une forme explicite? ressemble à une sorte de problème bpp-complete?
@Arul: Neither PIT nor this problem is BPP-complete in any sense that I am aware of. (In fact, showing that BPP-complete problems exist is still open, and requires non-relativizing techniques - a result going back to Sipser.) However, derandomizing either has a hardness-randomness trade-off, in that their derandomization is essentially equivalent to lower bounds. Aside from the paper linked in the answer ("GCT 5"), lookup hardness-randomness and Kabanets-Impagliazzo.
Joshua Grochow
Je vais le faire mais j'étais intéressé par cette phrase «et en effet, son être en P est essentiellement équivalent à dérandomiser PIT» qui semble dire que PIT est une sorte de problème de proxy complet
@Arul: Oui, pour voir pourquoi PIT est un tel "problème de proxy complet", voir les choses que j'ai mentionnées dans mon commentaire précédent.
Joshua Grochow
pourquoi utilise-t-il «Dédié à Sri Ramakrishna» dans plusieurs de ses œuvres?
6

Le problème de Skolem (étant donné une récurrence linéaire avec des cas de base entiers et des coefficients entiers, atteint-il jamais la valeur 0) est connu pour être NP-difficile et n'est pas connu pour être décidable. Pour autant que je sache, quelque chose entre les deux serait conforme à nos connaissances actuelles sans effondrement des classes de complexité standard.

David Eppstein
la source