¿Está bien definida la relativización?

Según BGS teorema [1], no es un oráculo de tal manera que . $A$ $P^A\neq NP^A$

Si la operación de relativización fuera una función bien definida, uno esperaría que de se pudiera concluir que , por ejemplo, seguiría de BGS. Sin embargo, todavía está abierto. $B\mapsto B^A$ $B^A\neq C^A$ $B\neq C$ $P\neq NP$ $P\neq NP$

¿Eso significa que la relativización no es una función bien definida?

Si es así, ¿tenemos algún ejemplo de dos relativizaciones probablemente diferentes de la misma clase de complejidad?

[1] TP Baker, J. Gill y R. Solovay, "Relativizaciones de la pregunta P =? NP"

cc.complexity-theory oracles relativization Miguel
fuente

Baker-Gill-Solovay muestra dos oráculos: uno donde P y NP son iguales y otro donde no lo son. Eso responde a tu última pregunta.

Suresh Venkat

@SureshVenkat: si quiere decir que hay oráculos

modo que

entonces este resultado (¿teorema de Ladner?) Es en realidad el trasfondo de mi pregunta. Puedo ver por qué

no implica

, pero no ver por qué

no implica

A, B

$A,B$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P^{B} = N P^{B}

$P^B=NP^B$

P^{B} = N P^{B}

$P^B=NP^B$

P = N P

$P=NP$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P \neq N P

$P\neq NP$

Michael

@Kaveh sería útil para señalar respuestas específicas. Hice un escaneo rápido de las preguntas y no vi nada.

Suresh Venkat

PD: la respuesta corta a su pregunta es que una relativización no es un operador extensional / funcional en la clase de problemas, incluso si la notación parece implicar lo contrario. No existe una definición general de relativización para las clases problemáticas, las relativizaciones se definen para modelos de máquina y un solo modelo de máquina puede tener varias versiones relativizadas diferentes.

Kaveh

FYI Fortnow notas / admite en su abstracta que teóricos de la complejidad tanto de uso y "mal uso" relativización .... parece ser un área gris es cierto de la teoría de la complejidad , a veces ....

VZN

Respuestas:

Tienes toda la razón. La operación de relativización no está bien definida. P y P ^A son objetos definidos independientemente. Los nombres son sugerentes, pero no puede definir formalmente P ^A del conjunto P. (Puede definir P de P ^A configurando A para que sea el conjunto vacío). $B\mapsto B^A$

Piense en P ^A como una especie de generalización de P, que equivale a P cuando A está vacío, pero de lo contrario puede ser diferente. Ahora bien, si sólo se conoce el conjunto P, no está claro cómo generalizar esto para obtener P ^A . Como analogía, si le pido que generalice los números reales, no está claro qué generalización estoy buscando. ¿Estoy pensando en campos, anillos, espacios vectoriales, etc.? La razón por la que esto sucede es que, si bien P es simplemente un conjunto de lenguajes, P ^A se define en términos de una máquina. Esta máquina tiene la propiedad de que cuando A está vacío, decide exactamente los mismos idiomas que P. Puede encontrar alguna otra máquina, llamémosla Q ^A , que también tiene la propiedad de que cuando A está vacío, decide los mismos idiomas que P Esto no significa que P^A = Q ^A para todos los A. Esto sería análogo a afirmar que si f (0) = g (0), entonces f y g son la misma función.

Quizás esta publicación de Terence Tao sea útil.

Robin Kothari
fuente

Gracias Robin. Esa es otra buena respuesta, y el enlace al artículo de Tao es muy útil.

Suresh Venkat

(Asumo que esta pregunta eventualmente se migrará a CS.SE, pero estoy publicando mi respuesta aquí en cstheory por ahora).

Técnicamente, uno no suele pensar en la relativización como un "operador" o "función"; sin embargo, no veo una razón por la que no pueda tomar una declaración y asignar la declaración a una versión relativizada de la misma.

El truco es que, como han dicho otros, la relativización no está realmente definida sobre una clase de complejidad; en cambio, se define en el modelo de cálculo que está utilizando. Además, lo que relativiza es la declaración, no las clases. (La notación es un poco engañosa).

Un ejemplo de esto es que teóricamente podría decir que una declaración se relativiza (o, lo que es menos probable, no se relativiza) incluso si no se refiere a una máquina de Turing. Por ejemplo, podría decir (sinceramente), "1 + 1 = 2" se relativiza, porque en relación con cada oráculo que podría agregarse a la definición de mi máquina universal de Turing, 1 + 1 = 2 seguiría siendo cierto.

Entonces la respuesta corta es: Sí, está bien definido, pero no en las clases.

Philip White
fuente

P^{A} \neq N P^{A}

$P^A \ne NP^A$

P = N P

$P = NP$

A

$A$

A eso me refería en mi respuesta ... Dije que no se puede relativizar sobre las clases, se relativiza sobre las declaraciones. La capacidad de relativizar sobre P y NP desaparece si no puedes relativizar sobre clases individualmente; el argumento no funciona si solo digo "Relativicé una declaración, ahora invierto la relativización y aún debería contener" más de lo que es posible decir (usando la función f (x) = x ^ 2 como ejemplo) " 5 ^ 2 es compuesto "->" 5 es compuesto ".

Philip White

No existe una definición general de relativización de declaraciones. Solo hay modelos relativizados de computación. La relativización de P vs. NP supone que hemos arreglado los modelos relativizados de P y NP de antemano.

Kaveh