Des problèmes naturels dans pas dans ?

26

Existe-t-il des problèmes naturels dans qui ne sont pas (connus pour être / pensés être) dans ? $NP \cap coNP$ $UP \cap coUP$

Évidemment, le grand que tout le monde connaît dans est la version décisionnelle de l'affacturage (n'a pas un facteur de taille au plus k), mais c'est en fait dans . $NP \cap coNP$ $UP \cap coUP$

cc.complexity-theory complexity-classes np Joshua Grochow
la source

Bien que techniquement, cela devrait être un wiki communautaire puisque je recherche une liste, je ne connais AUCUN de ces problèmes, donc je n'attends pas plus d'une réponse (et quand elle vient, elle mérite un certain crédit). S'il s'avère qu'il y a une litanie de tels problèmes, je le changerai en wiki communautaire.

Joshua Grochow

2

Veuillez définir UP ou donner un lien.

Emil

15

Bien que les jeux de parité soient connus pour être dans les deux, il a été affirmé que les jeux de parité stochastiques ne sont pas connus pour être dans la COUPE d'intersection UP.

Lev Reyzin
la source

J'accepte cela comme "la" réponse car c'est la seule qui n'implique pas de problèmes de promesse :). (Désolé Andy.) De plus, même si les répondeurs n'avaient aucun moyen de le savoir, c'est exactement ce que je cherchais car j'ai été inspiré de poser cette question après avoir lu cette réponse à une autre question: cstheory.stackexchange.com/questions/79/ … (Qui concernait les jeux de parité).

Joshua Grochow

13

Les problèmes de réseau sont une bonne source de candidats. Étant donné une base pour un réseau dans , on peut rechercher un vecteur réseau non nul dont la norme ( ) est la plus petite possible; c'est le «problème de vecteur le plus court» (SVP). Aussi, étant donné une base pour et un point , on peut demander un vecteur de réseau aussi proche que possible de ; c'est le «problème de vecteur le plus proche» (CVP). $L$ $R^n$ $\ell_2$ $L$ $t \in R^n$ $t$

Les deux problèmes sont difficiles à résoudre avec NP. Aharonov et Regev ont montré que dans (NP coNP), on peut les résoudre à l'intérieur d'un $\cap$ facteur: $O(\sqrt{n})$

http://portal.acm.org/citation.cfm?id=1089025

J'ai lu le document et je ne pense pas que leur travail laisse entendre que l'on peut faire cela dans UP coUP, sans parler de UP coUP. $\cup$ $\cap$

Une technicité: comme indiqué, ce sont des problèmes de recherche, donc à strictement parler, nous devons faire attention à ce que nous voulons dire lorsque nous disons qu'ils sont dans une classe de complexité. En utilisant une variante décisionnelle du problème d'approximation, le problème de décision candidat que nous obtenons est un problème de promesse : étant donné un réseau , distinguer les deux cas suivants: $L$

Cas I: a un vecteur non nul de norme ; $L$ $\leq 1$

Cas II: n'a pas de vecteur non nul de norme $L$ . (pour une constante) $\leq C\sqrt{n}$ $C > 0$

Ce problème se trouve dans Promise-NP Promise-coNP et peut ne pas être dans Promise-UP ou Promise-coUP. Mais supposons pour le moment que ce n'est pas dans Promise-UP; cela ne semble pas donner d'exemple de problème dans (NP coNP) UP. La difficulté vient du fait que NP coNP est une classe sémantique. (En revanche, si nous avons identifié un problème dans Promise-NP Promise-P, nous pourrions conclure P NP. En effet, toute machine NP résolvant un problème de promesse définit également un langage NP qui n'est pas plus facile que . ) $\cap$ $\cap$ $\setminus$ $\cap$ $\setminus$ $\neq$ $\Pi$ $L$ $\Pi$

Andy Drucker
la source

3

Très intéressant! Je pense cependant que la "technicité" des classes de promesses est très pertinente. Par exemple, Valiant-Vazirani montre que PromiseUP est NP-difficile sous des réductions aléatoires, mais je doute qu'une telle chose soit vraie pour UP. (En effet, si VV peut être dérandomisé et cela était vrai, alors nous aurions NP = UP. Bien sûr, il n'y a pas beaucoup de mauvaises conséquences connues de NP = UP, mais cela semble assez peu probable.)

Joshua Grochow

1

C'est un bon point, et je n'avais pas pensé à VV dans ces termes auparavant (comme parler de Promise-UP). Ici, par une réduction aléatoire pour promettre le problème

nous entendons des réductions aléatoires qui fonctionnent avec n'importe quel solveur pour

; nous ne pouvons pas insister pour que le solveur ne soit alimenté que des instances obéissant à la promesse

, car dans VV, nous attendons des instances avec des solutions non uniques.

Π

$\Pi$

Π

$\Pi$

Π

$\Pi$

Andy Drucker

7

Selon les hypothèses de dérandomisation standard, l'isomorphisme du graphe est en NP co-NP. $\cap$

Lance Fortnow
la source

3

Lance: avez-vous un pointeur sur la façon de montrer que GI n'est pas en UP ou pas en co-UP? Il n'est pas évident pour moi de montrer que l'IG ne peut pas être un espace de log réduit à l'IG limité à des graphes rigides (ceux sans automorphisme non trivial); il y a une simple réduction de Turing.

András Salamon

Je ne connais aucune conséquence intéressante du GI dans UP ou d'ailleurs GI dans P.

Lance Fortnow

@ AndrásSalamon: Je viens de remarquer votre commentaire (il y a quelques années). Je pense que je suis très lent aujourd'hui, mais je ne vois pas la "réduction de Turing simple" de GI à GI sur des graphiques rigides. Pourriez-vous élaborer?

Joshua Grochow

@JoshuaGrochow: Je ne suis pas sûr des détails maintenant, mais je pense que ce n'était qu'une référence à l'un des moyens standard de rigidifier les graphiques, par exemple en remplaçant chaque bord par un gadget approprié. Je ne pense pas que je voulais impliquer quoi que ce soit d'être efficace .

András Salamon

Des problèmes naturels dans pas dans ?

Réponses: