- a probléma
- a megoldás
- összefoglaló
ha időt tölt a programozási közösségben vagy annak környékén, akkor valószínűleg gyakran hallja a “P versus NP” kifejezést. Sajnos még a formális számítástechnikai képzéssel rendelkezők is gyengén értik a koncepciót.
tehát itt van egy egyszerű és tömör magyarázat:
A probléma
p vs. NP a P vs. NP probléma megkérdezi, hogy minden olyan probléma, amelynek megoldását számítógép gyorsan ellenőrizheti, gyorsan megoldható-e számítógéppel is., (Wikipedia)
tehát derítsük ki, mit értünk P és NP alatt.
O a problémák könnyen megoldhatók a számítógépek, valamint NP problémák nem könnyen megoldható, de ha jelen van egy lehetséges megoldás könnyen ellenőrizze, hogy helyes-e vagy sem.
amint az a fenti ábrából látható, minden P probléma NP probléma. Vagyis, ha a számítógép könnyen megoldható, akkor könnyű ellenőrizni a megoldást. Tehát a P vs NP probléma csak azt kérdezi, hogy ez a két problématípus azonos-e, vagy más-e, azaz vannak-e olyan problémák, amelyek könnyen ellenőrizhetők, de nem könnyen megoldhatók.,
jelenleg úgy tűnik, hogy P ≠ NP, ami azt jelenti, hogy rengeteg példa van olyan problémákra, amelyekre gyorsan ellenőrizhetjük a lehetséges válaszokat, de nem tudjuk gyorsan megoldani. Nézzünk néhány példát:
- egy utazó ügynök 100 különböző várost szeretne meglátogatni vezetéssel, otthoni utazásának megkezdésével és befejezésével. Korlátozott mennyiségű benzinnel rendelkezik, így csak összesen 10 000 kilométert tud vezetni. Azt akarja tudni, hogy meglátogathatja-e az összes várost anélkül, hogy kifogyna a benzin., (A Wikipédiából)
- egy gazdálkodó 100 különböző tömegű görögdinnyét akar a piacra vinni. Be kell csomagolnia a görögdinnyét dobozokba. Minden doboz csak 20 kilogrammot tarthat törés nélkül. A gazdálkodónak tudnia kell, hogy 10 doboz elegendő-e ahhoz, hogy mind a 100 görögdinnyét szállítsa a piacra. (A Wikipédiából)
mindezen problémák közös jellemzője, hogy a legfontosabb, hogy megértsük a intrika P versus NP: annak érdekében, hogy megoldja őket meg kell próbálni az összes kombinációt.
A megoldás
ezért a válasz A P vs., NP probléma annyira érdekes, hogy az emberek. Ha valaki meg tudná mutatni, hogy a P egyenlő az NP – vel, akkor nehéz valós problémákat okozna a számítógépek számára.
összefoglaló
- p vs. NP foglalkozik a különbség a számítógépek között, hogy képes gyorsan megoldani a problémákat vs. csak hogy képes tesztelni javasolt megoldások helyességét.
- mint ilyen, a P vs. NP probléma az, hogy megtaláljuk a módját, hogy megoldja a problémákat, amelyek megkövetelik a próbál millió, milliárd, vagy billió kombinációk anélkül, hogy ténylegesen megpróbál minden egyes.,
- a probléma megoldása mélyreható hatással lenne a számítástechnikára, ezért társadalmunkra.
február 7, 2017-hozzáadott Wikipedia attributions.
2014. március 2. – megtisztított néhány magyarázatot a zavartság elkerülése érdekében.