A KRW sejtés
| Témavezető: | Pálvölgyi Dömötör |
| ELTE TTK, Számítógéptudományi Tanszék | |
| email: | domotor.palvolgyi@ttk.elte.hu |
Projekt leírás
A Karchmer–Raz–Wigderson-sejtés Boole-függvények kocka kompozíciójának minimális mélységét korlátozza. Ha igaznak bizonyul, akkor bizonyítja, hogy P⊈NC, azaz, vannak ,,eredendően szekvenciális'' polinomiális eldöntési feladatok, amelyek nem gyorsíthatók jelentősen több processzorral dolgozva. Munkám során a sejtéshez kapcsolódó részeredményeket, speciális esetekre vonatkozó bizonyításokat tekintek át.