Mientras respondía esta pregunta en teoría , demostré (informalmente) sobre la marcha el siguiente teorema: Teorema : para cualquier fija, la sonda del ciclo hamiltoniano permanece completa NP incluso si está restringida a gráficos bipartitos planos no direccionados de grado máximo 3 que no...
Sudoku es un rompecabezas bien conocido que es NP completo. Sudoku binario es una variante que solo permite los números y 1 . Las reglas son las siguientes.000111 Cada fila y cada columna deben contener un número igual de ceros y unos. Cada fila y cada columna es única. Ninguna fila o columna...
Esta pregunta está motivada por esta publicación, ¿Puedes identificar la suma de dos permutaciones en el tiempo polinómico? , y mi interés en las propiedades computacionales de las permutaciones. Una secuencia de diferencias de una permutación π de los números 1 , 2 , ... n + 1 se forma al...
En un gráfico dirigido, , F ⊂ E , si G ∖ F es un DAG (gráfico acíclico dirigido), F se llama un conjunto de arco de retroalimentación. G = ( V, E)G=(V,E)G=(V,E)F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Si cada borde está asociado con un peso , el problema del conjunto de arco de retroalimentación...
Me pregunto si las clases de NPC definidas por muchas reducciones y las reducciones de Turing son iguales. Editar: Otra pregunta, ¿las reducciones de Turing solo están colapsando las clases C y co-C para algunos C o hay una clase , ya que existe un problema que no está en bajo la reducción de Karp...
En un gráfico, un conjunto independiente es un subconjunto de vértices que no contiene un borde como un subgráfico inducido. El problema de encontrar conjuntos independientes más grandes en un gráfico es una pregunta algorítmica fundamental, y difícil de resolver. Consideremos la cuestión más...
En la complejidad parametrizada, las personas utilizan la reducción de parámetros fijos manejables (FPT) para demostrar la dureza W [t]. Teóricamente, una reducción de FPT no es una reducción de tiempo polinomial, ya que puede ejecutarse exponencialmente en el parámetro k. Pero en la práctica,...
Esta pregunta fue motivada por una pregunta hecha en stackoverflow . Supongamos que se le da un árbol enraizado (es decir, hay una raíz y los nodos tienen hijos, etc.) en n nodos (etiquetados 1 , 2 , ... , n ).TTTnortenn1 , 2 , ... , n1,2,…,n1, 2, \dots, n Cada vértice tiene un peso entero no...
Nurikabe es un rompecabezas de relleno de cuadrícula basado en restricciones, más o menos similar al Buscaminas / Nonogramas; los números se colocan en una cuadrícula que se debe llenar con valores de activación / desactivación para cada celda, con cada número que indica una región de celdas...
Estoy interesado en una variación SAT donde la fórmula CNF es monótona (no se niegan variables). Tal fórmula es obviamente satisfactoria. Pero digamos que el número de variables verdaderas es una medida de cuán buena es nuestra solución. Entonces tenemos el siguiente problema: MÍNIMO VERDADERO...
Esta pregunta puede no ser técnica. Como hablante no nativo y TA para la clase de algoritmo, siempre me pregunté qué significa gadget en 'gadget de cláusula' o 'gadget variable'. El diccionario dice que un gadget es una máquina o un dispositivo, pero no estoy seguro de qué significado coloquial...
El problema de la partición de 3 cliques es el problema de determinar si los vértices de un gráfico, digamos , se pueden dividir en 3 camarillas. Este problema es NP-duro por una simple reducción del problema de 3 colorabilidad. No es difícil ver que la respuesta a este problema es fácil cuando...
Esto es similar a SAT, excepto que conocemos la asignación de cada variable, pero no conocemos la asignación de ningún operador booleano. En ese caso, ¿encontrar la asignación de cada operador para que la expresión evalúe un valor booleano dado es un problema NPC? En realidad, me preguntaba si...
El problema de N-queen es este: Entrada: N Salida: una colocación de N "reinas" en un tablero de ajedrez de NXN de modo que no haya dos reinas en la misma fila, columna o diagonal. Al hacer una búsqueda en Google sobre esto, descubrí que muchas diapositivas de muchos profesores afirman que este...
Estaba pensando a qué clase pertenece este lenguaje: es un gráfico, es un número natural es el número cromático deL={⟨G,k⟩∣GL={⟨G,k⟩∣GL =\{ \langle G,k \rangle \mid G kkkkkkG}G}G\} Pensé en como (1) "no hay coloración de k-1 colores" y (2) "hay coloración de colores". Ahora, (1) es coNP y (2)...
¿Hay alguna con las siguientes propiedades:L ∈ N PL∈NPL\in {\bf NP} Se sabe que implica P = N P .L ∈ PL∈PL\in {\bf P}P = N PP=NP{\bf P}={\bf NP} No hay (conocido) tiempo polinómico reducción Turing de (o algún otro N P problema -Complete) a L .SA TSATSATN PNP{\bf NP}LLL En otras palabras, si un...
Estoy buscando problemas NP-hard para una reducción. Hasta ahora he encontrado los siguientes problemas: Problema de 3 particiones problema de embalaje Emparejamiento numérico tridimensional TSP Cualquier problema de NP completo sin datos numéricos, por ejemplo, SATISFIABILIDAD, CICLO...
¿Se ha estudiado este problema antes? Dado un gráfico métrico no dirigido G (las longitudes de los bordes satisfacen la desigualdad del triángulo), encuentre un conjunto S de vértices tal que MST (G [S]) se maximice, donde MST (G [S]) es el árbol de expansión mínimo del subgráfico inducido por S....
En primer lugar, mi comprensión del teorema de incompletitud de Gödel (y la lógica formal en general) es muy ingenua, también es mi conocimiento en informática teórica (lo que significa que solo tomé un curso de posgrado mientras aún estoy en la universidad), por lo que esta pregunta puede ser Muy...
¿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....