Est-ce que “Valide l'expression mathématique du problème” P ou NP?

https://stackoverflow.com/questions/975626

13-09-2019
|

Question

Cette question est purement de la curiosité.Je suis hors de l'école pour l'été, et qu'il allait mettre en œuvre un algorithme pour résoudre ce juste pour le fun.Qui a conduit à la question ci-dessus, est-ce difficile problème?

Le problème:on vous donne une liste de nombres entiers positifs, un ensemble d'opérateurs mathématiques et le signe égal(=).pouvez-vous créer un valide expression mathématique à l'aide de nombres entiers (dans le même ordre) et les opérateurs (nombre de fois)?

Un exemple devrait clarifier toutes les questions:

donnée:{2, 3, 5, 25} , {+, -, *, /} , {=}
sortie:OUI

l'expression (le seul je pense) est (2 + 3) * 5 = 25.vous avez seulement besoin de sortie OUI/NON.

Je crois que le problème est dans NP.Je dis cela parce que c'est un problème de décision (OUI/NON-réponse) et je peux trouver un non-déterministe poly temps de l'algorithme qui décide.

un.non-déterministe sélectionnez une séquence d'opérateurs de place entre les nombres entiers.
b.vérifiez que vous avez la réponse est valide expression mathématique (ce qui peut être fait en constante de temps).

Dans ce cas, la grande question est:est-ceLe problème est dans P?(c'est à direEst-il déterministe poly temps de l'algorithme qui décide de cela?) OU Est le problème NP complet?(c'est à direPeut connu NP problème être réduit à cela?ou, de manière équivalente Est chaque NP langue poly temps réductible à ce problème?) OU aucun des deux?(c'est à direproblème dans NP, mais pas NP Complet)

Note:Cet énoncé du problème suppose P pas égal à NP.Aussi, bien que je suis nouveau à Débordement de Pile, je suis familier avec les devoirs de la balise.C'est en effet juste de la curiosité, pas de devoirs :)

La solution

Une réduction directe des (qui est NP-complet) - donné une ensemble de N nombres entiers S, l'entrée du problème « Math Valid » serait - les éléments de S, N-2 « + » opérateurs et un signe « = ».

Autres conseils

Il semble y avoir une sorte de confusion sur la façon de vérifier NP-complet. Un problème NP-complet est au moins aussi difficile, dans un sens particulier, comme tout autre problème dans NP. Supposons que nous comparions à 3SAT, comme des affiches tentent de le faire.

Maintenant, ce qui réduit le problème donné à 3SAT ne prouve rien. Il est donc vrai que, si 3SAT peut être résoudre efficacement (ce qui signifie P = NP), le problème donné peut être résolu efficacement. Toutefois, si le problème donné peut être résolu efficacement, alors peut-être il ne correspond qu'à des cas particuliers facile de 3SAT.

Il faudrait réduire 3SAT au problème donné. Cela signifie que nous devrions faire une règle pour transformer les problèmes 3sat arbitraires à des exemples du problème donné, de telle sorte que la solution du problème donné nous apprendrait comment résoudre le problème 3SAT. Cela signifie que 3SAT ne pouvait pas être plus dur que le problème donné. Depuis 3SAT est le plus dur possible, le problème donné doit être le plus dur possible.

La réduction du problème de la partition fonctionne. Ce problème fonctionne comme ceci: étant donné un multiset S d'entiers, peut-on diviser en deux sous-ensembles disjoints entre eux comprennent chaque membre de S, de sorte que les sommes des sous-ensembles disjoints sont égaux

Pour ce faire, nous avons construit une séquence commençant par 0, contenant chaque élément de S, puis 0. Nous utilisons {+, -} comme l'ensemble de l'opération. Cela signifie que chaque élément de S est soit ajouté ou soustrait un total de 0, ce qui signifie que la somme des éléments ajoutés est la même que la somme des éléments soustraites.

Par conséquent, ce problème est au moins aussi dur que le problème de la partition, puisque nous pouvons résoudre un exemple de programme de partition si nous pouvons résoudre le recevoir un, et est donc NP-complet.

OK, tout d'abord, vous spécifiez « set » d'entiers, mais un ensemble est par définition non ordonnée, de sorte que vous voulez dire une « liste » des entiers.

En outre, je vais faire une hypothèse ici qui peut se tromper, ce qui est que le signe = toujours apparaît exactement une fois, entre la deuxième à la dernière et le dernier entier sur votre liste. Si vous permettez le signe égal au milieu, il devient plus compliqué.

Voici une preuve réelle que « Expression mathématique valide » (VME) est NP complet. Nous pouvons faire une réduction de somme Subset. Notez que la définition de Wikipedia de somme sous-ensemble exige que le sous-ensemble est non vide. En fait, il est vrai que le problème plus général de la somme des sous-ensembles permettant des sous-ensembles vides est NP complet, si la somme désirée fait également partie de l'entrée. Je ne donnerai pas cette preuve, sauf sur demande. Compte tenu de l'exemple de la somme de sous-ensembles {i_1, i_2, ..., i_n} avec s somme désirée, créer l'instance suivante de VME:

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

Si l'instance de somme sous-ensemble est résoluble, alors il y a un sous-ensemble des entiers qui ajoute à 0. Si l'entier i1 fait partie de la somme, ajoutez-le avec son correspondant zéro (immédiatement à gauche) et si i1 ne fait pas partie de la somme, le multiplier. Entre chaque zéro et le terme à droite, insérez un signe d'addition.

Prenons l'exemple de Wikipedia

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

où des sommes { −3, −2, 5} à 0, nous encoder comme

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

et l'expression résultante serait

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

Maintenant, nous devons aussi montrer que toute solution à cette instance de VME aboutit à une solution à l'instance de somme sous-ensemble. Cela est plus facile que vous le pensez. Quand on regarde une expression qui en résulte, nous pouvons regrouper les nombres dans ceux qui sont multipliés par un 0 (y compris dans le cadre d'une multiplication de la chaîne) et ceux qui ne sont pas. Tout nombre est multiplié par un zéro est pas inclus dans la somme finale. Tout nombre ne se multiplie pas par un zéro, il faut ajouter à la somme finale.

Nous avons montré que cette instance de VME est résoluble si et seulement si l'instance correspondante de somme sous-ensemble est résoluble, de sorte que la réduction est terminée.

EDIT: La réduction de la partition (avec le commentaire) fonctionne aussi bien, et est meilleur parce qu'il vous permet de mettre le signe égal partout. Neat!

Ne pas avoir le temps pour la réponse complète en ce moment, mais vous pouvez décrire une réduction de ce problème à la problème Knapsack.

En utilisant la programmation dynamique, vous pouvez obtenir pseudo-polynomiale Solution de temps. Notez que ce ne sont pas en conflit avec le fait que le problème est en effet NP complet.

Il y a deux propriétés qui doivent être remplies pour qu'il soit NP Complet.

Un problème de décision, C est NP-complet si:

C est dans NP, et
Chaque problème dans NP est réductible à C en temps polynomial.

Nous avons établi 1.2 résultats par le fait que chaque problème dans NP est réductible à 3SAT et 3SAT est réductible au problème actuel.

Par conséquent, il est NP-complet.

(edit) Réponse au commentaire ci-dessous:

Je vais prouver que la SAT est réductible au problème actuel, et depuis 3SAT est réductible à la SAT, le résultat suit.

Entrée de la formule est la conjonction des expressions suivantes:

(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₆₄)

où chacun y_j' est un booléen basé sur ce que l'ordre des opérateurs appliquée entre tous les x_j's 'est.c'est à dire, y_j' peut prendre un total de 4x4x4x4x1 valeurs (en supposant que seulement +, -, x, / sont les opérateurs et = est toujours le dernier exploitant;elle peut être modifiée si l'opérateur mis est modifié pour inclure d'autres opérateurs)

Si aucune des expressions est vraie, alors l'expression complète sera à FALSE, et il n'y a aucun moyen de vérifier, à moins que nous remplacer toutes les valeurs possibles, j'.e, x₁ par le biais de x_n comme les nombres n et y₁ par y₆₄ les différentes façons dans lequel les opérateurs peuvent être appliquées (Ce qui prend soin de la commande)

Cette conversion est en POLY-temps, et la formule booléenne est satisfiable ssi l'expression mathématique est valide, etc.

On remarque une faille?

Ce n'est pas vraiment une réponse à votre question de la complexité, mais votre problème semble un peu comme le http: //www.cs.nott .ac.uk / ~ GMH / countdown.pdf

Je n'ai pas le temps de trouver une preuve pour le moment, mais une intuition me dit qu'il ne peut pas être dans P., vous pouvez définir une grammaire pour l'arithmétique, et cette question revient à trouver s'il y a un arbre d'analyse syntaxique valide qui utilise tous ces terminaux. i croire que ce problème est NP mais en dehors de P.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow