¿Problemas naturales en no en ?

¿Hay algún problema natural en que no se sabe (se sabe que se cree) en ?$NP \cap coNP$$UP \cap coUP$

Obviamente, el más grande que todos conocen en es la versión de decisión de factoring (no tiene un factor de tamaño como máximo k), pero eso es de hecho en .$NP \cap coNP$$UP \cap coUP$

Si bien se sabe que los juegos de paridad están en ambos, se ha afirmado que no se sabe que los juegos de paridad estocásticos se encuentren en UP intersect coUP.

Los problemas de celosía son una buena fuente de candidatos. Dada una base para una red en , se puede buscar un vector de red diferente de cero cuya norma ( ) sea lo más pequeña posible; Este es el 'problema de vector más corto' (SVP). Además, dada una base para y un punto , se puede pedir un vector reticular lo más cercano posible a ; Este es el 'problema de vector más cercano' (CVP).$L$$R^n$$\ell_2$$L$$t \in R^n$$t$

Ambos problemas son NP-difíciles de resolver exactamente. Aharonov y Regev mostraron que en (NP coNP), uno puede resolverlos dentro de un factor :$\cap$$O(\sqrt{n})$

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

He leído el documento, y no creo que haya indicios de su trabajo de que se pueda hacer esto en UP coUP, y mucho menos en UP coUP. $\cup$$\cap$

Un tecnicismo: como se dijo, estos son problemas de búsqueda, por lo que, estrictamente hablando, debemos tener cuidado con lo que queremos decir cuando decimos que están en una clase de complejidad. Usando una variante decisional del problema de aproximación, el problema de decisión del candidato que obtenemos es un problema prometedor : dada una red , distinga entre los dos casos siguientes:$L$

Caso I: tiene un vector distinto de cero de la norma ;$L$$\leq 1$

Caso II: no tiene un vector distinto de cero de la norma . (para alguna constante )$L$$\leq C\sqrt{n}$$C > 0$

Este problema está en Promise-NP Promise-coNP, y podría no estar en Promise-UP o Promise-coUP. Pero supongamos por el momento que no está en Promise-UP; Esto no parece dar un ejemplo de un problema en (NP coNP) UP. La dificultad proviene del hecho de que NP coNP es una clase semántica. (Por el contrario, si identificamos un problema en Promise-NP Promise-P, entonces podríamos concluir P NP. Esto se debe a que cualquier máquina NP que resuelva un problema de promesa también define un lenguaje NP que no es más fácil que .)$\cap$$\cap$$\setminus$$\cap$$\setminus$$\neq$$\Pi$$L$$\Pi$

Bajo los supuestos de desrandomización estándar, el isomorfismo gráfico está en NP co-NP.$\cap$