complexity theory
open problems in complexity theory
-
P vs BPP Problem
Can every problem solvable efficiently with randomness also be solved efficiently without it?
-
P vs NP Problem
Can every problem whose solution can be verified quickly also be solved quickly?