Herendi, TamásMajor, Sándor Roland2009-05-082009-05-0820092009-05-08http://hdl.handle.net/2437/85458A 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ó.78hubonyolultságelméletNP-teljességorákulumos számításBoole-hálózatokChomsky-hierarchiaTuring-gépveremautomataSzámítógéptudományno_restriction