Some of the popular problem that still exist today


  • L = NL problem
  • What is the fastest algorithm for multiplication of two n-digit numbers?
  • What is the fastest algorithm for matrix multiplication?





  • P = NP problem
  • NC = P problem
  • NP = co-NP problem
  • P = BPP problem
  • P = PSPACE problem
  • What is the relationship between BQP and NP?
  • Unique games conjecture
  • Is the exponential time hypothesis true?


  • Do one-way functions exist?


Similar Threads: