¿Cómo se puede demostrar que relación existe entre "Conjetura de juegos únicos" y "Teorema de PCP"? ¿Cómo se explica "La conjetura de juegos únicos" es una forma más fuerte de "teorema de
El método negativo del adversario ( ) es un SDP que caracteriza la complejidad de la consulta cuántica. Es una generalización del método adversario ampliamente utilizado ( A D V ) y supera las dos barreras que obstaculizaron el método adversario:ADV±ADV±ADV^\pmADVADVADV La barrera de la prueba de...
Recientemente leí una prueba que tenía la intención de mostrar que un problema era fuertemente NP-duro, simplemente reduciéndolo (en tiempo polinómico) a partir de un problema fuertemente NP-duro. Esto no tenía ningún sentido para mí. Pensé que tendrías que demostrar que cualquier número utilizado...
Rompecabezas Dado que el problema es largo aquí hay un caso especial que captura su sentido. Problema: Sea A un algoritmo detrminístico para 3-SAT. Es el problema de simular completamente el algoritmo A (en cada instancia del problema). P-Space duro? (Más precisamente, ¿hay razones para creer...
Las gráficas planas tienen género cero. Los gráficos que se pueden insertar en un toro tienen un género como máximo 1. Mi pregunta es simple: ¿Hay algún problema que sea polinomialmente solucionable en gráficos planos pero NP-duro en gráficos del género uno? En términos más generales, ¿hay algún...
Hoy enseñé los límites inferiores de , y uno de los estudiantes preguntó por la razón del nombre . La explicación oficial es que la "A" significa "Alternancia".A C0 0AC0AC^0A CACAC Recuerdo vagamente que me dijeron hace muchos años que Nick Pippenger Steve Cook nombró a después de Nick Pippenger...
Version corta. La prueba original de que # 2-SAT es # P- completo muestra, de hecho, que esas instancias de # 2-SAT son monótonas (no implican negaciones de ninguna variable) y bipartitas (el gráfico formado por las cláusulas sobre el variables es un gráfico bipartito) son #P -duro. Por lo tanto,...
La complejidad del circuito de profundidad limitada es una de las principales áreas de investigación dentro de la teoría de la complejidad del circuito. Este tema tiene su origen en resultados como "la función de paridad no está en AC0AC0AC^{0} " y "la función mod no es calculada por ", donde es la...
Estoy buscando ejemplos naturales de algoritmos eficientes (es decir, en tiempo polinómico) st su corrección y eficiencia pueden demostrarse de manera constructiva (p. ej., en o ), peroPAGR APAGRUNPRAHUNHUNHA no se conoce ninguna prueba que utilice solo conceptos eficientes (es decir, no sabemos...
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...
Una cosa que las computadoras cuánticas pueden hacer (posiblemente incluso con solo circuitos cuánticos de profundidad logarítmica BPP +) es aproximar-muestrear la transformada de Fourier de una función de valor booleano en P.± 1±1\pm 1 Aquí y más abajo, cuando hablo de probar la transformada de...
Considere el siguiente problema QQQ : Se nos da un número entero , y k intervalos [ l i , r i ] con 1 ≤ l i ≤ r i ≤ 2 n . También se nos dan 2 n enteros d 1 , ... , d 2 n ≥ 0 . La tarea es seleccionar un número mínimo de intervalos [ l i , r i
Al tratar de convencer a los economistas de la relevancia de la teoría de la complejidad en forma impresa, ¿hay alguna referencia estándar para citar? Estoy familiarizado con la publicación del blog de Noam Nisan , la encuesta de Tim Roughgarden y el capítulo 11 del ensayo de Scott Aaronson . Estas...
Estoy haciendo una revisión de la literatura sobre el problema del isomorfismo gráfico. La mayoría de los trabajos que estoy leyendo están escritos por EM Luks y Laszlo Babai. Estos documentos utilizan el conocimiento de alto nivel de la teoría de grupos y la teoría de la complejidad. Como soy...
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....
Mientras buscaba en el Sistema de información sobre clases de gráficos y sus inclusiones , encontré varias clases de gráficos para las cuales el problema del Ciclo Hamiltoniano es NP completo, mientras que la complejidad de los problemas del Camino Hamiltoniano NO se conoce. Algunas de esas clases...
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...
El artículo "Algoritmos subcuadráticos para 3SUM", de Ilya Baran, Erik D. Demaine, Mihai Patrascu tiene la siguiente complejidad para el Problema 3SUM: dada una lista LLL de enteros si hay tal quex , y , z ∈ L x + y = z .nnnx,y,z∈Lx,y,z∈Lx,y,z \in
Se sabe que el tamaño mínimo de los U_2 que calculan la función de paridad es exactamente igual a . La prueba de límite inferior se basa en el método de eliminación de puerta.U2U2U_23(n−1)3(n−1)3(n-1) Recientemente, noté que el método de eliminación de compuerta funciona bien también para U_2 no...
Dado el grupo de simetría y dos subgrupos y , ¿se mantiene ? G , H ≤ S n π ∈ S n G π ∩ H = ∅SnorteSnorteS_nG , H≤ Snortesol,H≤SnorteG, H\leq S_nπ∈ Snorteπ∈Snorte\pi\in S_nG π∩ H= ∅solπ∩H=∅G\pi\cap H=\emptyset Hasta donde yo sé, el problema se conoce como el problema de intersección de coset. Me...