¿Cambia la complejidad de los problemas NP-hard o completos cuando su entrada está codificada unariamente?

12

¿La dificultad de un problema NP-hard o NP-complete (como se define aquí ) cambia cuando su entrada es unaria en lugar de codificada en binario?

¿Qué diferencia hay si la entrada de un problema fuertemente NP-hard está codificada de forma unaria? Quiero decir, si tomo, por ejemplo, el problema de la mochila NP-complete débilmente, es NP-complete cuando está codificado en binario, pero puede resolverse en tiempo polinómico mediante programación dinámica cuando está codificado de forma unaria. ¿Quizás tiene algunas implicaciones para la dureza de los niveles superiores de la jerarquía del tiempo polinomial?

¿La noción de fuerte ...- duro también es válida para otras clases de complejidad, por ejemplo, clases más altas de la jerarquía de tiempo polinomial?

Anteriormente hice esta pregunta en stackoverflow.com pero se señaló que es más apropiado aquí.

complexity-theory time-complexity np-complete usuario2145167
fuente
¿Debería hacer esta pregunta mejor en cstheory.stackexchange.com ? Simplemente no sabía que existía. Las respuestas aquí no van en la dirección que esperaba.
user2145167
¿Por qué no ellos? Son (por lo que puedo decir) correctas, ¿entonces tal vez su pregunta no es la que desea hacer? Además, la informática teórica es para preguntas de TCS a nivel de investigación , que ciertamente no es esta.
Raphael

Respuestas:

4

Un tamaño problemático de codificado en unario es el tamaño N y el log N si es binario. Si el tiempo empleado es F ( N ) , este es F ( tamaño ) en el primer caso y F ( tamaño 2 ) en el segundo caso. Entonces, un algoritmo que es polinómico para el primer caso probablemente será exponencial para el segundo. La codificación del problema puede cambiar radicalmente la complejidad de un algoritmo.NNlog⁡NF(N)F(size)F(2size)

vonbrand
fuente
3

No.

Si cambia la codificación de la entrada, ha cambiado la definición formal del problema, lo que significa que es un problema diferente . La complejidad del problema original no cambia, por la misma razón que señalar una luz diferente en el cielo no cambia la masa de la luna.

JeffE
fuente
2
PP1
2

La respuesta corta es que si la entrada está codificada unariamente, entonces es más larga . Es exponencialmente más largo. Ahora, un algoritmo que funciona en tiempo polinómico en el tamaño de la entrada tiene "tiempo suficiente" para resolver el problema, solo porque la entrada en sí es exponencialmente más larga que en el problema original.

Sonó.
fuente
1

Al ver más allá del problema de formulación señalado en la respuesta de JeffE, la respuesta es sí.

Considere el problema de la mochila . Tiene un algoritmo pseudo-polinomial , que es uno con tiempo de ejecución limitado por un polinomio en un número codificado en la entrada. Debido a que los valores de codificación unarios corresponden a la longitud, este es un algoritmo de tiempo polinómico para la versión unaria.

De hecho, cada problema débil de NP completo cae en esta categoría.

Rafael
fuente
Pregunta secundaria, pero nunca entendí: ¿cómo "codificas" algo en unario? ¿No necesitas un delimitador de algún tipo?
user541686
@Mehrdad Sí y no. Si; los símbolos de separación generalmente no se cuentan en este sentido, cf también input vs tape alphabet; aquí solo consideramos el tamaño del alfabeto de entrada. No; en principio, un número es suficiente para codificar tuplas y conjuntos de números contables para que no necesite símbolos de separación. Eso claramente no es útil para "trabajar" con tales máquinas, pero justifica ignorar los símbolos de separación (y otros controles).
Raphael
Hmm ... no estoy seguro de entender tu parte de "no"; ¿cómo sabrías dónde termina el número si no tuvieras un separador al final? A mí me parece un poco como lógica circular: si ignoramos los separadores, entonces efectivamente la pregunta se convierte en "si forzamos a la entrada a ocupar exponencialmente más espacio, eso cambia el tiempo de ejecución de un algoritmo exponencial en relación con el tamaño de la entrada ? " cuya respuesta es trivialmente sí ... por definición. No se trata tanto de cambiar la codificación como de agregar artificialmente bits redundantes una vez que tenga en cuenta los separadores.
user541686
@Mehrdad De acuerdo, solo estaba pensando en separar varios números entre sí. En cualquier caso, necesita marcadores finales resp. símbolos "vacíos" en máquinas Turing; de los que no puedes deshacerte. El resto se puede codificar en un número (en una penalización de tiempo de ejecución, obviamente).
Raphael