¿Desrandomizando Valiant-Vazirani?

29

El teorema de Valiant-Vazirani dice que si hay un algoritmo de tiempo polinómico (determinista o aleatorio) para distinguir entre una fórmula SAT que tiene exactamente una asignación satisfactoria y una fórmula insatisfactoria, entonces NP = RP . Este teorema se demuestra mostrando que UNIQUE-SAT es NP- duro bajo reducciones aleatorias .

Sujeto a conjeturas plausibles de desrandomización, el Teorema puede fortalecerse a "una solución eficiente para UNIQUE-SAT implica NP = P ".

Mi primer instinto fue pensar que implicaba que existe una reducción determinista de 3SAT a UNIQUE-SAT, pero no me queda claro cómo esta reducción en particular puede ser aleatorizada.

Mi pregunta es: ¿qué se cree o se sabe acerca de las "reducciones de aleatorización"? ¿Es / debería ser posible? ¿Qué pasa en el caso de VV?

Dado que UNIQUE-SAT está completo para PromiseNP bajo reducciones aleatorias, ¿podemos usar una herramienta de desrandomización para mostrar que "una solución de tiempo polinomial determinista para UNIQUE-SAT implica que PromiseNP = PromiseP ?

cc.complexity-theory reductions derandomization unique-solution Henry Yuen
fuente
44
En cuanto al último párrafo, PromiseP = PromiseNP es equivalente a P = NP.
Tsuyoshi Ito

Respuestas:

31

Bajo los supuestos derandomization derecha (véase Klivans-van Melkebeek ) se obtiene el siguiente: Hay un polytime computable f ( φ ) = ( ψ 1 , ... , ψ k ) st para todos φ ,f(ϕ)=(ψ1,…,ψk)ϕ

  • Si ϕ es satisfactoria, entonces al menos uno de los ψ i tiene exactamente una asignación satisfactoria.ϕψi
  • Si ϕ no es satisfactoria, entonces todas las ψ i son insatisfactorias.ϕψi

Necesita k polinomio en la longitud de ϕ . Probablemente no se puede hacer para k = 1 .ϕk=1

Lance Fortnow
fuente
@LanceFortnow ¿ P = B P P implica que el lema de aislamiento vazirani-valiente se puede desrandomizar y, por lo tanto, P = B P P implica una reducción determinista a S A T que daría P = N P ? P=BPPP=BPPSATP=NP
T ....
1
No. Necesitas una suposición más fuerte que P = BPP para desrandomizar Valiant-Vazirani (de nuevo, te remito a Klivans-van Melkebeek). Incluso si desrandomiza Valiant-Vaizarni, esto solo da el resultado que mencioné anteriormente: no obtendría P = NP a menos que tuviera un algoritmo que pudiera resolver la satisfacción con testigos únicos.
Lance Fortnow
@LanceFortnow Solo para que quede claro. ¿Podemos obtener P ⊕ P = B P P ⊕ P con solo P = B P P o es esencial que (con el estado de conocimiento que tenemos) es probable que necesitemos desrandomizar VV para llegar a P ⊕ P = B P P ⊕ P (esta es una consulta un poco diferente a preguntar si solo si P = BPP da una reducción determinista SAT ya que puede no ser esencial que VV sea necesario en primer lugar para obtener NP en BPP ^ {oplus P }). P⊕P=BPP⊕PP=BPPP⊕P=BPP⊕P
T ....
22

Solo como referencia, me topé hoy con este artículo realmente interesante, que da evidencia de que una reducción determinista es poco probable:

Dell, H., Kabanets, V., Watanabe, O. y van Melkebeek, D. (2012). ¿Es mejorable el lema de aislamiento de Valiant-Vazirani? ECCC TR11-151

Argumentan que esto no es posible a menos que NP esté contenido en P / poli.

Henry Yuen
fuente