Clases de complejidad para casos distintos al "peor caso"

10

¿Tenemos clases de complejidad con respecto a, digamos, la complejidad del caso promedio? Por ejemplo, ¿hay una clase de complejidad (con nombre) para los problemas que toman el tiempo polinómico esperado para decidir?

Otra pregunta considera la mejor complejidad del caso , ejemplificada a continuación:

¿Existe una clase de problemas (naturales) cuya decisión requiera al menos un tiempo exponencial?

Para aclarar, considerar algunos EXP lenguaje -Complete . Obviamente, no todas las instancias de requieren tiempo exponencial: hay instancias que se pueden decidir incluso en tiempo polinómico. Entonces, la mejor complejidad de caso de no es el tiempo exponencial. $L$ $L$ $L$

EDITAR: Dado que surgieron varias ambigüedades, quiero intentar aclararlo aún más. Por "mejor de los casos", me refiero a una clase de complejidad cuya complejidad de problemas está limitada por alguna función. Por ejemplo, defina BestE como la clase de lenguajes que no puede decidirse en el tiempo por debajo de un exponencial lineal. Simbólicamente, dejar que denota una máquina arbitraria Turing, y , , y ser números naturales: $M$ $c$ $n_0$ $n$

$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

donde denota los tiempos que toma antes de que detenga en la entrada . $T(M(x))$ $M$ $x$

Acepto que definir esa clase de problemas es muy extraño, ya que estamos exigiendo que cada máquina de Turing , independientemente de su poder, no pueda decidir el lenguaje a tiempo menos que un exponencial lineal. $M$

Sin embargo, observe que la contraparte del tiempo polinomial ( BestP ) es natural, ya que cada máquina de Turing requiere tiempoal menos leer su entrada. $|x|$

PD: Tal vez, en lugar de cuantificar como "para todas las máquinas Turing ", tenemos que limitarlo a alguna clase de máquinas Turing previamente especificadas, como las máquinas Turing de tiempo polinómico. De esa manera, podemos definir clases como , que es la clase de lenguajes que requieren al menos tiempo cuadrático para decidirse en máquinas de Turing de tiempo polinómico. $M$ $\mathbf{Best(n^2)}$

PS2: También se puede considerar la contraparte de complejidad de circuito, en la que consideramos el menor tamaño / profundidad de circuito para decidir un idioma.

cc.complexity-theory complexity-classes MS Dousti
fuente

El hecho de que haya casos de SAT que sean fáciles, no significa que su tiempo esperado sea polinómico. No estoy seguro de entender tu pregunta ...

Lev Reyzin

@Lev Reyzin: No quise decir que SAT está en el tiempo polivinílico esperado. Es decir, dado que SAT tiene instancias fáciles, no podemos decir que su complejidad de "mejor caso" sea difícil.

MS Dousti

¡Ah, ya veo, la complejidad del caso promedio y la mejor complejidad del caso son dos preguntas separadas! De alguna manera me perdí esto en mi primera lectura, mi error.

Lev Reyzin

No puedo analizar tu definición de BestE. M y x están sentados fuera de su cuantificación ... además, ¿no quieres que rechace las entradas que no están en ?

M

$M$

L

$L$

Ryan Williams

@ Ryan: Gracias por señalar la falla. Lo corregí

MS Dousti

13

Aunque no puedo analizar tus definiciones, debes saber que se conocen jerarquías de tiempo mucho más fuertes, en particular las jerarquías de tiempo "en casi todas partes".

Aquí está la afirmación formal: por cada vez que está vinculado , existe un lenguaje con la propiedad de que cada algoritmo determinista que reconoce correctamente debe ejecutarse en el tiempo asintóticamente mayor que en todas las entradas menos finitas, durante un tiempo suficientemente pequeño . $T(n)$ $L \in TIME[T(n)]$ $L$ $t(n)$ $t(n)$

"Suficientemente pequeño" significa . $t(n) \log t(n) \leq o(T(n))$

Supongamos que elegimos para un ejemplo, y obtener una lengua difícil . Entonces, cualquier algoritmo que reconozca correctamente debe tomar al menos veces en todas las entradas que pasen una cierta longitud. Esto parece ser lo que estás buscando en tu clase BestE. $T(n)=2^n$ $L$ $L$ $2^n/n^2$

Referencia:

John G. Geske, Dung T. Huynh, Joel I. Seiferas: una nota sobre conjuntos complejos en casi todas partes y la separación de clases deterministas de complejidad de tiempo Inf. Comput 92 (1): 97-104 (1991)

Ryan Williams
fuente

Muy bien gracias. Creo que entendiste bastante bien mi pregunta, y tu frase introductoria "No puedo analizar tus definiciones" es solo una señal de tu modestia :)

MS Dousti

2

Siempre que haya adivinado correctamente, su definición debería ser algo como: "L \ en BestE \ iff (\ exist c) (\ forall M) [(L (M) = L) \ Rightarrow (\ exist n_0) (\ forall n > n_0) (\ forall x \ in \ {0,1 \} ^ n) [T (M (x))> 2 ^ {c | x |})] ".

Ryan Williams

Sí, tienes razón. Edité la definición en el último minuto y extravié algunos de los cuantificadores. Corregí la pregunta según tu definición.

MS Dousti

12

Hay una serie de clases que intentan abordar varias nociones de complejidad de caso promedio. En el complejo zoológico, algunas clases que pueden interesarle son:

Arora / Barak cubre muchas clases similares (en el capítulo 18), definiendo distP, distNP y sampNP.

La relación exacta entre todas estas clases se caracteriza por los Cinco Mundos de Impagliazzo, sobre los cuales se preguntó anteriormente en otra pregunta .

En cuanto a la pregunta de complejidad del "mejor caso", no estoy seguro de entender lo que quieres decir. ¿Estás buscando EXP ?

Si te refieres a clases de complejidad definidas en términos del mejor tiempo de ejecución de casos en todas las instancias, esta no es una muy buena medida de complejidad a priori, ya que solo estarías viendo los casos triviales de cualquier problema dado.

Daniel Apon
fuente

¡Muy bien hecho! Eso es lo que necesitaba para la parte media de la complejidad de la pregunta. Con respecto a la parte del "mejor caso", noté que la declaración original de la pregunta era vaga. ¡Culpa mía! Lo he editado mucho, así que considere leerlo nuevamente.

MS Dousti

5

[Ampliando la respuesta de Ryan Williams y agregando algunos términos de búsqueda para usted] Su noción de la mejor complejidad del caso ya tiene un nombre: dureza en casi todas partes (ae), o bi-inmunidad. (El ejemplo de Ryan es de -bi-inmunity). Si es una clase de complejidad, a continuación, un lenguaje es inmune a si no hay un subconjunto infinito tal que . es -bi-inmune si tanto como su complemento $TIME[T(n)]$ $\mathcal{C}$ $L$ $\mathcal{C}$ $L' \subseteq L$ $L' \in \mathcal{C}$ $L$ $\mathcal{C}$ $L$ son inmunes. Por ejemplo, no es difícil demostrar que su definición de es equivalente a la clase de conjuntos -bi-inmunes. $\overline{L} = \Sigma^* \backslash L$ $\mathcal{C}$ $\mathbf{BestE}$ $E$

(Histórico aparte: la noción de inmunidad fue desarrollada por primera vez por Post en 1944 en la teoría de la computabilidad, mucho antes incluso de que se definiera P. Post realmente se consideró "conjuntos simples": un conjunto es simple si su complemento es inmune. Para un teórico de la computabilidad, la palabra "inmune" generalmente significa "inmune a conjuntos computables". En ese contexto, la inmunidad es equivalente a "conjuntos inmunes a ce" ya que cada conjunto ce infinito contiene uno infinito computable. Creo que el artículo de Post también fue el primero en introducir el noción de reducción de muchos, pero no podría jurarlo).

Joshua Grochow
fuente

M

$M$

L

$L$

L

$L$

M (x) = 1

$M(x)=1$

L^{'}

$L'$

L^{'} \in C

$L' \in C$

1

@Sadeq: arreglado, gracias. @ Ryan: Cierto (o fue hace un par de horas: desde entonces ha actualizado la definición). Entonces sería inmunidad en lugar de bi-inmunidad. De cualquier manera, principalmente solo quería señalar la palabra clave "inmunidad".

Joshua Grochow

2

Diferentes casos tienen más sentido cuando se habla de algoritmos, no de problemas. Por otro lado, las clases de complejidad son sobre problemas, no algoritmos. Por lo tanto, la clase de complejidad siempre es el peor de los casos para cualquier algoritmo debido a la definición.

En complejidad, su objetivo es conocer la cantidad de recursos necesarios para resolver cualquier instancia de un problema determinado. Por lo tanto, sabe que para cualquier instancia y algoritmo dado, necesitará esos recursos y nada más.

En el análisis de algoritmos, su objetivo es garantizar que su algoritmo tenga un límite superior para un recurso, en cualquier caso del problema. Un límite trivial es la clase de complejidad del problema, ya que ningún algoritmo útil (uno que haga pasos innecesarios) lleva más tiempo que eso. Sin embargo, puede mejorar ese límite dados los detalles del algoritmo.

$\Theta$

En cuanto al mejor de los casos, es trivial para cada problema encontrar la menor cantidad de recursos necesarios. Suponga que la entrada es de longitud O (n) y la salida de longitud O (m). Entonces el siguiente TM M siempre se ejecuta en O (n) + O (m) para el mejor caso:

M {Entrada, Instancia, Solución}

Compare la instancia dada con la instancia codificada en la máquina.
Si son iguales, devuelve la solución codificada.
De lo contrario, haz una búsqueda de fuerza bruta.

chazisop
fuente

-1

$O(1)$

Umar
fuente

1

No creo que eso cuente como un algoritmo correcto para el problema. Sin embargo, su algoritmo puede modificarse para que primero verifique si la entrada es igual a la instancia particular que ha predeterminado (en el tiempo O (1)). Si es así, genera la respuesta calculada previamente. Si no, resuelve la instancia dada por cualquier medio. Pensando en ello, cualquier algoritmo correcto se ejecuta en tiempo O (1) para cada instancia, si podemos tomar diferentes constantes detrás de la notación O para diferentes instancias. Por eso, la "complejidad del mejor de los casos" en sentido literal no es útil.

Tsuyoshi Ito

Si habla de cálculo determinista, no probabilístico, tomaría tiempo lineal (O (n) tiempo) para verificar si dos codificaciones de instancias son equivalentes: escanee los n bits de la codificación de entrada y verifique que sea el mismo como la codificación programada, no?

Daniel Apon

2

@Daniel: Sí, pero si una de las instancias es fija, solo toma un tiempo constante, donde la constante depende de la duración de la instancia fija.

Tsuyoshi Ito

Clases de complejidad para casos distintos al "peor caso"

Respuestas: