A P vs. NP probléma vizsgálata

Dátum
2009-05-08T07:45:19Z
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

A P vs. NP probléma a bonyolultságelmélet egyik központi kérdése. A dolgozat megvizsgálja a probléma eddigi történelmét, a megoldására tett kísérletek főbb eszközeit (NP-teljes problémák, orákulumos számítások, Boole-hálózatok),valamint a Chomsky-hierarchia viszonyát a P és NP osztályokhoz. A dolgozat melléklete Java nyelven írt osztályok csomagjai, amelyekkel Turing-gép és veremautomata szimulálható, valamint a hozzátartozó dokumentáció.

Leírás
Kulcsszavak
bonyolultságelmélet, NP-teljesség, orákulumos számítás, Boole-hálózatok, Chomsky-hierarchia, Turing-gép, veremautomata
Forrás