Completitud bajo las reducciones inyectables de Karp

La reducción de Karp es una reducción de tiempo polinómico computable de muchos entre dos problemas computacionales. Muchas reducciones de Karp son en realidad funciones uno a uno. Esto plantea la pregunta de si cada reducción de Karp es inyectiva (función uno a uno).

¿Existe un problema natural de completo que se sabe que está completo solo bajo la reducción de Karp de muchos y no se sabe que está completo bajo la reducción inyectable de Karp? ¿Qué ganamos (y perdemos) si definimos la completitud de usando la reducción inyectable de Karp? $NP$ $NP$

Una ganancia obvia es que los conjuntos dispersos no se pueden completar con reducciones inyectables de Karp.

cc.complexity-theory Mohammad Al-Turkistany
fuente

¿Por qué Karp utilizó muchas reducciones de tiempo polinomiales en lugar de reducciones uno a uno? ¿Estaba influenciado por las reducciones utilizadas en la teoría de la computabilidad?

Mohammad Al-Turkistany

Creo que ya he abordado esta pregunta (o una muy relacionada) en un comentario sobre esta respuesta: cstheory.stackexchange.com/a/172/129 .

Joshua Grochow

@JoshuaGrochow Injectivity nos da un límite inferior en la densidad de los conjuntos duros. ¿Conoce algún problema de NP completo que no se sabe que está completo bajo las reducciones inyectables de Karp? Por favor considere publicar su comentario como respuesta.

Mohammad Al-Turkistany

Respuestas:

$|f(x)|>|x|$ $f$

$NP$ $P\neq NP$

$NP$

$NP$ $p$ $P\neq NP$
$P\neq NP$

$P\neq NP$

Andras Farago
fuente

La inversa de una función de aumento de longitud es disminución de longitud . ¿O me estoy perdiendo algo?

Emil Jeřábek

Además, ¿el p-isomorfismo de los problemas NP-completos implica P! = NP por la trivial razón de que un lenguaje de un elemento no es isomorfo a un lenguaje de dos elementos, o es más sofisticado? Si permite idiomas finitos, el reclamo tiene una prueba directa simple, y solo necesita inyectividad: es decir, un lenguaje de un elemento es NP-complete bajo muchas reducciones si P = NP, pero no puede ser NP-complete bajo uno -Una reducción.

Emil Jeřábek

¿Por qué debemos insistir en reducciones inyectivas en su lugar? La inyectividad no parece estar relacionada de ninguna manera con el propósito de las reducciones, por lo que la elección natural es no exigirla. Hay muchas otras restricciones arbitrarias que uno podría imponer, pero ¿cuál sería el punto?

Emil Jeřábek

¿Por qué los conjuntos finitos no deberían ser NP-completos cuando P = NP? Tenga en cuenta que en esta situación, otros conjuntos tontos son NP completos incluso bajo reducciones uno a uno, como el conjunto de todos los números binarios impares.

Emil Jeřábek

@JoshuaGrochow No necesitamos obtener una reducción inv, li de la inversa para ocuparnos de la duración opuesta. Si tomamos dos lenguajes NP-completos, ambos tienen una reducción de Karp entre sí (pero estas reducciones generalmente no son inversas entre sí). Si ahora suponemos que cualquier reducción de Karp puede hacerse inv, li, entonces obtenemos una reducción inv, li en ambas direcciones, por lo que, según el teorema citado, pueden transformarse en un isomorfismo p.

Andras Farago

$\mathsf{NP}$ $\mathsf{NP}$

De hecho, incluso los posibles contraejemplos "antinaturales" de la Conjetura del isomorfismo - los conjuntos k-creativos del Teorema 2.2 de Joseph y Young - se completan bajo reducciones uno por uno por construcción.

[Repetido de mi comentario aquí :] Dado que la mayoría de las reducciones de muchos que construimos son, de hecho, reducciones de uno a uno, ¿por qué no las estudiamos cuando son formalmente más fuertes y las obtenemos la mayor parte del tiempo de todos modos? Creo que porque es más simple no tener que molestarse en probar la inyectividad, a pesar de que generalmente la tenemos. En ese sentido, tal vez las reducciones de muchos son una especie de "reducciones de Ricitos de Oro": la potencia correcta, la simplicidad de prueba correcta.

Joshua Grochow
fuente

¿Existe una explicación intuitiva de la creatividad del set?

Mohammad Al-Turkistany

Gracias por tu respuesta. Desearía poder aceptar dos respuestas.

Mohammad Al-Turkistany

En realidad, las reducciones inyectivas son útiles en criptografía. Suponga que tiene un sistema de prueba ZK para una relación NP R sobre el lenguaje L. Si desea construir una prueba ZK para otra relación NP R 'sobre un lenguaje L', debe encontrar dos funciones f y g con las siguientes propiedades : 1. x pertenece a L 'iff f (x) pertenece a L, 2. Si (x, w) pertenece a R' entonces (f (x), g (x, w)) pertenece a R. 3. Además , f y g tienen que ser eficientemente computables.

Las propiedades anteriores implican que si el sistema de prueba para R está completo y en buen estado, el sistema de prueba para R '(definido de manera obvia usando las funciones anteriores para reducir las instancias de una relación con el otro) también está completo y sólido.

¿Qué hay de probar que el nuevo sistema también es ZK o indistinguible por testigos (WI)? Si f es invertible, puede probar que el sistema de prueba así obtenido es ZK. De lo contrario, para demostrar que debe suponer que el sistema de prueba para R es una entrada auxiliar ZK (en lugar de solo ZK). Para WI, si f es invertible, puede probar que el sistema de prueba para R 'es WI. Sin el hecho de que f es invertible, no estoy seguro de si puedes probar que

Vincenzo IOVINO
fuente