¿Está comprobado que el cálculo cuántico no es mejor para resolver problemas completos de NP que el cálculo clásico o simplemente se
Si de hecho es igual a N P , ¿cómo mejoraría esto nuestros algoritmos para factorizar enteros más rápido? En otras palabras, ¿qué tipo de información nos daría este hecho para comprender mejor la factorización de enteros?PP{\sf P}NPNP{\sf
Planar 3SAT es NP-completo. Una instancia plana de 3SAT es una instancia de 3SAT para la cual el gráfico creado con las siguientes reglas es plano: agregue un vértice para cada yXyoXyox_iXyo¯Xyo¯\bar{x_i} agregue un vértice para cada cláusulaCjCjC_j añadir una ventaja para todos los par( xyo,...
Me pregunto, ¿cuál es el algoritmo más conocido, en términos de notación Big- , para resolver la programación lineal entera?OOO Sé que el problema es completo, por lo que no espero nada polinomial. Y sé que hay muchas heurísticas y otras que se usan en aplicaciones prácticas como CPLEX, pero estoy...
El problema de 3 particiones pregunta si un conjunto de 3n3n3n enteros se puede dividir en nnn conjuntos de tres enteros, de modo que cada conjunto sume un entero dado BBB. El problema de Partición equilibrada pregunta si 2n2n2n enteros se pueden dividir en dos conjuntos de cardinalidad iguales de...
Supongamos que hay una sesión de tutoría en una universidad. Tenemos un conjunto de kkk preguntas Q = { q 1 ... q k }Q={q1…qk}Q = \{ q_1 \ldots q_k \} y un conjunto de nnn estudiantes S = { s 1 ... s n }S={s1…sn}S = \{ s_1 \ldots s_n \} . Cada estudiante tiene una duda en un determinado...
Mi profesor hizo la declaración Cualquier problema finito no puede ser NP-Complete Estaba hablando de Sudoku en ese momento diciendo algo similar a que para un Sudoku 8x8 hay un conjunto finito de soluciones, pero no puedo recordar exactamente lo que dijo. Escribí la nota que he citado pero...
El conocido problema SAT se define aquí como referencia. El problema DOUBLE-SAT se define como DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least...
Entonces, sé que probar si un lenguaje regular es un subconjunto del lenguaje regular S es decidible, ya que podemos convertirlos a ambos en DFA, calcular R ∩ ˉ S y luego probar si este idioma está vacío.RRRSSSR∩S¯R∩S¯R \cap \bar{S} Sin embargo, dado que esto requiere la conversión a DFA, es...
En términos de tiempo de ejecución asintótico en el peor de los casos, ¿qué problema de NP completo tiene el algoritmo (exacto) más rápido conocido y cuál es el algoritmo? ¿Hay algo conocido que sea más rápido que
Esta es probablemente una pregunta estúpida, pero simplemente no entiendo. En otra pregunta se les ocurrió el teorema de dicotomía de Schaefer . Para mí, parece que demuestra que cada problema de CSP está en P o en NP-completo, pero no en el medio. Dado que cada problema de NP puede transformarse...
Suponiendo que tenemos un problema pagpp y mostramos que el límite inferior para resolver pagpp es Ω ( 2norte)Ω(2n)\mathcal{\Omega}(2^n) . ¿puede el límite inferior Ω ( 2norte)Ω(2n)\mathcal{\Omega}(2^n) implica el problema en nortePAGNPNP
Estoy tratando de resolver este problema y realmente estoy luchando. Una fórmula booleana monótona es una fórmula en lógica proposicional donde todos los literales son positivos. Por ejemplo, (x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3...
Leí acerca de NPC y su relación con PSPACE y deseo saber si los problemas de NPC se pueden resolver de manera determinista utilizando un algoritmo con el requisito de espacio polinomial en el peor de los casos, pero potencialmente tomando tiempo exponencial (2 ^ P (n) donde P es...
¿La dificultad de un problema NP-hard o NP-complete (como se define aquí ) cambia cuando su entrada es unaria en lugar de codificada en binario? ¿Qué diferencia hay si la entrada de un problema fuertemente NP-hard está codificada de forma unaria? Quiero decir, si tomo, por ejemplo, el problema de...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
¿Está el siguiente problema NP-completo? (Asumo que sí). Entrada: un gráfico no dirigido en el que el conjunto de bordes puede descomponerse en dos ciclos simples separados por bordes (estos no son parte de la entrada).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Pregunta: ¿Hay un ciclo...
¿Hay algún algoritmo conocido que muestre correctamente "sí" a un problema NP-completo sin generar implícitamente un certificado? Entiendo que es sencillo convertir un oráculo de satisfacción en un buscador de asignación satisfactoria: simplemente repita las variables, pidiéndole al oráculo de...
Sé que el conjunto independiente máximo en gráficos sin triángulos cúbicos es NP-completo. ¿Sigue siendo NP completo en caso de que necesitemos que el conjunto independiente sea de tamaño exactamente ?|V|/2|V|/2|V|/2 Básicamente, la instancia SÍ de un problema de conjunto independiente en un...
Me pregunto si hay un algoritmo polinómico para "2-SAT con relaciones XOR". Tanto 2-SAT como XOR-SAT están en P, pero ¿es su combinación? Entrada de ejemplo: Parte 2-SAT: (a or !b) and (b or c) and (b or d) Parte XOR: (a xor b xor c xor 1) and (b xor c xor d) En otras palabras, la entrada es...