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.