Un idioma está en la clase D P si hay dos idiomas L 1 ∈ N P y L 2 ∈ c o N P de modo que L = L 1 ∩ L 2LLLDPDPDPL1∈NPL1∈NPL1 \in NPL2∈coNPL2∈coNPL2 \in coNPL=L1∩L2L=L1∩L2L = L1 \cap L2 Un problema canónico completo de es SAT-UNSAT: dadas dos expresiones 3-CNF, F y G , ¿es cierto que F es...
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...
Esta es una generalización de mi pregunta anterior . Deje que MMM sea una máquina determinista en tiempo polinómico que pueden hacer preguntas a algún oráculo AAA . Inicialmente, AAA está vacío, pero esto se puede cambiar después de un juego que se describirá a continuación. Deje xxx ser una...
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 ,...
Si podemos demostrar que , ¿implica que ?N L = N PL = PL=P\mathsf{L}=\mathsf{P}N L = N PNL=NP\mathsf{NL}=\mathsf{NP} Pensé que era el caso, pero no puedo probarlo (también por el
Llamemos un idioma NP escasamente certificado si y solo si:L∈L∈L \in Existe un polinomio tal que para cada entrada de tamaño , si entonces el conjunto de certificados que verifican que tiene un tamaño polinómico, es decir .p:N→Np:N→Np : \mathbb{N} \rightarrow \mathbb{N}x∈Σ∗x∈Σ∗x \in...
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...
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....
Esta es una publicación separada de Consecuencias de UP es igual a NP , y también una pregunta de seguimiento a las clases de complejidad semántica vs. sintáctica . En la publicación anterior aprendimos sobre las clases semánticas y sintácticas . En pocas palabras, cuando una clase puede...
Defina que el modelo computacional MPostBQP sea idéntico a PostBQP, excepto que permitimos polinómicamente muchas mediciones de qubit antes de la selección posterior y la medición final. ¿Podemos dar alguna evidencia que indique que MPostBQP es más poderoso que PostBQP? Defina MPostBQP [k]...
Incluso si no es un punto crucial, no veo ninguna literatura sobre esta cuestión. ¿Hay resultados de relativización? ¿No sería bastante sencillo demostrar una inclusión estricta adaptando el teorema de la jerarquía de tiempo no determinista explorando todos los caminos posibles de la máquina...
Intrigado por la interesante pregunta de Chris Pressey sobre funciones recursivas elementales , estaba explorando más y no pude encontrar una respuesta a esta pregunta en la web. Las funciones recursivas elementales corresponden muy bien a la jerarquía exponencial,
¿Cada lenguaje indecidible reconocible de Turing tiene un subconjunto NP-completo? La pregunta podría verse como una versión más fuerte del hecho de que cada lenguaje infinito reconocible de Turing tiene un subconjunto infinito
Sea la clase de lenguajes que se decida alternando máquinas de Turing que se detengan en el tiempo utilizando el espacio . Sea la clase de lenguajes que se decida alternando máquinas de Turing que dejen de usar las alternancias y el espacio .f ( n ) g ( n ) A A L T S P ( f ( n ) , g ( n ) ) f ( n )...
Sabemos que . Del teorema de Savitch, , y, del Teorema de la jerarquía espacial, . Entonces, como no sabemos si , no sabemos si , o sabemos que ? ¿Alguien ha intentado demostrar que \ mathcal L ^ 2 \ subseteq \ mathcal P ? ¿Cuáles son los últimos resultados o esfuerzos de esta manera? He estado...
Gran parte de la literatura de computación cuántica se centra en el modelo de circuito. La computación cuántica adiabática no se basa en aplicar una secuencia de operadores unitarios, sino en cambiar un hamiltoniano dependiente del tiempo. Estoy buscando información sobre cualquiera de los...
Es bien sabido que la existencia de funciones unidireccionales es necesaria y suficiente para gran parte de la criptografía (firmas digitales, generadores pseudoaleatorios, cifrado de clave privada, etc.). Mi pregunta es: ¿Cuáles son las consecuencias teóricas de la complejidad de la existencia de...
No se cree que lo siguiente sea cierto: L⊆L−uniform NC1L⊆L−uniform NC1\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1 ¿Puedes ayudarme a ver dónde se rompe la discusión? El problema de accesibilidad dirigida está completo para . Sostengo que está en -uniform .L N C...
Deje para , con la promesa de que (donde la suma ha terminado ). Entonces, ¿cuál es la complejidad de determinar si ?xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\}i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\}ZZ\mathbb{Z}x=1x=1x = 1 Observe que...