En el "último párrafo" de la "primera página" del siguiente documento: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , "Si NP tiene circuitos de tamaño polinómico, entonces MA = AM", Ciencias de la computación teóricas, 1995. Encontré una afirmación algo contraintuitiva:...
Recientemente, me he encontrado con la siguiente variante de coloración de bordes. Dado un gráfico conectado no dirigido, encuentre una coloración de los bordes que use la cantidad máxima de colores al tiempo que satisface la restricción de que, para cada vértice , los bordes incidentes a usan...
Siguiendo la sugerencia de Josh Grochow, estoy convirtiendo mi comentario de una pregunta anterior en una nueva pregunta. ¿Qué evidencia tenemos para ?U P ≠ N PUP≠NP\mathsf{UP} \neq \mathsf{NP} Aquí, U PUPAG\mathsf{UP} es la clase de lenguajes reconocibles por las máquinas de Turing no...
Supongamos que considero la siguiente variante de BPP, que nos permite llamar E (xact) BPP: un lenguaje está en EBPP si hay un TG polinomial aleatorio que acepta cada palabra del idioma con exactamente 3/4 de probabilidad y cada palabra no en el lenguaje con exactamente 1/4 de probabilidad....
¿Cuáles son algunos ejemplos de pares de clases de complejidad y B tales queAAABBB no sabemos si , yA=BA=BA=B tampoco conocemos relativizaciones contradictorias (es decir, no conocemos los oráculos y Q de manera que A P = B P y A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P = B^PAQ≠BQAQ≠BQA^Q \ne B^Q Para...
Debido a una pregunta que me hizo Greg Kuperberg, me pregunto si hay documentos que definan y estudien clases complejas de idiomas que admitan varios tipos de pruebas de conocimiento . Las clases como SZK y NISZK son extremadamente natural desde un punto de vista la complejidad, incluso si nos...
Decimos que NFA MMM es constantemente ambiguo si existe k∈Nk∈Nk\in \mathbb{N} tal que cualquier palabra w∈Σ∗w∈Σ∗w\in \Sigma^* sea aceptada por 000 o (exactamente) caminos.kkk Si el autómata es constantemente ambiguo para , entonces se llama FA inequívoca (UFA).k = 1 MMMMk=1k=1k=1MMM Deje que...
Me interesa si existen buenos artículos o encuestas expositivas a los que me pueda referir cuando escribo sobre operadores de clase de complejidad : operadores que transforman las clases de complejidad haciendo cosas como agregarles cuantificadores. Ejemplos de operadores. Lo siguiente se puede...
Me preguntaba si los problemas para los cuales existen algoritmos de tiempo sublineal (en el tamaño de entrada) pueden caracterizarse por poseer propiedades específicas. Esto incluye el tiempo sublineal (por ejemplo, pruebas de propiedad, una noción alternativa de aproximación para problemas de...
Necesito una lista de idiomas completos. Hay dos de estos problemas enumerados en el Complejo Zoo , a saber:Σpag2Σ2pag\Sigma_2^p Mínimo equivalente DNF. Dada una fórmula DNF F y un entero k, ¿hay una fórmula DNF equivalente a F con k o menos ocurrencias de literales? El implicante más corto. Dada...
¿Está NP en DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})
LogCFL es el conjunto de todos los idiomas que son logspace reductibles a un lenguaje sin contexto. Del mismo modo, LogDCFL es el conjunto de todos los lenguajes que son espacio de registro reducible a un lenguaje determinista sin contexto. Vea este artículo de Wikipedia para algunos problemas...
Los teoremas de la jerarquía son herramientas fundamentales. Un buen número de ellos se recopiló en una pregunta anterior (consulte ¿Qué jerarquías y / o teoremas de jerarquía conoce? ). Algunas separaciones de clase de complejidad se derivan directamente de los teoremas de jerarquía. Ejemplos de...
Se dice que un problema P está en APX si existe alguna constante c> 0 tal que existe un algoritmo de aproximación de tiempo polinómico para P con factor de aproximación 1 + c. APX contiene PTAS (visto simplemente seleccionando cualquier constante c> 0) y P. ¿APX está en NP? En particular,...
En nuestro trabajo reciente, resolvemos un problema computacional que surgió en un contexto combinatorio, suponiendo que , donde es el -versión de . El único artículo sobre que encontramos fue el artículo de Beigel-Buhrman-Fortnow 1998 que se cita en Complexity Zoo . Entendemos que podemos tomar...
¿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
La clase de complejidad BQP corresponde a subrutinas cuánticas de tiempo polinómico que toman entradas clásicas y escupen una salida clásica probabilística. El asesoramiento cuántico modifica eso para incluir copias de algunos estados de asesoramiento cuántico predeterminados pero con entradas...
Al leer el documento " Una teoría aplicativa para FPH " puede encontrar el siguiente pasaje: Considerando las teorías que caracterizan las clases de complejidad computacional, existen tres enfoques diferentes: en uno, las funciones que se pueden definir dentro de la teoría son...
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...
Pregunta corta ¿Cuál es el poder computacional de los circuitos "cuánticos", si permitimos puertas no unitarias (pero aún invertibles), y requerimos que la salida dé la respuesta correcta con certeza? Esta pregunta es, en cierto sentido, sobre lo que le sucede a la clase cuando permite que los...