Dado un grafo dirigido y dos vértices . Un par de rutas simples de a es un borde disjunto si no comparten un borde.s , t ∈ V p 1 , p 2 s tG = ( V, E)G=(V,E)G = (V,E)s , t ∈ Vs,t∈Vs,t \in Vpag1, p2p1,p2p_1,p_2sssttt Utilizando el flujo máximo, es fácil decidir si hay un par de caminos disjuntos...
Una fórmula monótona de CNF con m términos en n variables ( ) es una fórmula de la forma f ( x 1 , ... , x n ) = ⋀ C i , donde cada C i es un OR de algún subconjunto de las variables x 1 , ... , x n e i varía de 1 a m .X1, ... , xnortex1,…,xnx_1,\ldots,x_nF( x1, ... , xnorte) = ⋀...
Estoy leyendo la excelente encuesta de Watrous sobre la teoría de la complejidad cuántica. En él, afirma que sería sorprendente si se descubriera que un problema completo de QMA tiene una promesa vacía (es decir, ser un lenguaje). ¿Por qué esto es tan? ¿Tiene que ver con el hecho de que el...
Dado un gráfico mixto G=(V,E,A)G=(V,E,A)G=(V,E,A) con bordes EEE y arcos AAA , encuentre una coincidencia en EEE que minimice el número de arcos en G/MG/MG/M , donde G/MG/MG/M se obtiene de GGG al contraer vértices coincidentes y eliminar arcos paralelos ¿Es (la versión de decisión de) este...
Supongamos que es un lenguaje booleano, de cadenas finitas sobre { 0 , 1 } . Sea L n el número de cadenas en L con longitud n . Para una función d ( n ) desde los enteros positivos hasta los números reales positivos, L tiene una densidad superior d ( n ) si L n ≤ 2 n d ( n ) para todos los n...
Un idioma está en la clase D P si hay dos idiomas L 1 ∈ N P y L 2 ∈ c o N P de modo que L = L 1 ∩ L 2LLLDPDPDPL1∈NPL1∈NPL1 \in NPL2∈coNPL2∈coNPL2 \in coNPL=L1∩L2L=L1∩L2L = L1 \cap L2 Un problema canónico completo de es SAT-UNSAT: dadas dos expresiones 3-CNF, F y G , ¿es cierto que F es...
Contexto: consideramos solo los dígrafos. Deje que CYCLE sea el lenguaje de gráficos con un ciclo; Es un problema de NL completo. Deje que HASEDGE sea el lenguaje de gráficos con al menos un borde. Entonces, trivialmente, CICLO ∪ HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE} ya no es...
En el libro de Arora-Barak, en la definición de funciones construibles en el tiempo, se dice que el uso de funciones que no son construibles en el tiempo puede conducir a "resultados anómalos". ¿Alguien tiene un ejemplo de tal "resultado anómalo"? He escuchado en particular que pueden existir...
Estoy buscando ejemplos de problemas difíciles (en NP o más difíciles) de la informática que pueden reducirse a modelos de procesos físicos. Por ejemplo, max-2-sat se puede reducir a minimización de energía en un modelo Ising. Me gustaría encontrar más ejemplos de este tipo de...
¿Es difícil apx aproximar el número cromático fraccionario en gráficos de grados
La matriz de Moore es similar a la matriz de Vandermonde pero tiene una definición ligeramente modificada. http://en.wikipedia.org/wiki/Moore_matrix ¿Cuál es la complejidad de calcular el determinante de un rango completo de la matriz de Moore módulo algún entero?n×nn×nn \times n ¿Se puede...
Deje ser un gráfico no dirigido. Una descomposición de V en subconjuntos disjuntos V i se llama descomposición de Hamilton de G si el subgrafo inducido por cada conjunto V i es un gráfico de Hamilton o consiste en un solo borde con | V i | = 2
¿ implica E = N E ?E XP = N E X PEXP=NEXP\mathsf{EXP}=\mathsf{NEXP}E = N
Es bien sabido que el cálculo de una máquina de Turing no determinista (NTM) es representable como un árbol de configuraciones, enraizado en la configuración inicial. Cualquier transición en el programa está representada por un enlace padre-hijo en este árbol. También se pueden construir árboles...
Wikipedia escribe: FPT contiene los problemas manejables del parámetro fijo, que son aquellos que pueden resolverse en el tiempo para alguna función computable f . Por lo general, esta función se considera exponencial simple, como 2 O ( k ), pero la definición admite funciones que crecen aún más...
Decidir Graph Homomorphism es en general NP-Complete. ¿Hay algún resultado que estudie este problema cuando los gráficos subyacentes tienen estructura algebraica (como decidir los homomorfismos de Cayley o los gráficos de coset de Cayley a otros gráficos con alguna estructura definida también)?...
Para celebrar el cumpleaños de Alan Turing, Google publicó un garabato que muestra una máquina. ¿Qué tipo de máquina es el garabato? ¿Puede expresar un lenguaje completo de Turing? Hay diferencias obvias en la máquina clásica de turing: una cinta finita, restricciones en cómo se puede conectar el...
Deje que sea un problema completo de EXP. Entonces, .AAAPA=NPAPA=NPAP^A = NP^A Deje que sea cierto oráculo que tiene en cuentas las consultas que (TM en P) hará, y podemos obtener .BBBP B ≠ N P BMMMPB≠NPBPB≠NPBP^B \neq NP^B Pregunta: ¿Tenemos resultados de oráculo similares para P vs...
No he podido encontrar una declaración que relacione y N P R P en la literatura; los punteros serían apreciadosMAMA\mathsf{MA}NPRPNPRP\mathsf{NP}^\mathsf{RP} Creo que son iguales: : El N P máquina adivina cadena de Merlin, y los R P verifica Oracle la cadena como Arthur
En la mayoría de los sistemas de prueba probabilística (teorema PCP, por ejemplo), las probabilidades de error generalmente se definen del lado de los falsos positivos, es decir, una definición típica podría verse así: si , el verificador siempre acepta, pero en En otro caso, la probabilidad de...