Preguntas etiquetadas con np-hardness

La redacción exacta del título se debe a Anand Kulkarni (quien propuso que se creara este sitio). Esta pregunta se hizo como una pregunta de ejemplo, pero tengo una curiosidad increíble. Sé muy poco acerca de la geometría algebraica y, de hecho, solo tengo una comprensión superficial y de pregrado...

Esto está en la línea de " Algoritmos del libro ". Aunque las reducciones también son algoritmos, pensé que era dudoso pensar en una reducción en respuesta a la pregunta sobre los algoritmos del libro. Por lo tanto, una consulta por separado! Las reducciones de todo tipo son bienvenidas....

Estaba leyendo " ¿Es P versus NP formalmente independiente? ", Pero me desconcertó. Se cree ampliamente en la teoría de la complejidad que . Mi pregunta es sobre qué pasa si esto no es demostrable (digamos en ). (Supongamos que solo descubrimos que es independiente de pero no hay más información...

Deje que las variables sean . La distancia entre dos variables se define como. La distancia entre dos literales es la distancia entre las dos variables correspondientes. d ( x a , x b ) = | a - b |x1,x2,x3...xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nd(xa,xb)=|a−b|d(xa,xb)=|a−b|d(x_a , x_b) =...

Estoy considerando clases de gráficos que pueden caracterizarse por subgrafos prohibidos. Si una clase de gráfico tiene un conjunto finito de subgrafos prohibidos, entonces hay un algoritmo de reconocimiento de tiempo polinómico trivial (uno puede usar la fuerza bruta). Pero una familia infinita...

Muchos problemas de gráficos algorítmicos se pueden resolver en tiempo polinómico tanto en gráficos no ponderados como ponderados. Algunos ejemplos son la ruta más corta, el árbol de expansión mínimo, la ruta más larga (en gráficos acíclicos dirigidos), flujo máximo, corte mínimo, coincidencia...

Los gráficos cúbicos son gráficos en los que cada vértice tiene grado 3. Se han estudiado ampliamente y soy consciente de que varios problemas NP-hard siguen siendo NP-hard incluso restringidos a subclases de gráficos cúbicos, pero otros se vuelven más fáciles. Una superclase de gráficos cúbicos es...

Si un problema es NP-hard (usando reducciones de tiempo polinomiales), ¿eso implica que es P-hard (usando espacio de registro o reducciones NC)? Parece intuitivo que si es tan difícil como cualquier problema en NP, debería ser tan difícil como cualquier problema en P, pero no veo cómo encadenar las...

Motivado por la respuesta de Shor relacionada con diferentes nociones de integridad de NP, estoy buscando un problema que es NP completo bajo las reducciones de P pero no se sabe que es NP completo bajo las reducciones de Logspace (preferiblemente durante mucho tiempo). Además, ¿es más difícil...

Recientemente, pasé por la experiencia divertida y dolorosa de explicar informalmente el concepto de complejidad computacional a un programador autodidacta joven y talentoso, que nunca antes había tomado un curso formal sobre algoritmos o complejidad. No es sorprendente que muchas nociones...

Shor declaró, en su comentario a la respuesta anónima de los alces a esta pregunta ¿Puedes identificar la suma de dos permutaciones en el tiempo polinómico? , que es completo para identificar la diferencia de dos permutaciones. Desafortunadamente, no veo una reducción directa del problema de la...

Ya publiqué esta pregunta hace un tiempo en MathOverflow , pero que yo sepa, todavía está abierta, así que la vuelvo a publicar aquí con la esperanza de que alguien haya oído hablar de ella. Planteamiento del problema Supongamos que , y son tres particiones en partes no vacías (denotadas por 's,...

¿Cuál es la relación entre los algoritmos de ADN y las clases de complejidad definidas usando las máquinas de Turing? ¿A qué corresponden las medidas de complejidad como el tiempo y el espacio en los algoritmos de ADN? ¿Se pueden usar para resolver casos de problemas NP-completos como TSP que las...

En esta pregunta , parece que hemos identificado un problema natural que es NP completo bajo reducciones aleatorias, pero posiblemente no bajo reducciones deterministas (aunque esto depende de qué suposiciones no comprobadas en la teoría de números sean verdaderas). ¿Hay algún otro problema...

Supongamos que tenemos una matriz n por n. ¿Es posible reordenar sus filas y columnas de manera que obtengamos una matriz triangular superior? Esta pregunta está motivada por este problema: ordenamiento topológico positivo El problema de decisión original es al menos tan difícil como este, por...

(Esta pregunta es un poco una "encuesta"). Actualmente estoy trabajando en un problema en el que trato de dividir los bordes de un torneo en dos conjuntos, los cuales son necesarios para cumplir con algunas propiedades estructurales. El problema "se siente" bastante difícil, y espero que sea...

El siguiente problema interesante surgió en mi investigación recientemente: INSTANCIA: Gráfico .G ( V, E)G(V,E)G(V, E) SOLUCIÓN: Una finalización de ciclo impar sin acordes, definida como un superconjunto del conjunto de bordes E, de modo que el gráfico completado G ' ( V , E ' ) tiene la...

Una cadena de suma es una secuencia de enteros positivos donde y cada índice , tenemos para algunos índices . La longitud de la cadena de adición es ; El objetivo de la cadena de suma es .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i n(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)x1=1x1=1x_1 =...

En su artículo (p. 503), Garey y Johnson comentan: ... podría existir un problema de NP-completo que no es NP-completo en sentido estricto ni resuelto por un algoritmo de tiempo pseudo-polinomial ... ¿Alguien sabe algunos problemas candidatos con las propiedades mencionadas...

Feedback Vertex Set es NP-complete para gráficos generales. Se sabe que es NP-completo para gráficos limitados de grado 8 debido a una reducción de la cubierta del vértice. El artículo de Wikipedia dice que es polisoluble para gráficos limitados de grado 3 y NP-completo para gráficos limitados de...