List of unsolved problems in computer science: Difference between revisions
Content deleted Content added
Puzl bustr (talk | contribs) →Algorithms: Order symbol is O not theta |
Puzl bustr (talk | contribs) →Algorithms: Wikified |
||
| Line 20: | Line 20: | ||
* Can [[parity game]]s be solved in polynomial time? |
* Can [[parity game]]s be solved in polynomial time? |
||
* Does [[Linear_programming#Open_problems_and_recent_work|linear programming]] admit a [[Time complexity#Strongly and weakly polynomial time|strongly polynomial]]-time algorithm? This is problem #9 in [[Smale's problems|Smale's list]] of problems. |
* Does [[Linear_programming#Open_problems_and_recent_work|linear programming]] admit a [[Time complexity#Strongly and weakly polynomial time|strongly polynomial]]-time algorithm? This is problem #9 in [[Smale's problems|Smale's list]] of problems. |
||
* What is the lower bound on the complexity of [[fast Fourier transform]] algorithms? Can they be faster than O(N log N)? |
* What is the lower bound on the complexity of [[fast Fourier transform]] algorithms? Can they be faster than [[Big O notation|O]](N log N)? |
||
* Can the [[3SUM]] problem be solved in [[subquadratic time]]? |
* Can the [[3SUM]] problem be solved in [[subquadratic time]]? |
||
* [[Splay_tree#Dynamic_optimality_conjecture|Dynamic optimality conjecture]] for splay trees |
* [[Splay_tree#Dynamic_optimality_conjecture|Dynamic optimality conjecture]] for splay trees |
||
Revision as of 17:34, 20 March 2012
This article is a list of unsolved problems in computer science. Problems in computer science are considered unsolved when an expert in the field considers it unsolved or when several experts in the field disagree about a solution to a problem.
- P = NP problem. This is one of the seven Millennium Prize 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
- Is the exponential time hypothesis true?
- Do one-way functions exist?
- 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?
- Can the discrete logarithm be computed in polynomial time?
- 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 O(N log N)?
- Can the 3SUM problem be solved in subquadratic time?
- Dynamic optimality conjecture for splay trees
- K-server problem
Other problems
External links
- Major unsolved problems in theoretical computer science on StackExchange.
- Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
- Challenges for Theoretical Computer Science
- The Open Problems Project - open problems in computational geometry and related fields.
- The RTA list of open problems - open problems in rewriting.
- The TLCA List of Open Problems - open problems in area typed lambda calculus.