Problemas naturais em

Existem problemas naturais no que não são (se sabe / são) no ?U P ∩ C o U $NP \cap coNP$$UP \cap coUP$

Obviamente, o grande problema que todos conhecem no é a versão de decisão do fatoração (não tem um fator de tamanho no máximo k), mas isso é de fato no .U P ∩ C o U $NP \cap coNP$$UP \cap coUP$

Embora os jogos de paridade sejam conhecidos por ambos, foi alegado que os jogos de paridade estocásticos não são conhecidos por estarem no grupo de interseção UP.

Os problemas de treliça são uma boa fonte de candidatos. Dada a base para uma rede em R n , pode-se procurar um vetor de rede diferente de zero cuja norma ( ℓ 2 ) seja a menor possível; este é o "Problema de vetor mais curto" (SVP). Além disso, dada uma base para L e um ponto t ∈ R n , pode-se solicitar um vetor de treliça o mais próximo possível de t ; este é o 'Problema vetorial mais próximo' (CVP).$L$$R^n$$\ell_2$$L$$t \in R^n$$t$

Ambos os problemas são difíceis de resolver exatamente. Aharonov e Regev mostraram que em (NP coNP), pode-se resolvê-los dentro de um O ( $\cap$fator:$O(\sqrt{n})$

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

Eu li o papel, e eu não acho que há qualquer indício de seu trabalho que se pode fazer isso em UP golpe, muito menos UP ∩ golpe. $\cup$$\cap$

Um tecnicismo: como afirmado, esses são problemas de pesquisa; portanto, estritamente falando, precisamos ter cuidado com o que queremos dizer quando dizemos que eles estão em uma classe de complexidade. Usando uma variante decisional do problema de aproximação, o problema de decisão do candidato que obtemos é um problema promissor : dada uma rede , faça uma distinção entre os dois casos a seguir:$L$

Caso I: tem um vetor diferente de zero da norma ≤ 1 ;$L$$\leq 1$

Caso II: não possui vetor diferente de zero da norma ≤ C $L$ . (para alguma constanteC>0)$\leq C\sqrt{n}$$C > 0$

Esse problema está no Promise-NP Promise-coNP e pode não estar no Promise-UP ou no Promise-coUP. Mas suponha, no momento, que não esteja no Promise-UP; isso não parece fornecer um exemplo de problema em (NP ∩ coNP) ∖ UP. A dificuldade decorre do fato de NP ∩ coNP ser uma classe semântica. (Em contraste, se identificou um problema em Promise-NP ∖ Promise-P, então podemos concluir P ≠ NP. Isso ocorre porque qualquer máquina NP resolver um problema promessa Π também define uma linguagem NP L que não é mais fácil do que Π . )$\cap$$\cap$$\setminus$$\cap$$\setminus$$\neq$$\Pi$$L$$\Pi$

Sob as premissas padrão de des aleatorização, o isomorfismo gráfico está em NP co-NP.$\cap$