az idős P versus NP probléma
Tehát mi akkor, a P versus NP probléma?
a feljegyzés szerint a status quo az, hogy P≠NP.
P (polinom idő) azon problémák osztályára utal, amelyeket polinom időben egy algoritmus oldhat meg. A p osztály problémái bármi olyan egyszerűtől terjedhetnek, mint a szorzás, hogy megtalálják a lista legnagyobb számát. Ezek a viszonylag “könnyebb” problémák.
NP (nem determinisztikus polinomidő) azon problémák osztályára utal, amelyeket polinom időben nem determinisztikus számítógép megoldhat., Ez lényegében egy másik módja annak, hogy azt mondjam:”ha korlátlan számítási teljesítményem van (azaz annyi számítógép, amennyire szükségem van), akkor képes vagyok bármilyen probléma megoldására legfeljebb polinom időben”. Intuitívabban azonban arra a problémaosztályra utal, amely jelenleg nem képes elég gyors (polinom idő) választ találni, de gyorsan ellenőrizhető (polinom időben), ha valaki megoldást nyújt a problémára. Az itt ellenőrzött kifejezés azt jelenti, hogy ellenőrizni lehet, hogy a megadott megoldás valóban helyes-e.
egyértelműen, a fenti meghatározás alapján, P ⊆ NP., Vessünk egy pillantást egy példára, hogy bemutassuk ezt az absztrakt problémát.
az egyik leggyakoribb, mégis hatékony példa a Sudoku. Mivel egy megoldatlan sudoku rács (9 x 9 például), tartana egy algoritmus egy tisztességes mennyiségű időt, hogy megoldja az egyik. Ha azonban a 9 x 9 rács 100 x 100 vagy 10 000 x 10 000 rácsra nő, akkor a megoldáshoz szükséges idő exponenciálisan növekszik, mivel maga a probléma jelentősen nehezebbé válik., Azonban, mivel a megoldott sudoku rács (a 9 x 9), ez meglehetősen egyszerű, hogy ellenőrizze, hogy az adott megoldás valóban helyes akkor is, ha a méret skálák 10.000 által 10.000. Lassabb lenne, de a megoldás ellenőrzésének ideje lassabb ütemben növekszik (polinom módon).
sok más NP probléma van odakint, beleértve a hátizsák problémát és az utazó értékesítők problémáját, és hasonlóak, mivel nehéz megoldani őket, de gyorsan ellenőrizhetők., Az alapvető probléma, amelyet itt próbálunk megoldani:
képes gyorsan felismerni az NP helyes válaszokat, azt jelenti, hogy van egy gyors módja annak, hogy megtaláljuk őket?
Ha igen (azaz P=NP), ez nagyban megváltoztathatja, hogyan nézzük ezeket az NP problémákat, mert ez azt jelenti, hogy van egy gyors módja ezeknek a problémáknak a megoldására, csak hogy még nem tudtuk kitalálni, hogyan.
ha ez nem elég bonyolult, fűszerezzük fel.,
Ezen NP problémák között létezik minden olyan probléma királya, amelyet a kutatók NP-teljes problémáknak neveznek. Formálisan ezek olyan problémák halmaza, amelyek mindegyikéhez bármely más NP-probléma csökkenthető (az alábbiakban) polinom időben, és amelynek megoldása polinom időben még mindig ellenőrizhető. Ez azt jelenti, hogy minden NP probléma lehet alakítani egy NP-teljes probléma.
informálisan ezek az NP problémák” legnehezebb”., Így ha egy NP-teljes probléma polinom időben megoldható, akkor minden NP-teljes probléma polinom időben oldható meg, az NP-ben pedig minden probléma polinom időben oldható meg (azaz P=NP). A leghíresebb példa az utazó értékesítők problémája lenne.
létezik egy sor probléma az úgynevezett NP-Hard problémák., Ezek a problémák legalább olyan kemények, mint az NP-problémák, de anélkül, hogy azt polinom időben meg kellene oldani. Ez arra utal, hogy az NP-kemény problémák nem feltétlenül tartoznak az NP osztályba. Példa lenne egy sakktábla megoldása — a sakktábla állapotát tekintve szinte lehetetlen megmondani, hogy egy adott lépés az adott állapotban valójában az optimális lépés. Formálisan, nincs polinom idő algoritmus, hogy ellenőrizze a megoldást egy NP-kemény probléma.,
ha összerakjuk a kettőt, egy NP-teljes probléma azt jelenti, hogy NP-kemény, de egy NP-kemény probléma nem jelenti azt, hogy NP-teljes.
meghatározása NP-teljesség
a probléma L, NP-teljes, ha:
- l NP-Hard
- l tartozik NP
az alábbi ábra (összpontosítani a bal oldali) kell, hogy a dolgok tisztább.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Informálisan, egy probléma L1 csökkenteni lehet, hogy egy másik probléma, L2, ha:
- Minden esetben az L1 modellezhető, mint egy példányát L2
- A megoldás, hogy az utóbbi megoldást nyújt, hogy a korábbi, illetve fordítva
ahhoz, Hogy megértsük ezt ösztönösen, lehet gondolni, mint például:
Ha az L1 redukálható L2, L1 kell A LEGTÖBB olyan nehéz, mint L2. Ezzel szemben az L2-nek legalább olyan keménynek kell lennie, mint az L1.
matematikailag ezt a következőképpen jelöljük: L1 ≤P L2 (olvassa el: “az L1 polinom módon redukálható L2-re”).,
