complexity theory

open problems in complexity theory

  1. P vs PSPACE Problem

    Is every problem that can be solved with polynomial space also solvable in polynomial time?

    2025-07-23 Complexity Theory

  2. P vs BPP Problem

    Can every problem solvable efficiently with randomness also be solved efficiently without it?

    2025-07-16 Complexity Theory

  3. P vs NP Problem

    Can every problem whose solution can be verified quickly also be solved quickly?

    2025-07-12 Complexity Theory