Log-space-uniform NC está contenido en un espacio polylog determinista (a veces escrito PolyL). ¿Log-space-uniform RNC también está en esta clase? La versión aleatoria estándar de PolyL debería estar en PolyL, pero no veo que el RNC (uniforme) esté en PolyL aleatorizado. La dificultad que veo es...
Parity-L es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación" (en lugar de un número cero o no cero de rutas de aceptación), y que es restringido aún más al trabajo en espacio...
Mientras lee el artículo "¿Es hora de declarar la victoria en el conteo de la complejidad?" en el blog "La carta perdida de Godel y P = NP" , mencionaron la dicotomía para los CSP. Después de seguir algunos enlaces, buscar en Google y escribir en wikipedia, me encontré con el teorema de Ladner :...
¿Cuáles serían las consecuencias de #P = FP? Me interesan las consecuencias prácticas y teóricas. Desde un punto de vista práctico, estoy particularmente interesado en las consecuencias sobre la Inteligencia Artificial. Punteros a papeles o libros son más que bienvenidos. Por favor no digas que...
El estudio de la representación sucinta de gráficos fue iniciado por Galperin y Wigderson en un artículo de 1983, donde demuestran que para muchos problemas simples como encontrar un triángulo en un gráfico, la versión sucinta correspondiente en -completa. Papadimitriou y Yanakkakis amplían esta...
¿Hay algún problema natural en que no se sabe (se sabe que se cree) en ?NP∩coNPNP∩coNPNP \cap coNPUP∩coUPUP∩coUPUP \cap coUP Obviamente, el más grande que todos conocen en es la versión de decisión de factoring (no tiene un factor de tamaño como máximo k), pero eso es de hecho en .NP∩coNPNP∩coNPNP...
Shiva Kintali acaba de anunciar un resultado (¡genial!) De que el isomorfismo gráfico para gráficos de ancho de árbol acotado de ancho es -hard≥4≥4\geq 4⊕L⊕L\oplus L . Informalmente, mi pregunta es: "¿Qué tan difícil es eso?" Sabemos que no uniformemente , vea las respuestas a esta pregunta ....
Hola chicos, entiendo que el truco de relleno nos permite traducir clases de complejidad hacia arriba - por ejemplo, . El relleno funciona "inflando" la entrada, ejecutando la conversión (digamos de N P a P ), lo que produce un algoritmo "mágico" que puede ejecutar en la entrada rellenada. Si bien...
Recientemente, Ryan Willams demostró que la constructividad en la prueba natural es inevitable para derivar una separación de clases de complejidad: y . NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} La constructividad en la prueba natural es una condición que satisface todas las pruebas combinatorias...
Existe una rica literatura y al menos un libro muy bueno que establece la dureza conocida de los resultados de aproximación para problemas NP-duros en el contexto de error multiplicativo (por ejemplo, la aproximación 2 para la cobertura de vértices es óptima suponiendo UGC). Esto también incluye...
Esto está relacionado con la pregunta ¿Ya se conoce el tamaño de membresía de los testigos para cada idioma de NP? Algunos problemas naturales (-completos) tienen testigos de longitud lineal: una asignación satisfactoria para , una secuencia de vértices para , etc. S A T H A M P A T...
La teoría de la complejidad, a través de conceptos como la completitud de NP, distingue entre problemas computacionales que tienen soluciones relativamente eficientes y aquellos que son intratables. La complejidad "de grano fino" tiene como objetivo refinar esta distinción cualitativa en una guía...
Considere los problemas de optimización de la siguiente forma. Sea f(x)f(x)f(x) una función computable en tiempo polinómico que mapea una cadena xxx en un número racional. El problema de optimización es este: ¿cuál es el valor máximo de f(x)f(x)f(x) sobre cadenas de nnn bits xxx ? Digamos que tal...
¿Cuáles son las razones de peso para creer ? L es la clase de algoritmos de espacio logarítmico con punteros a la entrada.L≠PL≠PL\neq P Supongamos que L = P por el momento. ¿Cómo sería un algoritmo de espacio logarítmico para un problema P-completo en sus esquemas
Al leer una respuesta de Peter Shor y una pregunta anterior de Adam Crume, me di cuenta de que tengo algunas ideas erróneas sobre lo que significa ser PP\mathsf{P} -hard. Un problema es PP\mathsf{P} -hard si cualquier problema en PP\mathsf{P} es reducible con LL\mathsf{L} (o si prefiere...
En este hilo , la prueba de intentada por Norbet Blum se refuta sucintamente al señalar que la función de Tardos es un contraejemplo del Teorema 6.P≠NPP≠NPP \neq NP Teorema 6 : Sea cualquier función booleana monótona. Suponga que hay un aproximador CNF-DNF A que se puede usar para probar un límite...
Me pregunto si hay alguna justificación para creer que o para creer que ?N L ≠ LnorteL = LNL=LNL=LnorteL ≠ LNL≠LNL\neq L Se sabe que . La literatura sobre derandomization de es bastante convincente de que . ¿Alguien sabe acerca de algunos artículos o ideas convincentes que ? R L R L = L N L ≠...
Esta es una especie de pregunta abierta, por lo que me disculpo de antemano. ¿Hay ejemplos de afirmaciones que (aparentemente) no tienen nada que ver con la complejidad o las máquinas de Turing, pero la respuesta implicaría ?P≠NPP≠NP\mathbf{P}\neq
¿Hay un ejemplo de un problema natural que está en BPP pero que no se sabe que está en RP o
¿Es BQP igual a BPP con acceso a un oráculo de subgrupos ocultos