El papel Lauri Hella y José María Turull-Torres, Cálculo de consultas con lógicas de orden superior , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 propone lógica VO, lógica de orden variable. Esto permite la cuantificación sobre los pedidos sobre las variables. VO es bastante...
La siguiente pregunta utiliza ideas de criptografía aplicadas a la teoría de la complejidad. Dicho esto, es una pregunta puramente teórica de la complejidad, y no se requiere ningún conocimiento criptográfico para responderla. Deliberadamente escribo esta pregunta de manera informal. A falta de...
Por http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Si es un lenguaje de PSPACE completa, P A = N P A .UNAAPAGUN= NPAGUNPA=NPAP^{A}=NP^{A} Si es un oráculo de tiempo polinómico determinista, P B ≠ N P B (suponiendo P ≠ N P ).siBBPAGsi≠ NPAGsiPB≠NPBP^{B}\ne NP^{B}PAG≠ NPAGP≠NPP\ne NP...
El resultado de Baker-Gill-Solovay mostró que la pregunta P = NP no se relativiza, en el sentido de que ninguna prueba relativizante (insensible a la presencia de un oráculo) puede resolver la pregunta P = NP. Mi pregunta es: ¿Hay un resultado similar para la pregunta "¿Existe un problema de PH...
Mientras trabajaba en un proyecto algo no relacionado para Suresh, recientemente me encontré con un trabajo realizado por Page y Opper sobre sistemas componibles por el usuario y una parte de su trabajo discutió brevemente problemas que no pueden verificarse en el tiempo polinómico. No he podido...
He leído en SP Jordan, D. Gosset, "Amor del PJ problemas -Complete para hamiltonianas stoquastic y matrices de MarkovQ MUNQMAQMA " que es poco probable que .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM Me sorprendió esta afirmación. Entonces, ¿cuál es la relación adecuada entre y A M ?Q MUNQMAQMAA...
'Dado , ¿hay x , y ∈ N , a x 2 + b y = c ' es N P -completo?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} ¿A qué clase de complejidad pertenece 'Dado , a qué pertenece x , y ∈ N , a x 2 + b y 2 = c '?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb...
Tengo parte de un intento de prueba de . El intento de prueba consiste en una reducción de Karp desde -complete problem 3-REGULAR VERTEX COVER a SAT. ⊕ P ⊕⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Dado un gráfico cúbico , la reducción genera una fórmula CNF que...
¿Podemos demostrar que para cada idioma que no es N P -duro (esto supone P ≠ N P ), P L ≠ P SAT ? Alternativamente, ¿se puede probar esto bajo cualquier supuesto razonable?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne...
El teorema de la jerarquía del tiempo establece que las máquinas de Turing pueden resolver más problemas si tienen (suficiente) más tiempo. ¿Se mantiene de alguna manera si el espacio está limitado asintóticamente? ¿Cómo se relaciona DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
Sabemos que si entonces todo el PH colapsa. ¿Qué pasa si la jerarquía polinómica se colapsa parcialmente? (¿O cómo entender que el PH podría colapsar por encima de cierto punto y no por debajo?)PAG= NPAGP=NPP=NP En palabras más cortas, ¿cuáles serían las consecuencias de y P ≠ N P ?nortePAG= c o...
Imaginemos que tenemos dos conjuntos de puntos tamaño . ¿Cuál es la complejidad (temporal) de las pruebas si difieren solo por rotación? : existe una matriz de rotación tal que ?mmm O O T = O T O = I X = O YX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Hay un...
RP=NPRP=NPRP = NP es ampliamente conjeturado como falso. Pero imagine por un momento que es verdad. En tal caso, ¿qué tan probable sería que ?P=NPP=NPP = NP En otras palabras: en un mundo donde RP=NPRP=NPRP = NP , ¿qué podría verse como un obstáculo para que creamos P=NPP=NPP = NP...
La página de Wikipedia en PSPACE menciona que la inclusión no es estricta (desafortunadamente sin referencias).NL⊂PHNL⊂PHNL\subset PH P1: ¿Qué pasa con y ? ¿Se sabe que son estrictos?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Si no, ¿hay una clase establecida que contiene y para la cual no...
TC0TC0\mathsf{TC^0} dTC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd La entrada del zoológico para TC0TC0\mathsf{TC^0} solo menciona la separación entre la profundidad 2 y 3. ¿También hay una referencia estándar para el hecho de que la jerarquía AC0dACd0\mathsf{AC^0_d} no...
¿Cuál es el ancho de árbol mínimo de un circuito sobre {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} para calcular MAJ? Aquí MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} produce 1 si al menos la mitad de sus entradas son 111 . Solo me importa el tamaño del circuito (debe ser polinomial) y...
¿ NPNP∩coNP=NPNPNP∩coNP=NP\mathsf{NP^{NP \,\cap\, coNP}=NP}mantener? Claramente NPNP≠NPNPNP≠NP\mathsf{NP^{NP}\neq NP} , pero me parece que NP∩coNPNP∩coNP\mathsf{NP\cap coNP} es "determinista", lo que me hace creer que esto es cierto. ¿Hay una prueba simple (o tal vez solo por definición)?...
Esta pregunta puede tener una respuesta obvia ... pero aquí está la pregunta de todos modos. Intuitivamente, es la siguiente declaración plausible: "una máquina con una subrutina A que a su vez tiene una subrutina B es lo mismo que una máquina con una subrutina A que tiene acceso a la subrutina...
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...