Esperaba que alguien pudiera explicarme por qué exactamente el problema del producto del subconjunto es fuertemente NP-duro, mientras que el problema de la suma del subconjunto es débilmente NP-duro. Subconjunto Suma: Dada y , ¿existe un subconjunto tal que .X= { x1, . . . ,
Hace un tiempo hice esta pregunta sobre Stack Overflow: Problema: la venta de Bob . Alguien sugirió publicar la pregunta aquí también. Alguien ya ha hecho una pregunta relacionada con este problema aquí: peso mínimo por debajo del bosque de la cardinalidad dada , pero, por lo que entiendo, no me...
Un conjunto de bateo de una familia S= { S1, ... , Snorte}S={S1,...,Snorte}\mathcal{S} = \{S_1, \dots, S_n\} es un subconjunto HHH de ⋃nortei = 1Syo⋃yo=1norteSyo\bigcup_{i=1}^{n} S_i tal que H∩ Syo≠ ∅H∩Syo≠∅H \cap S_i \ne \emptyset para 1 ≤ i ≤ n1≤yo≤norte1 \le i \le n . El problema para encontrar...
Esta pregunta está estrechamente relacionada con otra publicación: Transiciones de fase en problemas difíciles de NP, pero es algo diferente. Si bien esa pregunta es sobre la dureza de instancias particulares de problemas difíciles de NP, se trata de clasificar la dificultad de las mismas...
Tengo un politopo PPP definido por {x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} . Pregunta: Dado un vértice vvv de PPP , ¿existe un algoritmo de tiempo polinómico para muestrear uniformemente de los vecinos de vvv en el gráfico de PPP ? (Polinomio en la dimensión, el número de ecuaciones y...
Hice esta pregunta hace 10 días en cs.stackexchange aquí, pero no tenía ninguna respuesta. En un artículo muy famoso (en la comunidad de redes), Wang y Crowcroft presentan algunos resultados de -completitud del cálculo de ruta bajo varias restricciones aditivas / multiplicativas. El primer...
¿Cuál es la complejidad computacional del siguiente problema: dados dos complejos matrices y verifique si hay una matriz de permutación tal que: n × nnorte×norten\times nUNUNAsisiBPAGPAGPB = PA PT.si=PAGUNPAGT.B = P A P^T. Si ayuda, uno puede suponer que y son hermitianos (o incluso que y son...
Considere una colección de conjuntos F={F1,F2,…,Fn}F={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\} sobre un conjunto base U={e1,e2,…,en}U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\} donde |Fi||Fi||F_i| ≪≪\ll nnn y ei∈Fiei∈Fie_i \in F_i , y sea kkk un número entero positivo. El objetivo es encontrar otra colección...
Dado un grafo, G=(V,E)G=(V,E)G = (V, E) , quiero encontrar un óptimo -domination para . Es decir, quiero un subconjunto de tal que todos los vértices enrrrGGGSSSVVVGGG están a una distancia de como máximo rrr de algún vértice en SSS , mientras se minimiza el tamaño de SSS . De lo que he verificado...
¿Hay alguna forma de codificar una instancia de Subset Sum o el problema de partición numérica para que una solución (pequeña) a una relación entera produzca una respuesta? Si no es definitivamente, ¿en algún sentido probabilístico? Sé que LLL (y quizás PSLQ) se han utilizado con éxito moderado en...
¿Cuál es la complejidad del siguiente problema? Entrada : HHH un camino hamiltoniano en KnKnK_n R⊆[n]2R⊆[n]2R \subseteq [n]^2 un subconjunto de pares de vértices un entero positivo kkk Consulta : ¿hay una M coincidente tal que para cada ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (donde G = ( [ n ] ,...
Problema: Dado representado por un circuito booleano, genera una uniformemente aleatoria tal que (o salida si no existe tal ). ϕ : { 0 , 1 }norte→ { 0 , 1 }ϕ:{0 0,1}norte→{0 0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }norteX∈{0 0,1}nortex \in \{0,1\}^nϕ ( x ) =
Durante mucho tiempo, pensé que un problema era NP-completo si es (1) NP-hard y (2) está en NP. Sin embargo, en el famoso artículo "El método del elipsoide y sus consecuencias en la optimización combinatoria" , los autores afirman que el problema del número cromático fraccional pertenece a NP y...
Ese es un nombre que he inventado para este problema. No lo he visto descrito en ninguna parte antes. Todavía no he podido encontrar una prueba de integridad de NP ni un algoritmo de tiempo polinómico para este problema. No es un problema de tarea, está relacionado con un problema que he encontrado...
Lema: Suponiendo equivalencia eta tenemos eso (\x -> ⊥) = ⊥ :: A -> B. Prueba: ⊥ = (\x -> ⊥ x)por equivalencia eta y (\x -> ⊥ x) = (\x -> ⊥)por reducción bajo la lambda. El informe Haskell 2010, sección 6.2 especifica la seqfunción mediante dos ecuaciones: seq :: a -> b ->...
Recientemente estuve leyendo un artículo muy bueno de Valiant y Vazirani que muestra que si , entonces no puede haber un algoritmo eficiente para resolver SAT incluso bajo la promesa de que es insatisfactorio o tiene una solución única. De este modo, se demuestra que SAT no admite un algoritmo...
Como todos saben, SAT está completo para wrt polinomial-tiempo muchas reducciones de uno. Todavía está completo wrt reducciones muchos-uno.N PnortePAG\mathsf{NP}A C0 0UNC0 0\mathsf{AC^0} Mi pregunta es ¿cuál es la profundidad mínima requerida para las reducciones? Más formalmente, ¿Cuál es la...
¿Qué tan difícil es encontrar la solución más escasa para un sistema de ecuaciones lineales? Más formalmente, considere el siguiente problema de decisión: Instancia: Un sistema de ecuaciones lineales con coeficientes enteros y un número CCc . Pregunta: ¿Existe una solución para el sistema con al...
El problema del ciclo hamiltoniano (HC) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico no dirigido dado. El problema del vendedor ambulante (TSP) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico ponderado de borde dado y minimice la...
Aquí está el problema: Tenemos un cuadrado con algunos números de 1..N en algunas celdas. Es necesario para determinar si se puede completar en un cuadrado mágico. Ejemplos: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ ¿Es este problema...