Problemy naturalne w

Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w U P ∩ c o U P ?$NP \cap coNP$$UP \cap coUP$

Oczywiście wielki każdy wie o w jest wersja decyzja faktoringu (czy n mają współczynnik wielkości co najwyżej k), ale to jest w rzeczywistości w U P ∩ c o U P .$NP \cap coNP$$UP \cap coUP$

Chociaż wiadomo, że gry parzystości są w obu przypadkach, twierdzi się, że stochastyczne gry parzystości nie są znane w UP przecinają koUP.

$L$$R^n$$\ell_2$$L$$t \in R^n$$t$

$\cap$$O(\sqrt{n})$

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

$\cup$$\cap$

$L$

$L$$\leq 1$

$L$$\leq C\sqrt{n}$$C > 0$

$\cap$$\cap$$\setminus$$\cap$$\setminus$$\neq$$\Pi$$L$$\Pi$

$\cap$