Ejemplos de variantes completas de limitadas de conjuntos indecidibles:NPNPNP Problema de detención delimitado = { | La máquina NTM detiene y acepta en pasos}M x t( M, x , 1t)(M,x,1t)(M, x, 1^t)METROMMXxxttt Mosaico limitado = { | hay un mosaico de un cuadrado de área por mosaicos de }t 2 T(...
Suponga que P≠NPP≠NPP \neq NP Deje usar la siguiente notación para la tetración (es decir.iaia{}^ia ).ia=aa⋅⋅⋅ai timesia=aa⋅⋅⋅a⏟i times{}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}} | x | es el tamaño de la instancia x. Deje L ser una lengua,...
Hiroimono es un popular rompecabezas completo de Estoy interesado en la complejidad computacional de un rompecabezas relacionado.NPNPNP El problema es: Entrada : dado un conjunto de puntos en una cuadrícula x n cuadrada y entero knnnnnnkkk Pregunta : ¿Existe un polígono rectilíneo (sus lados...
El problema de coincidencia perfecta de dos colores es decidir si un gráfico tiene una coloración con dos colores de manera que cada nodo tenga exactamente un vecino del mismo color que él. Schaefer demostró que el problema era NP completo . Sigue siendo NP-completo incluso para gráficos cúbicos...
Planteamiento del problema : Deje que sea un autómata pushdown (potencialmente no determinista) y deje que sea su alfabeto de entrada. ¿Hay una palabra st que es aceptado por ?A w ∈ A ∗ | w | ≤ k MMETROMETROMUNAUNA\cal Aw ∈ A∗w∈UNA∗w \in \cal A^*El | w | ≤kEl |wEl |≤k|w| \leq kMETROMETROM ¿Es...
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...
Se proporciona el conjunto . Para cada elemento , tenemos peso y costo . El objetivo es encontrar el subconjunto de tamaño que maximice la siguiente función objetivo: .e i w i > 0 c i > 0 M k ∑ e i ∈ M w i + ∑ e i ∉ M w i c iS= { e1, ⋯ , enorte}S={e1,⋯,en}S=\{e_1,\cdots,e_n\}miyoeie_iwyo>...
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
¿Existen algoritmos conocidos para el siguiente problema que superen al algoritmo ingenuo? Entrada: Un sistema de desigualdades lineales.mA x ≤ bAx≤bAx \le bmetromm Salida: una solución factible si existe.X∗∈ { 0 , 1 }nortex∗∈{0,1}nx^*\in \{0,1 \}^n Supongamos que y tienen entradas enteros....
Encontré dos ejemplos de dureza hipotética de algunos problemas gráficos. La dureza hipotética significa que refutar alguna conjetura implicaría la completitud NP del problema gráfico respectivo. Por ejemplo, la conjetura de Barnette establece que cada gráfico bipartito plano cúbico conectado a 3...
¿Qué tan difícil es el problema de Set Cover si el número de elementos está limitado por alguna función (por ejemplo, lognlogn\log n ) donde nnn es el tamaño de la instancia del problema. Formalmente, Let y F = { s 1 , ⋯ , S n } donde S i ⊆ U y m = O ( log n ) . ¿Qué tan difícil es decidir el...
Tengo el siguiente problema: Entrada: dos conjuntos de intervalos y T (todos los puntos finales son enteros). Consulta: ¿hay una biyección monótona f : S → T ?SSSTTTF: S→ Tf:S→Tf:S \to T La biyección es monótona wrt el conjunto para su inclusión en y T . ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y )SSSTTT∀ X⊆...
¿Es un problema CNF SAT NP difícil cuando el número total (pero no el ancho) de las cláusulas de 3 o más términos está limitado por una constante? ¿Qué pasa específicamente cuando solo hay una de esas
¿Cuál es la definición estándar de Planar 3-SAT? He visto varias definiciones diferentes. ¿Cuál fue el documento original que lo definió y demostró que era NP
Estoy interesado en el siguiente problema. Se nos da como entrada una "permutación de destino" , así como una lista ordenada de índices . Luego, comenzando con la lista (es decir, la permutación de identidad), en cada paso de tiempo intercambiamos el elemento en con el elemento, con probabilidad...
Sea un conjunto de formas rectangulares -dimensionales. Para y , describe la longitud de en la dimensión . La misma notación se utiliza para el contenedor C . El problema del empaque ortogonal dimensional D (OPP- D ) es decidir si V encaja en el contenedor C sin solaparse. Formalmente, el problema...
Hay algunos problemas NP-Complete ( , , etc.) que se sabe que están en . ¿Qué pasa con los espacios sub-lineales?S A TSUNAT \mathsf{SAT} D S P A C E ( n )S U B S E T S U MSUsiSmiTSUMETRO \mathsf{SUBSETSUM} D S P A C E ( n )reSPAGSUNACmi(norte) \mathsf{DSPACE(n)} ¿Existe algún problema conocido...
¿Cada lenguaje indecidible reconocible de Turing tiene un subconjunto NP-completo? La pregunta podría verse como una versión más fuerte del hecho de que cada lenguaje infinito reconocible de Turing tiene un subconjunto infinito
Considere un problema en el que se le proporciona una cuadrícula 2D (por ejemplo, un tablero de ajedrez) donde están ocupados ciertos cuadrados y necesita colocar el número mínimo de rectángulos no superpuestos de cualquier tamaño wxh donde w = 1 o h = 1 (es decir, "cuadrado segmentos ") de modo...
Supongamos que P! = NP. Sabemos que podemos hacer instancias fáciles de 3-SAT en cualquier momento. También podemos generar lo que creemos que son instancias difíciles (porque nuestros algoritmos no pueden resolverlas rápidamente). ¿Hay algo que impida que el conjunto de instancias difíciles sea...