¿Cuáles son algunos problemas no triviales donde sabemos que el algoritmo actual que tenemos es el asintóticamente óptimo? (Para máquinas de turing) ¿Y cómo se prueba
Se ha realizado un trabajo fantástico en lo Permanente durante las últimas dos décadas. Me he estado preguntando por un tiempo sobre la posibilidad de un algoritmo Smooth P para el Permanente de Matrices No Negativas. Por supuesto, existe el famoso algoritmo JSV, pero este es un fpras. Pensando en...
Dados dos CNF, si tienen el mismo número de asignaciones para hacerlos verdaderos, responda "Sí", de lo contrario responda "No". Es fácil ver que está en , ya que si conocemos el número exacto de soluciones para estos dos CNF, simplemente hacemos campaña y respondemos "Sí" o...
1) ¿Es posible tener una reducción parsimoniosa de un problema # P completo #A a un problema de conteo #B cuando (la versión de decisión) A es NP-completa y B está en P? Por ejemplo, ¿puede haber una reducción parsimoniosa de #SAT a #B, cuando B está en P? 2) Si B está en P, ¿cuáles son las...
¿Hay problemas interesantes que están en pero no se sabe que están en N C 2 ? En el documento 'Una taxonomía de problemas con algoritmos paralelos rápidos', Cook menciona que se sabía que MIS solo estaba en N C 5, pero esto se ha reducido a N C 2 . Me pregunto si hay otros problemas con los...
Estoy leyendo el apéndice sobre los límites inferiores de ACC para NEXP en el libro Arora and Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Uno de los lemas fundamentales es una transformación de la circuitos a lo largo de los polinomios...
Hice una búsqueda sobre esto, pero no pude encontrar una respuesta de ninguna manera. Huck respondió por completo. Gracias
Sé que (logarítmicamente muchas llamadas al oráculo NP) es equivalente a P N P | El | (número polinómico de consultas paralelas al oráculo NP). Me preguntaba si la versión de "función" de estas clases también es equivalente, es decir, siPAGN P [logn ]PAGnortePAG[Iniciar
Jan Pax hizo esta pregunta en la lista de correo de Fundamentos de Matemáticas . Ciertamente, P⊕P⊆P#P=PPPP⊕P⊆P#P=PPPP^{\oplus P} \subseteq P^{\#P} = P^{PP} pero sospecho por las respuestas a esta pregunta que no se sabe si ⊕P⊆PP⊕P⊆PP\oplus P \subseteq PP (de lo contrario, PPPPPP sería una posible...
Durante mucho tiempo, pensé que un problema era NP-completo si es (1) NP-hard y (2) está en NP. Sin embargo, en el famoso artículo "El método del elipsoide y sus consecuencias en la optimización combinatoria" , los autores afirman que el problema del número cromático fraccional pertenece a NP y...
La clase de complejidad PPAD generalmente se define al indicar que Fin de línea está completa con PPAD. El fin de la línea es un problema de búsqueda. La entrada consiste en un gráfico dirigido en el que cada nodo tiene un grado de entrada y salida como máximo 1. El gráfico viene dado por una...
Muchas clases de complejidad definidas con máquinas de Turing tienen definiciones en términos de circuitos uniformes. Por ejemplo, P también se puede definir usando circuitos de tamaño polinómico uniforme, y de manera similar BPP, NP, BQP, etc. se pueden definir con circuitos uniformes....
Cada vez que enseño NP-Completeness, los estudiantes preguntan "¿hay algún problema que se sepa que no pertenece a NP?" ¿Cómo responderías? Por lo general, les doy un problema indecidible como ejemplo, pero esto a menudo no resulta bien: (a) si les doy el problema de detención, piensan que es un...
Una pregunta reciente (ver Consecuencias de NP = PSPACE ) pidió a las consecuencias "desagradables" de NP=PSPACENP=PSPACENP=PSPACE . Las respuestas lista bastantes consecuencias de colapso, incluyendo NP=coNPNP=coNPNP=coNP y otros, proporcionando un montón de razones para creer
El teorema de la pretición paralela de Raz es un resultado importante en PCP, aproximación, etc. El teorema se resume de la siguiente manera. G=(S,T,A,B,π,V)G=(S,T,A,B,π,V)G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi,
P / poly es la clase de problemas de decisión que puede resolver una familia de circuitos booleanos de tamaño polinómico. Alternativamente, se puede definir como una máquina de Turing de tiempo polinómico que recibe una cadena de aviso que tiene un tamaño polinómico en n y que se basa únicamente en...
Considere el siguiente juego en un gráfico ponderado dirigido con una ficha en algún nodo.GGG Todos los nodos de están marcados por A o B.GGG Hay dos jugadores, Alice y Bob. El objetivo de Alice (Bob) es cambiar el chip a un nodo marcado por A (B). Inicialmente, Alice y Bob tienen y dólares...
¿Puede todo lo siguiente sostenerse simultáneamente? LsLsL_s está contenido en para todos los enteros positivos .Ls+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s es el lenguaje de todas las palabras finitas sobre .{0,1}{0,1}\{0,1\} Hay una cierta clase de complejidad y una noción de reducción...
¿Qué otros problemas de idiomas diferentes al isomorfismo de gráficos hay en ? ¿Puedes dar algunas referencias?nortePAG∩ c o A MNP∩coAMNP\cap coAM Actualización: Olvidé mencionar que estoy interesado en idiomas que no se sabe que están en .c o
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...