É este “Válido matemática expressão” problema P, ou NP?

Question

Esta questão é puramente por curiosidade. Estou de folga da escola para o verão, e estava indo para implementar um algoritmo para resolver este apenas por diversão. Isso levou à pergunta acima, quão difícil é este problema?

O problema: você é dado uma lista de números inteiros positivos, um conjunto de operadores matemáticos e o sinal de igual (=). você pode criar uma expressão matemática válida usando os números inteiros (na mesma ordem) e os operadores (qualquer número de vezes)?

Um exemplo deve esclarecer quaisquer dúvidas:

dada: {2, 3, 5, 25}, {+, -, *, /}, {=}
Saída: YES

a expressão (apenas um eu acho) é (2 + 3) * 5 = 25. você só precisa de saída SIM / NÃO.

Eu acredito que o problema está em NP. Digo isto porque é um problema de decisão (resposta sim / não) e eu posso encontrar um algoritmo de tempo poly não determinística que decide isso.

a. não-determinística seleccionar uma sequência de operadores para o lugar entre os números inteiros.
b. verificar se você responder é uma expressão matemática válido (isso pode ser feito em constante Tempo).

Neste caso, a grande questão é esta: é o problema em P? (Ou seja Existe um algoritmo de tempo poli determinista que decide isso?) Ou o problema é NP completo? (Ou seja, pode um problema completa conhecida NP ser reduzida a isso? Ou equivalentemente É cada NP linguagem poli reducable tempo para este problema?) Ou nenhum dos dois? (Problema ou seja, na NP, mas não NP Complete)

Nota: Esta declaração do problema assume P não é igual a NP. Além disso, embora eu sou novo para estouro de pilha, eu estou familiarizado com a tag lição de casa. Este é realmente apenas uma curiosidade, não lição de casa:)

Answer 1

Uma redução direta do problema Partition (que é NP-Completo) - dado um conjunto de N inteiros S, a entrada para o problema "válido matemática" seria - os elementos de S, N-2 operadores '+' e um '=' sinal.

Answer 2

Parece haver algum tipo de confusão sobre como verificar NP-completude. problema um NP-completo é pelo menos tão duro, em um sentido particular, como qualquer outro problema em NP. Suponha que estavam comparando a 3SAT, como alguns cartazes estão tentando fazer.

Agora, reduzindo o problema dado a 3SAT não prova nada. É então verdade que, se 3SAT pode ser resolver de forma eficiente (ou seja, P = NP), o problema dado pode ser resolvido de forma eficiente. No entanto, se o problema dado pode ser resolvido de forma eficiente, então talvez isso corresponde apenas a simples casos especiais de 3SAT.

Nós teria de reduzir 3SAT para o problema dado. Isso significa que teríamos que fazer uma regra para transformar problemas 3sat arbitrários para exemplos do problema dado, de tal forma que a solução do problema dado que nos dizem como resolver o problema 3SAT. Isto significa que 3SAT não poderia ser mais difícil do que o problema dado. Desde 3SAT é o mais difícil possível, então o problema dado também deve ser o mais difícil possível.

A redução do problema de partição funciona. Esse problema funciona assim: dado um S multiset de inteiros, podemos dividir isso em dois subconjuntos disjuntos que entre eles incluem cada membro da S, de modo que as somas dos subconjuntos disjuntos são iguais

?

Para fazer isto, construímos um início de sequência com 0, contendo cada elemento de S, e, em seguida, 0. Nós usamos {+, -} como o conjunto de operação. Isto significa que cada elemento de S deverá ser adicionado ou subtraído para total a 0, o que significa que a soma dos elementos adicionados é a mesma que a soma dos elementos subtraídos.

Portanto, esse problema é pelo menos tão duro como o problema de partição, uma vez que pode resolver um exemplo de programa Partition se podemos resolver o dado, e por isso é NP-completo.

Answer 3

OK, em primeiro lugar, você especificar "set" de inteiros, mas um conjunto é, por definição, não ordenada, para que significa uma "lista" de inteiros.

Além disso, eu vou fazer uma suposição aqui que pode estar errado, o que é que o sinal = sempre aparece exatamente uma vez, entre a penúltima ea última inteiro em sua lista. Se você permitir que o sinal de igual no meio, torna-se mais complicado.

Aqui é uma prova real de que "Expressão matemática válido" (VME) é NP completa. Podemos fazer uma redução de subconjunto soma . NOTA que a definição de soma subconjunto da Wikipedia exige que o subconjunto não é vazio. Na verdade, se é verdade que o problema mais geral de soma subconjunto permitindo subconjuntos vazios é NP completa, se a soma desejada é também parte da entrada. Eu não vou dar essa prova a menos que solicitado. Dado o exemplo de {i_1, i_2, ..., i_n} soma subconjunto, juntamente com s soma desejado, criar o seguinte exemplo de VME:

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

Se a instância de soma subconjunto tem solução, então existe algum subconjunto dos inteiros que adiciona a 0. Se o i1 inteiro é parte do montante, adicioná-lo com o seu correspondente zero (imediatamente à esquerda) e se i1 não faz parte da soma, multiplicá-lo. Entre cada zero e o termo para a direita, insira um sinal disso.

Tomando o exemplo Wikipedia

{−7, −3, −2, 5, 8}

onde somas { −3, −2, 5} a 0, gostaríamos de codificá-lo como

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

e a expressão resultante seria

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

Agora nós também precisa mostrar que qualquer solução para esta instância de resultados VME em uma solução para o caso de soma subconjunto. Isto é mais fácil do que você pensa. Quando se olha para uma expressão resultante, que podem agrupar os números para aqueles que são multiplicados com um 0 (incluindo como parte de uma cadeia de multiplicação) e aqueles que não são. Qualquer número que é multiplicado com um zero não está incluído na soma final. Qualquer número que não é multiplicado com um zero deve ser adicionado na soma final.

Assim, temos mostrado que esta instância do VME tem solução se e somente se a instância correspondente da soma subconjunto tem solução, então a redução está completa.

EDIT: A redução de partição (com o comentário) funciona tão bem, e é melhor porque permite que você coloque a qualquer sinal de igual. ! Neat

Answer 4

não têm o tempo para a resposta completa agora, mas você pode descrever uma redução deste problema com o Problema da mochila .

Usando dinâmica de programação que você pode conseguir pseudo-polinomial solução de tempo. Note-se que esta não conflito com o fato de que o problema é realmente NP completa.

Answer 5

Há duas propriedades que precisam ser satisfeitas para que seja NP completa.

A decisão problema C é NP-completo se:

1. C está em NP e
2. Cada problema em NP é redutível a C em tempo polinomial.

Nós estabelecemos 1. 2 resultados do fato de que todos os problemas em NP é redutível a 3SAT e 3SAT é redutível ao problema atual.

Por isso, é NP-completo.

(edit) Resposta ao comentário abaixo:

Vou provar que SAT é redutível ao problema atual, e uma vez que 3SAT é redutível a SAT, o resultado segue.

fórmula de entrada é a conjunção das seguintes expressões:

(X ₁ V x ₂ V x ₃ V ... x _n V y ₁ )

(X ₁ V x ₂ V x ₃ V ... x _n V y ₂ )

(X ₁ V x ₂ V x ₃ V ... x _n V y ₃ )

.

.

.

(X ₁ V x ₂ V x ₃ V ... x _n V y ₆₄ )

em que cada y _i é um booleano com base no que a ordem dos operadores aplicados entre todos os X _i 's é. isto é, y _i pode ter um total de 4x4x4x4x1 valores (assumindo que apenas +, -, x, / são os operadores e = é sempre a última operador, o que pode ser alterada, se o terminal do operador é modificado para incluir outros operadores)

Se nenhuma das expressões for verdade, então a expressão completa será avaliada como FALSE, e não há maneira de verificar a menos que substituir todos os valores possíveis, ou seja, x ₁ através x _n como os números de N e Y ₁ por y ₆₄ como as diversas formas em que os operadores podem ser aplicadas (Este cuida de ordem)

Esta conversão é em POLY-tempo, e a dada fórmula booleana é satisfatível sse a expressão matemática é válido, etc.

Aviso Qualquer uma falha?

Answer 6

Isto não é realmente uma resposta à sua pergunta complexidade, mas seu problema soa um pouco como o problema da contagem regressiva . Uma rápida pesquisa apareceu neste artigo: http: //www.cs.nott .ac.uk / ~ gmh / countdown.pdf

Answer 7

Eu não tenho que tempo para trabalhar fora uma prova no momento, mas um palpite me diz que ele não pode estar em P. você pode definir uma gramática para a aritmética, e, em seguida, esta questão equivale a encontrar se há uma árvore de análise válido que usa todos estes terminais. i acreditam que esse problema está em NP mas fora da P.