Adott a következő probléma: wiki. Az ezredforduló, és napjaink legjelentősebb megoldatlan matematikai problémája.
A P osztályba azon problémák tartoznak, melyek algoritmikusan megoldhatók polinom időben. Vagyis a megoldáshoz szükséges idő a probléma bemenetének polinom függvénye.
Az NP osztályba azon problémák tartoznak, melyek általánosan ugyan nem oldhatók meg polinom időben, de egy adott megoldásról polinom időben eldönthető, hogy helyes-e.
Egyik legismertebb példa NP-beli problémára a prímfaktorizáció. Ha egy tetszőlegesen nagy számhoz megadják a prímtényezőit, akkor nagyon könnyen eldönthető, hogy az adott szám az adott prímek szorzataként előáll-e. Viszont ha csak a nagy számot adják meg, akkor a prímtényezők meghatározása elég költséges feladat.
Léteznek NP teljes problémák is. Azon problémák tartoznak ide, amelyekre minden NP-beli probléma visszavezethető. Ha ezek bármelyikéről kiderül, hogy megoldhatók polinom időben, abból az következik, hogy minden NP-beli probléma megoldható polinom időben. Tehát akkor P = NP.
Ha pedig P = NP, akkor elkezdhetünk igazán félni. Ugyanis az egész kriptográfia, abból kifolyólag pedig minden létező titkosítás arra a feltételezésre épül, hogy P != NP.
Viszont egy cikk szerint megszületett a bizonyítás, mégpedig arra, hogy P != NP. A bizonyítás itt tekinthető meg. Ha valóban helyes a bizonyítás, akkor nyugodtan élhetjük tovább az életünket (egyenlőre:D)
Nincsenek megjegyzések:
Megjegyzés küldése