Preguntas etiquetadas con reductions

En computabilidad y complejidad, encontrar mapeos entre problemas que permiten resolver un problema utilizando una solución de otro. Para la reducción en la teoría del lenguaje de programación (por ejemplo, reducción beta), consulte [cálculo lambda] o [reescritura de términos].

28
¿Por qué el tipo de vacío de C no es análogo al tipo vacío / inferior?

Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...

24
Ordenar como un programa lineal

Un sorprendente número de problemas tiene reducciones bastante naturales a la programación lineal (LP). Consulte el Capítulo 7 de [1] para ver ejemplos como flujos de red, emparejamiento bipartito, juegos de suma cero, rutas más cortas, una forma de regresión lineal e incluso evaluación de...

21
Reduce el siguiente problema a SAT

Aquí está el problema. Dado , donde cada T i ⊆ { 1 , ... , n } . ¿Hay un subconjunto S ⊆ { 1 , ... , n } con un tamaño máximo de k tal que S ∩ T i ≠ ∅ para todo i ? Estoy tratando de reducir este problema a SAT. Mi idea de una solución sería tener una variable x ik , n , T1, ... ,...

20
MEDIA CLIQUE - NP Completa el problema

Permítanme comenzar señalando que este es un problema de tarea, por favor brinden solo consejos y observaciones relacionadas, NO RESPUESTAS DIRECTAS por favor . Dicho esto, aquí está el problema que estoy viendo: Deje HALF-CLIQUE = { | es un gráfico no dirigido que tiene una subgrafía completa...

15
¿Está completo el NP de Hidoku?

Un Hidoku es una cuadrícula con algunos enteros precompletados de 1 a n 2 . El objetivo es encontrar un camino de enteros sucesivos (de 1 an×nn×nn \times nn2n2n^2 ) en la cuadrícula. Más concretamente, cada celda de la cuadrícula debe contener un número entero diferente de 1 a n 2 y cada celda con...

15
Si P = NP, ¿por qué

Aparentemente, si P=NPP=NP{\sf P}={\sf NP} , todos los idiomas en PP{\sf P} excepto ∅∅\emptyset y Σ∗Σ∗\Sigma^* serían NPNP{\sf NP} -completos. ¿Por qué estos dos idiomas en particular? ¿No podemos reducir a ellos otro lenguaje en PP{\sf P} al enviarlos al aceptar o no...