One of the major open problems in theoretic computer science is

showing the existence of a problem that could be solved in polynomial

time but not by a logarithmic depth circuit (P vs NC_1). One approach

that has a lot of progress in the last several years is to prove

Karchmer, Raz, and Wigderson conjecture. It states that there is no

better way to compute the composition... more

showing the existence of a problem that could be solved in polynomial

time but not by a logarithmic depth circuit (P vs NC_1). One approach

that has a lot of progress in the last several years is to prove

Karchmer, Raz, and Wigderson conjecture. It states that there is no

better way to compute the composition... more