Tengo un problema que está en NEXP NP y también se puede resolver con una TM alterna usando tiempo exponencial y solo una alternancia (comenzando en un estado existencial).notario públicoNP^{\text{NP}} ¿Se sabe algo sobre NEXP NP ? ¿Es igual a NEXP o alguna otra clase? ¿Hay problemas completos...
No recuerdo haber visto una separación de clases no basada en resultados de diagonalización y relativización. La diagonalización aún podría usarse para separar las clases conocidas restantes, porque los argumentos no relativizantes aún podrían usarse en la conclusión de diagonalización, o en la...
¿Cómo se ve un problema y la razón por la que es probable NP-Intermedio en lugar de NP-Completo? A menudo es bastante simple observar un problema y determinar si es probable que esté NP-Completo o no, pero me parece mucho más difícil saber si un problema es NP-Intermedio ya que la línea parece ser...
Supongo que se llamaría # P-Space, pero solo he encontrado un artículo que lo menciona vagamente. ¿Qué tal la versión de conteo de EXP-TIME-Complete, NEXP-Complete y EXP-SPACE-Complete? ¿Hay algún trabajo previo que pueda citarse con respecto a este o algún tipo de inclusión o exclusión como el...
Desde el teorema de la jerarquía espacial se sabe que si fff es construible en el espacio, entonces DSPACE ( 2f(n)2f(n)2f(n) ) no es igual a DSPACE ( f(n))f(n))f(n)) . Aquí, por DSPACE ( f(n))f(n))f(n)) me refiero a la clase de todos los problemas que se pueden resolver en el espacio f(n)f(n)f(n)...
Respuesta: no conocida Muchas gracias a todos los que ayudaron a refinar esta pregunta y las definiciones asociadas. Las definiciones de esta wiki proporcionaron el punto de partida para la wiki TCS más reciente " ¿Contiene P lenguajes cuya existencia es independiente de PA o ZFC? (Wiki de la...
NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Consideremos ahora las familias de circuitos con puertas de Oracle - por ejemplo, , donde es una clase de la complejidad del circuito que contiene logspace con acceso a Oracle a otra clase , a través de puertas de Oracle adjuntas a la base de . ¿Hay algún...
¿Es NPPP=PPPNPPP=PPP\mathsf{NP^{PP}} = \mathsf{P^{PP}} ? O, más generalmente, ¿es NPPP⊆PPP/polyNPPP⊆PPP/poly\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}
Se sabe que algunas clases de complejidad sintáctica (no relativizadas) entre y P S P A C E tienen la siguiente propiedad, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Me pregunto si existe una clase de complejidad sintáctica (no relativizada) X tal que P P ⊆ X ⊆ P S P A C EPP{\bf...
Deje que sea un oráculo genérico en el sentido de la categoría de Cohen / Baire. Deje ser un oráculo al azar.RGGGRRR ¿Hay clases de complejidad A y B con o el al revés, A G ≠ B GAG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne...
La clase UP se define como tal: La clase de problemas de decisión que una máquina NP puede resolver Si la respuesta es 'sí', se acepta exactamente una ruta de cálculo. Si la respuesta es 'no', todas las rutas de cálculo se rechazan. Estoy tratando de desarrollar la intuición para esta...
¿Qué evidencia hay de que ?c o R P≠ NPAGcoRP≠NPcoRP \neq NP es la clase de idiomas para los que existe una máquina de Turing probabililista que se ejecuta en tiempo polinómico y siempre responde Sí en una entrada que pertenece al idioma y responde No con probabilidad al menos la mitad de una...
¿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...
Los problemas han sido, en su conjunto, clasificados, gracias a la Complejidad Computacional. Pero, en ecuaciones diferenciales, ¿es posible clasificar las ecuaciones diferenciales en función de su estructura computacional? Por ejemplo, si una ecuación no homogénea de primer orden es...
Me pregunto si hay lenguaje escaso (incluso construido por diagolanización retrasada) en NPI bajo el supuesto de que .P≠NPP≠NPP \neq
En esta pregunta , se mencionó que existen versiones descriptivas de complejidad del teorema de Rice. Encontré una prueba del siguiente teorema: Dada una clase de complejidad C , las propiedades no triviales de los lenguajes en C no se pueden calcular en C Anteriormente había publicado la...
Deje que la clase BPNC (la combinación de y ) sean algoritmos paralelos de profundidad logarítmica con probabilidad de error limitada y acceso a una fuente aleatoria (no estoy seguro si este tiene un nombre diferente). Defina la clase DBPNC de manera similar, excepto que todos los procesos tienen...
Conjetura de Berman-Hartmanis: todos los lenguajes NP completos se parecen, en el sentido de que pueden estar relacionados entre sí por isomorfismos de tiempo polinomiales [1]. Estoy interesado en una versión más detallada del "tiempo polinómico", es decir, si usamos reducciones parametrizadas....
BPPBPP\mathsf{BPP} yZPPZPP\mathsf{ZPP} son dos de las clases básicas de complejidad probabilística. BPPBPP\mathsf{BPP} es la clase de lenguajes decididos por algoritmos probabilísticos de tiempo de polinomio de Turing donde la probabilidad de que el algoritmo devuelva una respuesta incorrecta está...
La clase de complejidad se define de la siguiente manera (de Wikipedia ):SP2S2P\textrm{S}_2^\textrm{P} Un lenguaje está en si existe un predicado de tiempo polinómico tal queLLLSP2S2PS_2^PPPP Si , entonces existe una tal que para todo ,x∈Lx∈Lx \in LyyyzzzP(x,y,z)=1P(x,y,z)=1P(x,y,z)=1 Si ,...