List of unsolved problems in computer science
This article is a list of unsolved problems in computer science. Problems of computer science are considered unsolved when an expert in the area it sees as unresolved or when different experts disagree on a solution to a problem.
Complexity Theory
- P- NP problem. This is one of seven Millennium problems.
- NC P- problem
- NP co - NP problem
- P -BPP problem
- P PSPACE problem
- What is the relationship between BQP and NP?
- Unique games conjecture
- If the Exponentialzeithypothese it?
- Is there one-way functions?
Algorithms
- Which is the fastest algorithm for multiplying two n- digit numbers?
- Which is the fastest algorithm for matrix multiplication?
- Can a prime factorization be done in polynomial time?
- Can the discrete logarithm can be computed in polynomial time?
- Can the graph Isomorphismusproblem be solved in polynomial time?
- Can parity games be solved in polynomial time?
- Allows a strictly linear programming polynomial -time algorithm? This is problem # 9 in the problem list of Smale.
- Which is the lower limit of the complexity of an algorithm for fast Fourier transform? Can such be faster than Θ ( N log N)?
- Can the 3sum problem be solved in less than quadratic time complexity?
- Behave splay trees dynamically optimal?
- K- server problem
Theory of Programming Languages
- POPLmark
- Barendregt - Geuvers - Klop conjecture
- Generalized star height problem-
Other problems
- Aanderaa - Karp -Rosenberg conjecture