¿Existen clases de complejidad sin problemas completos demostrables?

Question

Se dice que un problema es completo para una clase de complejidad $\mathcal{C}$ si a) está en $\mathcal{C}$ y b) cada problema en $\mathcal{C}$ es log-espacial reducible a él. Existen ejemplos naturales de problemas NP-completos (SAT), problemas P-completos (circuito-valor), problemas NL-completos (alcanzabilidad), etc.

Papadimitrou afirma que las clases de complejidad "semántica" como (creo) BPP tienen menos probabilidades de admitir problemas completos. Por otra parte, en realidad no sabemos si P = BPP o no, y si es así, habría problemas BPP-completos. (Existen problemas IP-completos, ya que IP=PSPACE, y determinar si una fórmula booleana cuantificada es satisfacible es PSPACE-completo).

Pregunta: ¿Existe alguna clase de complejidad natural que se pueda demostrar no tener problemas completos?

Creo que esta pregunta debe modificarse ligeramente, porque me imagino que $Time(n)$ no tiene problemas completos porque las reducciones log-espaciales pueden introducir un factor polinómico. Así que, en la palabra "natural", incluyo la suposición de que la clase de complejidad debe ser invariante bajo transformaciones polinómicas (no sé cómo precisar esto, pero espero que quede claro).

(Además, los límites temporales o espaciales deben ser como mínimo $\log n$ )

Edita: Un comentarista me ha señalado un resultado interesante de Sipser que $\mathrm{BPP}^M$ para $M$ un oráculo adecuado no tiene problemas completos. ¿Ocurre lo mismo con una clase (menos elegante) de la forma $\bigcup_f TIME(f)$ donde la unión es sobre una clase de funciones recursivas $f$ que están todos polinómicamente relacionados entre sí? (Lo mismo para $\bigcup_f NTIME(f)$ y lo mismo para el espacio.

Answer 1

He aquí una clase muy simple que es muy natural y no tiene problemas completos: ALL, la clase de todos los idiomas. La razón es que hay un número incontable de problemas en TODOS, pero sólo un número contable de máquinas de Turing (para reducciones), por lo que cada problema en TODOS no se puede reducir a un solo problema en TODOS.

Del mismo modo, cualquier clase con consejos, como P/poly, L/poly, BQP/qpoly, o incluso P/1 no tiene problemas completos (utilizando el mismo argumento).

Answer 2

Otra clase sin problemas completos con las reducciones logspace o polytime (no una unión de clases TIEMPO ( f ) para alguna familia de funciones polinómicamente afines f pero relativamente natural en mi opinión) es

ELEMENTAL \= TIEMPO (2 n ) ∪ TIEMPO (2 2 n ) ∪ TIEMPO (2 2 2 n ) ∪ TIEMPO (2 2 2 2 n ) ∪ ⋯

Si L eran ELEMENTAL -completo, entonces pertenecería a algún nivel de esta jerarquía, y todos los problemas anteriores podrían reducirse a él. Pero se sabe que esta jerarquía es propia (teorema de la jerarquía temporal), contradicción.

Answer 3

En zoo de clases de complejidad se extiende naturalmente al ámbito de teoría de la computabilidad y más allá, a teoría descriptiva de conjuntos y en estos reinos superiores hay numerosas clases naturales que no tienen miembros que estén completos, incluso con respecto a nociones de reducción mucho más generosas que la que usted menciona.

• Por ejemplo, consideremos la clase Dec de todos los conjuntos decidibles de números naturales. No puede haber ningún conjunto decidible $U$ tal que cualquier otro conjunto decidible $A$ se reduce a ella en un tiempo uniformemente acotado por cualquier función computable $f$ (incluso exponenciales iteradas, o la función de Ackerman, etc.). En particular, no tiene ningún miembro que sea completo en su sentido. Si hubiera tal miembro, entonces podríamos construir una enumeración computable $A_0$ , $A_1$ , $\ldots$ que contiene todos los conjuntos decidibles, lo cual es imposible ya que entonces podríamos diagonalizar contra él: el conjunto de $n$ tal que $n\notin A_n$ sería computable, pero no puede estar en la lista.

• La clase de todos los conjuntos definibles aritméticamente se obtiene cerrando los conjuntos decidibles (o mucho menos) bajo proyección de $\mathbb{N}^{n+1}\to \mathbb{N}^n$ y bajo combinaciones booleanas. Los miembros de esta clase son exactamente los conjuntos definidos por una fórmula de primer orden sobre la estructura $\langle\mathbb{N},+,\cdot,\lt\rangle$ y la jerarquía se estratifica según la complejidad de estas definiciones. Esta clase no tiene ningún miembro que sea completo con respecto a cualquier reducción computable, e incluso con respecto a cualquier reducción definible aritméticamente de complejidad acotada, ya que en este caso la jerarquía se colapsaría en algún nivel $\Sigma_n$ lo que se sabe que no ocurre.

• Un argumento similar funciona para la hiearquía hiperaritmética, que no puede tener ningún miembro universal reducciones hiperaritméticas de cualquier complejidad fija.

• Y análogamente para la hiearquía proyectiva sobre conjuntos de reales.

El fenómeno general es que existen numerosas jerarquías que crecen desde la teoría de la computabilidad hacia la teoría descriptiva de conjuntos, todas las cuales se sabe que exhiben un crecimiento estrictamente propio de tal manera que les impide tener miembros universales.

Answer 4

Esto es más un comentario que una respuesta, pero el comentario ir demasiado largo. De este hilo, parece que hay dos temas diferentes para llegar a clases sin problemas completos.

La integridad se define mediante dos propiedades. L es X-completo si
(1) L está en X
(2) L es X-difícil (bajo alguna noción adecuada de reducciones eficientes)

El primer tema se refiere a las clases que tienen problemas difíciles, pero si el problema difícil fuera un miembro de la propia clase, causaría problemas. Los ejemplos de POLYLOGSPACE y ELEMENTARY entran en esta categoría. Ambos tienen problemas difíciles, por supuesto, pero si el problema difícil fuera un miembro de la clase, se violaría algún teorema de jerarquía. (Teoremas de jerarquía espacial y de jerarquía temporal, respectivamente.) Del mismo modo, se nos podrían ocurrir más ejemplos de este tipo.

El segundo tema se refiere a las clases que no tienen problemas difíciles, como ALL o P/poly. Estas clases no tienen un problema completo por una razón fundamentalmente distinta a la del caso anterior.

Sería interesante ver si hay otras clases que no tienen problemas completos por razones completamente diferentes.

Answer 5

No estoy seguro de que sea del todo correcto, pero ahí va. Deje que $f(n)$ sea una función de complejidad adecuada (es decir, construible en el espacio y en el tiempo, etc.) y consideremos la clase $\mathcal{C} = \bigcup_{P,Q} \mathsf{DTIME} (Q(f(P(n))))$ donde $P,Q$ abarca polinomios con coeficientes de números naturales. Supongamos que $f(n) \geq n$ . Entonces la lengua $L=(M,x,P,Q)$ : $M$ es una máquina de Turing determinista que acepta la cadena $x$ en un máximo de $Q(f(P(n))$ pasos deben ser $\mathcal{C}$ -completa. De hecho, la verificación no es más que un proceso mecánico de simulación de la máquina de Turing (que puede hacerse en tiempo polinómico sobre la longitud de $M$ y $x$ ), y todo lenguaje decidido por una máquina de Turing $M$ en $\mathsf{DTIME}(Q(f(P(n)))$ debe reducirse a $L$ basado en la máquina $M$ . Lo mismo debería ocurrir con las clases de complejidad no deterministas.

He visto algo así para $\mathsf{NP}$ (así es como se demuestra el teorema de Cook-Levin, si no he entendido mal), y creo que debería generalizarse, y que las clases de complejidad natural basadas únicamente en una restricción temporal (que sea suficientemente grande) deberían admitir problemas completos.