Consecuencias de

Tengo parte de un intento de prueba de . El intento de prueba consiste en una reducción de Karp desde -complete problem 3-REGULAR VERTEX COVER a SAT. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P}$ $\oplus$

Dado un gráfico cúbico , la reducción genera una fórmula CNF que tiene las dos propiedades siguientes: $G$ $F$

$F$ tiene como máximo tarea satisfactoria. $1$
$F$ es satisfactoria si y solo si el número de cubiertas de vértices de es impar. $G$

Preguntas

¿Cuáles serían las consecuencias de ? Una consecuencia de la que ya estoy al tanto es la siguiente: sería reducible a través de una reducción aleatoria de dos lados. En otras palabras, tendríamos (usando el Teorema de Toda, que establece que , simplemente reemplazando con ). No sé si se ha demostrado que está contenido en algún nivel de la Jerarquía polinómica: en caso afirmativo, una consecuencia adicional sería que $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\mathbf{PH}$ $\mathbf{NP}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ $\oplus\mathbf{P}$ $\mathbf{NP}$ $\mathbf{BPP}^{\mathbf{NP}}$ $i$ $\mathbf{PH}$ colapsa a tal nivel . ~~Además, bajo supuestos de desrandomización ampliamente aceptados (~~ ~~), la Jerarquía polinómica se colapsaría entre el primer y el segundo nivel, ya que tendríamos~~ ~~(Me dijeron que esto no es cierto, sin embargo, no borraré esta línea hasta que comprenda por qué).~~ $i$ ~~$\mathbf{BPP} = \mathbf{P}$ $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$~~

Si no me equivoco, la reducción antes mencionada en realidad resultaría más que . Sería . ¿Cuáles serían las consecuencias de , además de las que ya implica ? No sé exactamente si agregaría más sorpresa a las consecuencias ya sorprendentes de , ni en qué medida. Intuitivamente, supongo que sí, y en gran medida. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$

cc.complexity-theory graph-theory complexity-classes sat counting-complexity Giorgio Camerani
fuente

\oplus P

$\oplus\mathrm P$ está cerrado bajo complemento, y la reducción aleatoria de PH a es múltiple, por lo tanto, realidad implica , y . UP no hace mucha diferencia (cf. la falta de algo útil en cstheory.stackexchange.com/questions/3887 ).

\oplus P

$\oplus\mathrm P$

\oplus P \subseteq N P

$\oplus\mathrm P\subseteq\mathrm{NP}$

P H = Σ_{2}^{P} = Π_{2}^{P} = A M \cap c o A M

$\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$

P H \subseteq N P / p o l y \cap c o N P / p o l y

$\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$

Emil Jeřábek

@ EmilJeřábek Gracias por su interesante comentario, no sabía que consecuencias. Yo sabía que la pregunta que señaló que lo haga, sin embargo, lo que habría esperado

(así como

) a ser sorprendente, al menos, porque

no se sabe que tiene problemas completos. Es interesante cómo se sabe que algo ampliamente conjeturado como falso (

) tiene, si es cierto, alguna consecuencia impactante. Podría considerar expandir su comentario en una respuesta ...

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

U P

$\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

Giorgio Camerani

No, estás completamente equivocado. BPP = P solo dice que cada lenguaje computable por una máquina BPP también es computable por una máquina P. No dice nada sobre los lenguajes que son computables por una máquina BPP con un oráculo no trivial. Por su argumento defectuoso, NP = P implica

para cada

, que sabemos que es falso, por lo tanto,

está resuelto. Y para el caso, su argumento implicaría

, ya que existen oráculos

para los cuales

{N P}^{A} = P^{A}

$\mathrm{NP}^A=\mathrm P^A$

A

$A$

N P \neq P

$\mathrm{NP}\ne\mathrm P$

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$

A

$A$

{B P P}^{A} \neq P^{A}

$\mathrm{BPP}^A\ne\mathrm P^A$ .

Emil Jeřábek

@Giorgio: Él solo afirma que la línea de razonamiento que consideró no funciona en esta circunstancia. Parte relevante: "Si la máquina a la que adjunto el oráculo es al menos igual de potente, ¿por qué no debería seguir la inclusión?". No parece decir que el reclamo en sí mismo es falso; solo que tu intuición particular no funciona. Todavía no podemos descartar que los aspectos probabilísticos del PPTM no puedan obtener más beneficios de ese oráculo. El TM probabilístico tiene más herramientas a su disposición, pero la herramienta puede no proporcionar un beneficio estricto sin otras adicionales (como el oráculo NP).

mdxn

Incluso con la suposición de que existe un PRNG lo suficientemente fuerte como para colapsar P y BPP, no veo por qué esto necesariamente debe implicar BPP con un oráculo NP y P con un oráculo NP debe ser el mismo. Normalmente, los PRNG tienen la garantía de que ningún circuito polisize puede distinguir su salida de bits verdaderamente aleatorios. Pero para las máquinas Oracle necesita la garantía para cada circuito de polisización con puertas NP permitidas, y esto es más fuerte. Impagliazzo-Wigderson se relativiza, pero necesita fortalecer la suposición de dureza ( eccc.hpi-web.de/report/1998/055/comment/1/download )

Sasho Nikolov

Consecuencias de

Respuestas: