Preguntas etiquetadas con p-hardness

128
Problemas entre P y NPC

La factorización y el isomorfismo gráfico son problemas en NP que no se sabe que están en P ni en NP-Completo. ¿Cuáles son algunos otros problemas naturales (suficientemente diferentes) que comparten esta propiedad? Los ejemplos artificiales que provienen directamente de la prueba del teorema de...

66
¿Son los problemas completos

En la actualidad, no es factible resolver un problema completo o un problema completo P S P A C E en el caso general de entradas grandes. Sin embargo, ambos se pueden resolver en tiempo exponencial y espacio polinómico.nortePAGSNPNPPAGSSPAGSA CmiPSPACEPSPACE Dado que no podemos construir...

47
Problemas NP-duros en los árboles

Varios problemas de optimización que se sabe que son NP-hard en los gráficos generales se pueden resolver trivialmente en tiempo polinómico (algunos incluso en tiempo lineal) cuando el gráfico de entrada es un árbol. Los ejemplos incluyen cobertura mínima de vértice, conjunto independiente máximo,...

45
Una variante de factorización NP-completa.

El libro de Arora y Barak presenta el factoring como el siguiente problema: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORIZACIÓN={⟨L,U,norte⟩El |(∃ un primer pags∈{L,...,U})[pagsEl |norte]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p...

34
Encuentros cotidianos con problemas NP-completos

Mark Dominus recolectó algunos ejemplos de reducciones de tiempo polinomial de varios problemas NP-duros a la coincidencia de "expresión regular" . Visualizar verificaciones de tiempo polinomial no es un gran salto. ¿Cómo ilustran la clase NP-complete para estudiantes universitarios o para amigos...

33
¿Referencia para la dureza NP de 3 colores?

Tengo una pregunta historica. Estoy tratando de determinar la referencia para el hecho de que la capacidad de coloración en 3 de los gráficos (alternativamente, la capacidad de coloración en para k ≥ 3 dada ) es NP-difícil.kkkk≥3k≥3k\geq 3 La respuesta tentadora es "el documento original de...