Preguntas etiquetadas con polynomial-time

31
¿Qué clases de programas matemáticos pueden resolverse exactamente o aproximadamente, en tiempo polinómico?

Estoy bastante confundido por la literatura de optimización continua y la literatura de TCS sobre qué tipos de programas matemáticos (continuos) (MP) se pueden resolver de manera eficiente y cuáles no. La comunidad de optimización continua parece afirmar que todos los programas convexos se pueden...

30
¿Existe un algoritmo de tiempo polinómico para determinar si el lapso de un conjunto de matrices contiene una matriz de permutación?

Me gustaría encontrar un algoritmo de tiempo polinómico que determine si el lapso de un conjunto dado de matrices contiene una matriz de permutación. Si alguien sabe si este problema es de una clase de complejidad diferente, sería igual de útil. EDITAR: He etiquetado esta pregunta con la...

21
¿Puede

Considere el lenguaje .EQUALITY={anbn∣n≥0}EQUALITY={anbn∣n≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} Se sabe que no puede ser reconocido por ninguna máquina de Turing alterna (espacio) sublogarítmico (Szepietowski, 1994) . (¡Hay un cajero automático que utiliza un espacio sublogarítmico...

14
¿Es la equivalencia eta para funciones compatible con la operación seq de Haskell?

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 ->...

13
¿Ejemplos de problemas donde los algoritmos exponenciales se ejecutan más rápido que los algoritmos polinómicos para tamaños prácticos?

¿Conoce algún problema (preferiblemente al menos algo bien conocido), donde, para un tamaño de problema práctico , un algoritmo exponencial se ejecuta mucho más rápido que una contraparte de tiempo polinomial más conocida. Por ejemplo, suponga que un problema tiene un tamaño práctico * de y hay...