• Problema
• Soluția
• Sumar

Dacă vă petreceți timpul în sau în jurul valorii de programare comunității probabil ai auzit termenul de „P versus NP” destul de frecvent. Din păcate, chiar și mulți cu pregătire formală în informatică au o înțelegere slabă a conceptului.deci, iată o explicație simplă și concisă:

problema

p vs.NP problema P vs. NP întreabă dacă fiecare problemă a cărei soluție poate fi verificată rapid de un computer poate fi rezolvată rapid și de un computer., (Wikipedia)

deci, să ne dăm seama ce înțelegem prin P și NP.problemele P sunt rezolvate cu ușurință de computere, iar problemele NP nu sunt ușor de rezolvat, dar dacă prezentați o soluție potențială, este ușor să verificați dacă este corectă sau nu.după cum puteți vedea din diagrama de mai sus, toate problemele P sunt probleme NP. Adică, dacă este ușor pentru computer să rezolve, este ușor să verificați soluția. Deci, problema P vs NP se întreabă doar dacă aceste două tipuri de probleme sunt aceleași sau dacă sunt diferite, adică că există unele probleme care sunt ușor de verificat, dar nu sunt ușor de rezolvat.,în prezent, se pare că P ≠ NP, ceea ce înseamnă că avem o mulțime de exemple de probleme la care putem verifica rapid răspunsurile potențiale, dar pe care nu le putem rezolva rapid. Să ne uităm la câteva exemple:

• un vânzător care călătorește vrea să viziteze 100 de orașe diferite conducând, începând și terminând călătoria acasă. El are o cantitate limitată de benzină, astfel încât el poate conduce doar un total de 10.000 de kilometri. Vrea să știe dacă poate vizita toate orașele fără să rămână fără benzină., (de la Wikipedia)
• un fermier vrea să ia pe piață 100 de pepeni de diferite mase. Trebuie să împacheteze pepenii verzi în cutii. Fiecare cutie poate ține doar 20 de kilograme fără a se rupe. Fermierul trebuie să știe dacă 10 cutii vor fi suficiente pentru ca ea să transporte toate cele 100 de pepeni pe piață. toate aceste probleme au o caracteristică comună care este cheia înțelegerii intrigii P versus NP: pentru a le rezolva, trebuie să încercați toate combinațiile.

  soluția

  acesta este motivul pentru care răspunsul la p vs., Problema NP este atât de interesantă pentru oameni. Dacă cineva ar putea arăta că P este egal cu NP, ar face ca problemele dificile din lumea reală să fie banale pentru computere.

  rezumat

  1. P vs.NP se ocupă cu diferența dintre computere fiind capabil de a rezolva rapid problemele vs. doar fiind capabil de a testa soluțiile propuse pentru corectitudine.
  2. ca atare, problema P vs. NP este căutarea unei modalități de a rezolva probleme care necesită încercarea a milioane, miliarde sau trilioane de combinații fără a fi nevoie să încercați fiecare.,
  3. rezolvarea acestei probleme ar avea efecte profunde asupra calculului și, prin urmare, asupra societății noastre.

  Feb 7, 2017 — a adăugat atribuții Wikipedia.
  martie 2, 2014-curățat o parte din explicația pentru a evita confuzia.

  Note