¿Qué es la clase de complejidad

¿Qué significa la clase de complejidad ? Sé que es la clase de complejidad que contiene los lenguajes para los cuales existe una máquina de Turing no determinista de tiempo polinomial tal que si el número de estados de aceptación de la máquina en la entrada es impar. $\oplus P^{\oplus P}$ $\oplus P$ $A$ $M$ $x \in A$ $M$ $x$

Pero, ¿qué significa ? Simplemente no puedo seguir lo que realmente hace :) $\oplus P^{\oplus P}$

¿Cuáles son las consecuencias prácticas de tal clase de complejidad y cómo es posible demostrar que ? $\oplus P^{\oplus P} = \oplus P$

complexity-theory terminology complexity-classes Stewenson
fuente

Esta notación (incómoda) denota clases de complejidad relativa u oráculo. Ver Wikipedia para una definición. ¿Eso responde a la pregunta? Si no, edítelo para aclararlo.

Raphael

Encontrará la prueba de

en cs.rutgers.edu/~allender/538/murata3.pdf

\oplus P^{\oplus P} = \oplus P

$\oplus P^{\oplus P} = \oplus P$

sdcvvc

Respuestas:

denota la clase equipada con lo que se conoce como unoráculopara - decimos que se le ha dado la capacidad de determinar si una cadena eso nomiembro de un lenguaje contenido en la clase En una sola operación. $\oplus P^{\oplus P}$ $\oplus P$ $\oplus P$ $s$ $L$ $\oplus P$

Veo que otro comentarista (sdcwc) se ha vinculado a la prueba de (vea estas notas en una conferencia de CS 538 en Rutgers ). Una clase de complejidad que es un oráculo a una clase tal que , se dice que es baja para la clase . En este caso, decimos que es bajo en sí mismo. $\oplus P^{\oplus P} = \oplus P$ $C$ $B$ $B^C= B$ $B$ $\oplus P$

Josh Lockhart
fuente

Otro enlace para usted, esta vez a la página de Wikipedia sobre 'baja' de clases de complejidad: en.wikipedia.org/wiki/Low_%28complexity%29

Josh Lockhart

Su estilo de explicación es suficiente para comprender los principios básicos y es fácil de seguir.

stewenson

¿Qué quiere decir básicamente que

está equipado con el oráculo que puede determinar la pertenencia a la lengua

en un solo paso? Desde mi punto de vista, si se trata de resolver algún problema en

, está consultando el oráculo al comienzo del cálculo, así que después del primer paso, ¿sabe cómo le responde el oráculo? Entonces sabes que, dado que has alcanzado un estado de aceptación, el número de tales estados es solo uno, entonces el número impar, ¿entonces aceptas?

\oplus P

$\oplus P$

L

$L$

\oplus P^{\oplus P}

$\oplus P^{\oplus P}$

stewenson

\oplus P

$\oplus P$

L

$L$

\oplus P

$\oplus P$

s

$s$

L

$L$

\oplus P

$\oplus P$

L

$L$

\oplus S A T

$\oplus SAT$

\oplus P

$\oplus P$

f (1^{i}, x)

$f(1^i,x)$

1^{3} = 111

$1^3 = 111$

1^{i}

$1^i$

k

$k$

n^{k}

$n^k$

i \leq n^{k}

$i \leq n^k$

f (1^{i}, x) = f (1^{n^{k}}, x) = f (1^{| x |^{k}}, x)

$f(1^i,x) = f(1^{n^k}, x) = f(1^{|x|^k}, x)$

f \in ♯ P

$f \in \sharp P$