List of unsolved problems in computer science

[0x1]

From Wikipedia, the free encyclopedia​

​

 ​

This article is a

This link is hidden for visitors. Please Log in or register now.

in

This link is hidden for visitors. Please Log in or register now.

. A problem in computer science is considered unsolved when no solution is known, or when experts in the field disagree about proposed solutions.




Contents

• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  

Computational complexity




Main article:

This link is hidden for visitors. Please Log in or register now.

• This link is hidden for visitors. Please Log in or register now.
  
  
• What is the relationship between
  This link is hidden for visitors. Please Log in or register now.
  and
  This link is hidden for visitors. Please Log in or register now.
  ?
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• L = P problem
  
• L =
  This link is hidden for visitors. Please Log in or register now.
  problem
  
• This link is hidden for visitors. Please Log in or register now.
  
  
• Is the
  This link is hidden for visitors. Please Log in or register now.
  true?
  
  
  Is the strong exponential time hypothesis (SETH) true?
  

[*]Do

This link is hidden for visitors. Please Log in or register now.

exist?

• 
  
  Is
  This link is hidden for visitors. Please Log in or register now.
  possible?
  

[*]

This link is hidden for visitors. Please Log in or register now.

Polynomial versus non-polynomial time for specific algorithmic problems


Main article:

This link is hidden for visitors. Please Log in or register now.

• Can
  This link is hidden for visitors. Please Log in or register now.
  be done in
  This link is hidden for visitors. Please Log in or register now.
  on a classical (non-quantum) computer?
  
• Can
  This link is hidden for visitors. Please Log in or register now.
  be found in polynomial time?
  
• Can the
  This link is hidden for visitors. Please Log in or register now.
  be computed in polynomial time?
  
• Can the
  This link is hidden for visitors. Please Log in or register now.
  be solved in polynomial time?
  
• Can
  This link is hidden for visitors. Please Log in or register now.
  and k-leaf powers be recognized in polynomial time?
  
• Can
  This link is hidden for visitors. Please Log in or register now.
  be solved in polynomial time?
  
• Can the
  This link is hidden for visitors. Please Log in or register now.
  between two
  This link is hidden for visitors. Please Log in or register now.
  be computed in polynomial time?
  
• Can graphs of bounded
  This link is hidden for visitors. Please Log in or register now.
  be recognized in polynomial time?
  This link is hidden for visitors. Please Log in or register now.
  
  
• Can one find a
  This link is hidden for visitors. Please Log in or register now.
  on a convex polyhedron in polynomial time?
  This link is hidden for visitors. Please Log in or register now.
  
  
• Can a
  This link is hidden for visitors. Please Log in or register now.
  with fixed edges for two given graphs be found in polynomial time?
  This link is hidden for visitors. Please Log in or register now.
  
  

Other algorithmic problems

• The
  This link is hidden for visitors. Please Log in or register now.
  : do splay trees have a bounded competitive ratio?
  
• Is there a k-competitive online algorithm for the
  This link is hidden for visitors. Please Log in or register now.
  ?
  
• Can a
  This link is hidden for visitors. Please Log in or register now.
  be constructed in
  This link is hidden for visitors. Please Log in or register now.
  ?
  
• Can the
  This link is hidden for visitors. Please Log in or register now.
  be computed in o(n log n) time?
  
• What is the fastest
  This link is hidden for visitors. Please Log in or register now.
  of two n-digit numbers?
  
• What is the lowest possible average-case time complexity of
  This link is hidden for visitors. Please Log in or register now.
  with a deterministic, fixed gap sequence?
  
• Can
  This link is hidden for visitors. Please Log in or register now.
  be solved in strongly sub-quadratic time, that is, in time O(n2−ϵ) for some ϵ>0?
  
• Can the
  This link is hidden for visitors. Please Log in or register now.
  between two strings of length n be computed in strongly sub-quadratic time? (This is only possible if the strong
  This link is hidden for visitors. Please Log in or register now.
  is false.)
  
• Can
  This link is hidden for visitors. Please Log in or register now.
  be done in o(n2 log n) time?
  
• What is the fastest
  This link is hidden for visitors. Please Log in or register now.
  ?
  
• Can
  This link is hidden for visitors. Please Log in or register now.
  be computed in strongly sub-cubic time, that is, in time O(V3−ϵ) for some ϵ>0?
  
• Can the
  This link is hidden for visitors. Please Log in or register now.
  for
  This link is hidden for visitors. Please Log in or register now.
  be
  This link is hidden for visitors. Please Log in or register now.
  ?
  
• Does
  This link is hidden for visitors. Please Log in or register now.
  admit a
  This link is hidden for visitors. Please Log in or register now.
  -time algorithm? (This is problem #9 in
  This link is hidden for visitors. Please Log in or register now.
  of problems.)
  
• How many queries are required for
  This link is hidden for visitors. Please Log in or register now.
  ?
  
• What is the algorithm for the
  This link is hidden for visitors. Please Log in or register now.
  that consistently generates playable mazes in the 1982
  This link is hidden for visitors. Please Log in or register now.
  game
  This link is hidden for visitors. Please Log in or register now.
  merely from the values of the five pixels adjacent to the next ones to be generated?