nextuppreviouscontents
Next:BonyolultságelméletUp:Boole függvények számítási bonyolultságaPrevious:Contents

Bevezetés

Ezeken az oldalakon a Boole-függvények számítási bonyolultságával kapcsolatos eredményeinket foglaljuk össze. Az eredmények jelentősebb része az elméleti számítógéptudomány, pontosabban a bonyolultságelmélet területén fekszik, és azzal a kérdéssel foglalkozik, hogy egyes, többnyire igen egyszerű Boole-függvényeket egyes számítási modellekben milyen erőforrások igénybevételével lehet kiszámolni. Az eredmények kisebb része a kombinatorika területére esik, pontosabban az extremális halmazrendszerek és az explicit Ramsey-gráf konstrukciók területére. Az átmenetet a két terület között az összetett modulusokra vonatkozó vizsgálatok adják. Mindkét területen külön tekintjük át kutatásaink motivációját és a releváns eredményeket, majd saját eredményeinket is.
 


Vince Grolmusz

1999-11-08