Comment savoir si un problème appartient à la classe NP?

Question

ce que je sais (pas strictement parlant): Je sais qu'il existe une question ouverte sur l'égalité des classes P et NP et tant qu'il n'y a pas d'algorithme connu qui résoudra des problèmes np dans p Temps alors nous distinguons la solvabilité spatiale de ces problèmes. De plus, je sais que vous pouvez effectuer des réductions (de temps polynomial) entre problèmes, donc si vous savez qu'un problème appartient à une certaine classe, l'autre problème appartiendra également à cette classe. En outre, je sais que l'algorithme simplex résout des problèmes de programmation linéaire

Ce que j'aimerais savoir: J'aimerais savoir comment "deviner" si un problème appartient à la classe NP. Cela a-t-il à voir avec les contraintes du problème, le nombre de contraintes, le "type" de contraintes?

Un exemple dans ce lien https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-le plus-k-times/ Nous pouvons voir un algortihm qui résolvait "Bénéfice maximum en achetant et en vendant une action au plus k fois" avec une programmation dynamique.

Cependant, si nous augmentons les contraintes. Disons que nous sommes limités à une valeur nette (nous n'avons pas d'argent illimité) ou nous pouvons acheter et vendre plus d'un stock à une époque, mais nous sommes limités à la portée des stocks que nous pouvons acheter ou vendre au moment donné. , ou il y a plusieurs stocks de différentes entreprises que nous pouvons choisir, mais nous sommes limités au nombre total de stocks que nous pouvons avoir.

Comment pouvons-nous savoir quel type de contraintes rendent le problème plus difficile et plus difficile "en mouvement" de P à la classe NP? Quels types de contraintes un problème doit être sûr que ce problème est certain de ce problème à la classe P ou NP?

Answer 1

1. Assurez-vous d'utiliser NP correctement. Dire que quelque chose appartient au NP ne dit rien, sauf qu'une solution correcte du problème peut être vérifiée rapidement.

2. de mon expérience, c'est plus sur le type de problème que quelles contraintes spécifiques que vous le donnez.
   Par exemple, Set indépendant: y compris un sommet à une extrémité du graphique peut inciter si vous pouvez prendre un sommet à l'autre extrémité du graphique. Ce type d'effets secondaires imprévisibles rend impossible de trouver un algorithme, car vous ne pouvez rien décider de votre solution car vous ne connaissez pas les implications.

au contraire est le tri: si vous utilisez QuickSort, vous pouvez choisir un pivot et diviser les éléments en 2 parties, les plus bas et ceux plus élevés que le pivot.
De cette façon, vous avez déjà apporté le problème plus facile: vous n'avez besoin que de trier ces 2 parties et vous savez lequel d'entre eux appartient à quel côté du pivot.

Obtenir une telle manche sur un problème de NP-dur n'était pas encore réussi.

Je sais que c'était assez vague, à la fin, vous ne pouvez pas généraliser votre question. Chaque passage à un problème donné peut généralement le rendre np-dur, vous devez regarder individuellement.

Pour prouver que quelque chose est le NP-dur, vous pouvez essayer de réduire un problème connu NP-dur. Voici comment cela se fait avec la plupart d'entre eux.

Un exemple de votre question serait aussi:
Le Problème de coupe maximale est NP-DUR, mais si vous ne demandez que s'il existe une coupe de taille | E |, alors il devient facile, car il est équivalent à demander si le graphique est bipartite