Unsolved Problems in Computer Science - Algorithms

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