Естественные проблемы в

Существуют ли какие-либо естественные проблемы в , которых нет (как известно / считается, что они есть) в ?U P ∩ c o U $NP \cap coNP$$UP \cap coUP$

Очевидно, что большая часть, о которой все знают в - это вариант факторинга для решения (не имеет ли коэффициент размера не более k), но это на самом деле в .U P ∩ c o U $NP \cap coNP$$UP \cap coUP$

Хотя известно, что игры с проверкой на четность присутствуют в обеих, утверждается, что игры с проверкой на четность, как известно, не участвуют в UP Intersect CoUP.

Решетки проблемы являются хорошим источником кандидатов. Учитывая базис для решетки в , можно искать ненулевой вектор решетки, у которого ( ) норма наименьшая из возможных; это «проблема кратчайшего вектора» (SVP). Кроме того, учитывая базис для и точку , можно попросить вектор решетки как можно ближе к ; это «проблема ближайшего вектора» (CVP).R n ℓ 2 L t ∈ R n$L$$R^n$$\ell_2$$L$$t \in R^n$$t$

Обе проблемы NP-трудно решить точно. Ааронов и Регев показали, что в (NP coNP) их можно решить с точностью до :O ( $\cap$$O(\sqrt{n})$

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

Я прочитал газету, и я не думаю, что есть какой-то намек на их работу, что это можно сделать в UP coUP, не говоря уже о UP coUP. $\cup$$\cap$

Техническость: как уже говорилось, это проблемы поиска, поэтому строго говоря, мы должны быть осторожны с тем, что имеем в виду, когда говорим, что они в классе сложности. Используя вариант решения задачи аппроксимации, мы можем получить потенциальную проблему решения, которая является многообещающей : учитывая решетку , различают следующие два случая:$L$

Случай I: имеет ненулевой вектор нормы ;≤ $L$$\leq 1$

Случай II: не имеет ненулевого вектора нормы . (для некоторой константы )≤ C $L$ C>$\leq C\sqrt{n}$$C > 0$

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

$\cap$