most-important-problems-in-computer-science.md

#The most important problems in Computer Science

June 2014

http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science

##Computational complexity theory

###P versus NP ###P = NP problem ###NC = P problem ###NP = co-NP problem ###P = BPP problem ###P = PSPACE problem ###L = NL problem ###L = RL problem ###What is the relationship between BQP and NP? ###Unique games conjecture ###Is the exponential time hypothesis true? ###Do one-way functions exist? *Is public-key cryptography possible?

##Algorithms

###What is the fastest algorithm for multiplication of two n-digit numbers? ###What is the fastest algorithm for matrix multiplication? ###Can integer factorization be done in polynomial time on a classical computer? ###Can the discrete logarithm be computed in polynomial time on a classical computer? ###Can the graph isomorphism problem be solved in polynomial time? ###Can parity games be solved in polynomial time? ###Does linear programming admit a strongly polynomial-time algorithm? This is problem #9 in Smale's list of problems. ###What is the lower bound on the complexity of fast Fourier transform algorithms? Can they be faster than Θ (N log N)? ###Can the 3SUM problem be solved in subquadratic time? ###Dynamic optimality conjecture for splay trees ###K-server problem

##Programming language theory

POPLmark

Barendregt–Geuvers–Klop conjecture

##Other problems

###Aanderaa–Karp–Rosenberg conjecture ###Generalized star height problem