Es este “Válido expresión matemática” problema P o NP?
https://stackoverflow.com/questions/975626
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esta pregunta es puramente por curiosidad. Estoy fuera de la escuela durante el verano, y que iba a aplicar un algoritmo para resolver este sólo por diversión. Eso llevó a la pregunta anterior, lo difícil es este problema?
El problema: se le da una lista de números enteros positivos, un conjunto de operadores matemáticos y el signo igual (=). se puede crear una expresión matemática válida usando los números enteros (en el mismo orden) y los operadores (cualquier número de veces)?
Un ejemplo se debe aclarar cualquier duda:
dado: {2, 3, 5, 25}, {+, -, *, /}, {=}
salida: YES
la expresión (sólo uno creo) es (2 + 3) * 5 = 25 sólo es necesario para la salida SÍ / NO.
Creo que el problema está en NP. Digo esto porque se trata de un problema de decisión (respuesta sí / no) y puedo encontrar un algoritmo de tiempo poli no determinista que lo decida.
a. de manera no determinista seleccionar una secuencia de operadores para colocar entre los números enteros.
si. verificar su respuesta es una expresión matemática válida (esto se puede hacer en constante
hora).
En este caso, la gran pregunta es la siguiente: ¿Es el problema de P? (Es decir, ¿Hay un algoritmo de tiempo poli determinista que decide que?) O es el problema NP completo? (Es decir, ¿Puede un conocido problema NP completo se reduce a esto? O equivalentemente Es cada vez poli lenguaje NP reducible a este problema?) O ninguno? (Es decir, un problema en NP pero no NP completo)
Nota: Este planteamiento del problema asume P no es igual a NP. También, aunque soy nuevo en desbordamiento de pila, estoy familiarizado con la etiqueta tarea. Este es de hecho simplemente curiosidad, no tareas:)
Otros consejos
Parece que hay algún tipo de confusión acerca de cómo verificar la NP-completitud. Un problema NP-completo es al menos tan duro, en un sentido particular, como cualquier otro problema en NP. Supongamos que comparábamos a 3SAT, como algunos carteles están tratando de hacer.
Ahora, lo que reduce el problema dado a 3SAT prueba nada. Es entonces cierto que, si 3SAT se puede resolver de manera eficiente (es decir, P = NP), el problema dado puede ser resuelto de manera eficiente. Sin embargo, si el problema dado puede ser resuelto de manera eficiente, entonces tal vez corresponde únicamente a los casos especiales fáciles de 3SAT.
Nos tendríamos que reducir 3SAT al problema dado. Esto significa que tendríamos que hacer una regla para transformar los problemas arbitrarias 3SAT a ejemplos del problema dado, de tal manera que la solución del problema dado nos indican cómo resolver el problema 3SAT. Esto significa que 3SAT no podía ser más duro que el problema dado. Desde 3SAT es el más duro posible, entonces el problema dado también debe ser la más difícil posible.
La reducción del problema de la partición funciona. Ese problema funciona así:? Dado un conjunto múltiple S de enteros, podemos dividirlo en dos subconjuntos disjuntos que entre ellos incluye cada miembro de S, de tal manera que las sumas de los subconjuntos disjuntos son iguales
Para hacer esto, se construye una secuencia que comienza con 0, que contiene cada elemento de S, y luego 0. Utilizamos {+, -} como el conjunto operación. Esto significa que cada elemento de S se suma o se resta ya sea a un total a 0, lo que significa que la suma de los elementos añadidos es el mismo que la suma de los elementos restados.
Por lo tanto, este problema es al menos tan difícil como el problema de reparto, ya que podemos resolver un programa de ejemplo de reparto si podemos resolver la dada, y por lo tanto es NP-completo.
OK, primero, se especifica "conjunto" de los números enteros, sino un conjunto es, por definición, no ordenada, lo que significa una "lista" de los números enteros.
Además, voy a hacer una suposición aquí que puede estar equivocado, que es que el signo = siempre aparece exactamente una vez, entre el penúltimo y el último número entero en su lista. Si permite que el signo de igualdad en el medio, se hace más complicado.
Aquí es una prueba real de que "expresión matemática válido" (VME) es NP completo. Podemos hacer una reducción de subconjunto suma . NOTA que la definición de la suma de subconjuntos de Wikipedia requiere que el subconjunto no está vacío. De hecho, es cierto que el problema más general de la suma de subconjuntos permitiendo subconjuntos vacíos es NP completo, si la suma deseada es también parte de la entrada. No voy a dar esa prueba salvo que lo solicite. Dada la instancia de la suma de subconjuntos {i_1, i_2, ..., i_n} junto con s suma deseada, crear el siguiente ejemplo de VME:
{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}
Si la instancia de la suma de subconjuntos tiene solución, entonces no es un subconjunto de los enteros que se suma a 0. Si el i1 entero es parte de la suma, agregarlo con su correspondiente cero (inmediatamente a la izquierda) y si i1 no es parte de la suma, se multiplica. Entre cada uno cero y el término de la derecha, insertar un signo de adición.
Tomando el ejemplo Wikipedia
{−7, −3, −2, 5, 8}
donde sumas { −3, −2, 5} a 0, tendríamos codificarlo como
{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}
y la expresión resultante sería
{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}
Ahora también tenemos que mostrar que cualquier solución a esta instancia de VME se traduce en una solución a la instancia de la suma de subconjuntos. Esto es más fácil de lo que piensas. Cuando miramos a una expresión resultante, podemos grupo los números en los que se multiplican con un 0 (incluido como parte de una multiplicación de la cadena) y los que no lo son. Cualquier número que se multiplica por un cero no está incluido en la suma final. Cualquier número que no se multiplica con un cero se debe agregar a la suma final.
Así hemos demostrado que esta instancia de VME tiene solución si y sólo si la instancia correspondiente de la suma de subconjuntos tiene solución, por lo que la reducción es completa.
EDIT: La reducción de reparto (con el comentario) funciona tan bien, y es mejor porque le permite poner el signo igual en cualquier lugar. Neat!
No tienen el tiempo para la respuesta completa en este momento, pero se puede describir una reducción de este problema a la Problema de la mochila .
El uso de programación dinámica se puede conseguir la disolución pseudo-polinomial tiempo. Tenga en cuenta que este no está en conflicto con el hecho de que el problema es de hecho NP completo.
Hay dos propiedades que deben ser satisfechos para que sea NP completo.
Un problema de decisión C es NP-completo si:
- C está en NP, y
- Cada problema en NP es reducible a C en tiempo polinómico.
Hemos establecido 1. 2 resulta del hecho de que todos los problemas de NP se puede reducir a 3SAT y 3SAT es reducible al problema actual.
Por lo tanto, es NP-completo.
(editar) respuesta al comentario a continuación:
Voy a demostrar que el SAT es reducible al problema actual, y desde 3SAT es reducible a SAT, el resultado sigue.
fórmula de entrada es la conjunción de las siguientes expresiones:
(X 1 V x 2 V x 3 V ... x n V y 1 )
(X 1 V x 2 V x 3 V ... x n V y 2 )
(X 1 V x 2 V x 3 V ... x n V y 3 )
.
.
.
(X 1 V x 2 V x 3 V ... x n V y 64 )
donde cada Y i es un valor booleano basado en lo que el orden de los operadores aplicados entre todos los x i 's es. es decir, y i puede tomar un total de valores 4x4x4x4x1 (suponiendo que sólo +, -, x, / son los operadores y = siempre es el último operador; esto se puede cambiar si el conjunto operador se modifica para incluir otros operadores)
Si ninguna de las expresiones es verdadera, entonces la expresión completa se evalúa como FALSO, y no hay manera de comprobar a menos sustituimos todos los valores posibles, es decir, x 1 a través x n como los números N e y 1 a través de y 64 como las diversas formas en las que los operadores se pueden aplicar (Este se encarga de orden)
Esta conversión está en POLY-tiempo, y la fórmula boolean dado es satisfiable si y sólo si la expresión matemática es válido, etc.
Cualquiera que observe un defecto?
Esto no es realmente una respuesta a su pregunta complejidad, pero su problema suena un poco como el Cuenta atrás problema. Una búsqueda rápida se presentó este documento: http: //www.cs.nott .ac.uk / ~ GMH / countdown.pdf
No tengo a tiempo para elaborar una prueba en este momento, pero una corazonada me dice que puede que no sea en P. Se puede definir una gramática para la aritmética, y luego esta pregunta equivale a encontrar si hay una árbol de análisis válido que utiliza todos estos terminales. i creer que ese problema está en NP pero fuera de P.
