Problemas fuera de P que no son P-hard

Al leer una respuesta de Peter Shor y una pregunta anterior de Adam Crume, me di cuenta de que tengo algunas ideas erróneas sobre lo que significa ser $\mathsf{P}$ -hard.

Un problema es $\mathsf{P}$ -hard si cualquier problema en $\mathsf{P}$ es reducible con $\mathsf{L}$ (o si prefiere $\mathsf{NC}$ ) reducciones. Un problema está fuera de $\mathsf{P}$ si no existe un algoritmo de tiempo polinómico para resolverlo. Esto significa que debería haber un problema que esté fuera de $\mathsf{P}$ pero no sea $\mathsf{P}$ duro. Si suponemos que FACTORING está fuera de $\mathsf{P}$ , la respuesta de Peter Shor sugiere que FACTORING podría ser un problema.

¿Hay algún problema conocido (natural o artificial) que se sepa que está fuera de $\mathsf{P}$ pero no es $\mathsf{P}$ duro? ¿Qué pasa con los supuestos más débiles que el supuesto de factorización? ¿Hay un nombre para esta clase de complejidad?

cc.complexity-theory complexity-classes Artem Kaznatcheev
fuente

Respuestas:

Si $\mathsf{P} \neq \mathsf{L}$ entonces ningún conjunto disperso (incluso uno no computable) puede ser $\mathsf{P\text{-}hard}$ .

La idea errónea proviene de pensar en las clases de complejidad (y los problemas computacionales) como la creación de un orden lineal que no es cierto. El uso de la palabra "dureza" para un problema se puede utilizar para resolver otros problemas en la clase también contribuye a la idea errónea. Un límite inferior para un problema (es decir, no estar en una clase de complejidad) no implica que el problema sea difícil para la clase (es decir, puede usarse para resolver otros problemas en la clase). No sé si hay una mejor terminología alternativa para la "dureza" que se usa actualmente, una que se ha usado en décadas anteriores es la "universalidad" (que, en mi humilde opinión, expresó el concepto con mayor fidelidad, y entonces podríamos haber usado "dureza" por no estar en la clase, pero cambiar la terminología establecida es muy difícil).

Kaveh
fuente

Algunos de los diagramas de Euler que he visto de las clases de complejidad también me han alimentado la segunda idea errónea, que es lo que creo que causó mi confusión sobre la dureza X.

Artem Kaznatcheev

@Artem, sí, eso también es un factor. Esto es lo que hago en la clase: menciono la incomparabilidad de y bajo las reducciones , con la esperanza de que esto ayude a los estudiantes a evitar pensar que todo está ordenado linealmente.

\mod p

$\mod p$

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Kaveh

La parte del pedido total con la que tengo muchos menos problemas. En particular, creo que NP y coNP son lo suficientemente buenos como para mostrar que no debemos pensar en clases de complejidad que tengan un orden total.

Artem Kaznatcheev

@Artem, buen punto (aunque no podemos probar que sean diferentes). Creo que parte de la razón de la terminología es la falta de límites inferiores razonables, no tenemos un límite inferior bueno para SAT, pero creemos que es difícil de resolver porque es universal, pero la palabra "universal" no dar la misma sensación de dificultad que "difícil", especialmente a los no expertos. Pero eso crea el problema porque aunque uno puede argumentar que la universalidad de un problema implica que el problema es difícil de resolver, la dificultad de resolver un problema no implica que el problema sea universal.

Kaveh

es decir, los problemas universales son difíciles (al menos tan difíciles como cualquier problema en la clase), pero los problemas difíciles no necesitan ser universales.

Kaveh

Creo que puedes construir un conjunto que no esté en que no sea duro por un argumento de estilo Ladner. Aquí hay un ejemplo específico. $P$ $P$

En su artículo "Un enfoque uniforme para obtener conjuntos diagonales en clases de complejidad" (Theor. Comp. Sci. 18, 1982), Schöning demuestra lo siguiente:

Teorema Suponga que , , y son clases de complejidad presentables de forma recursiva y están cerradas bajo variaciones finitas. Luego hay un conjunto tal que , , y si y no es trivial (conjunto vacío o todas las cadenas), entonces es polytime many-one reducible a . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

Para aplicar este, conjunto para ser el conjunto vacío, y sea -Complete bajo reducciones polytime, establecer el conjunto de -Hard conjuntos que están en , establecidos . El conjunto vacío no puede ser -hard (la definición de -hardness para un lenguaje requiere que haya al menos una instancia en el lenguaje y una instancia no incluida). definitivamente no está en . El y el se pueden verificar para cumplir con las condiciones anteriores (similar a cómo lo hace Schoening para el $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ $C_2$ $NP$ -conjuntos completos; ver también esta pregunta relacionada ). Por lo que obtener una que no es un problema -Hard en , y que no está en . Pero debido a que y no es trivial, es reducible a un conjunto completo de , por lo que está en . Por lo tanto, en particular, tampoco puede ser duro. $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ $P$

En el argumento anterior, la restricción a problemas -Hard en es necesario garantizar presentabilidad recursiva, ya que los problemas P-duro como un todo son no recursivamente presentable y ni siquiera contable . Ahora, ejemplos "naturales" de esto son una historia diferente ... $P$ $EXP$

Ryan Williams
fuente

Me gusta cómo va esto a través incluso si . A menos que haya entendido mal algo.

L = P

$L = P$

Artem Kaznatcheev

@Artem: Si considera la dureza bajo la reducibilidad del espacio de registro, entonces cada lenguaje no trivial es L-hard. Por lo tanto, si L = P, no hay idiomas fuera de P que sean P-hard bajo la capacidad de reducción del espacio logarítmico.

Tsuyoshi Ito

Otra forma de generar problemas que están fuera de P pero que no son difíciles de P es tomar problemas completos para clases incomparables con P. Digamos que una clase X es incomparable con P, en el sentido de que ninguno es un subconjunto del otro. Entonces, un problema X-complete está necesariamente fuera de P (de lo contrario, P incluiría X) y no es P-hard (de lo contrario X incluiría P).

Traté de pensar en algunas clases incomparables con P, pero P es una clase bastante robusta, por lo que no hay demasiadas clases. Por ejemplo, RNC y QNC pueden ser incomparables con P. DSPACE ( ) también puede ser incomparable con P. PolyL es incomparable con P, pero no tiene problemas completos en las reducciones de espacio de registro. $\log^2$

Robin Kothari
fuente

En mi opinión, esta es casi la misma pregunta formulada de manera diferente, y no es necesariamente una forma de responderla. De hecho, el lenguaje A no está en P ni P-hard si y solo si la clase de lenguajes reducibles a A es incomparable con P (tome su noción favorita de reductibilidad). En lo que respecta a la pregunta actual, creo que es más probable que sea útil en la dirección opuesta; es decir, esta es otra forma de interpretar las respuestas a la pregunta actual.

Tsuyoshi Ito