This is a list of unsolved problems in computer science. A solution to the problems in this list will have a major impact on the field of study to which they belong.

Computational complexity theory

P versus NP

Source:

• S. A. Cook and Leonid Levin
• Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.

Description: P is the class of problems whose solution can be found in polynomial time. NP is the class of problems whose solution can be verified in polynomial time. Naturally, any problem in P is also in NP. The P versus NP question is whether NP is in P, hence the classes are equal. One can see the question as a specific case of the problem in proving lower bounds for computational problems.

Importance: If the classes are equal then we can solve many problems that are currently considered intractable. If they are not, then NP-complete problems are problems that are provably hard.

Current conjecture: Though the question is far from being settled, it seems that the classes are different.

Cryptography

Source:

• W.Diffie, M.E.Hellman
• IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654
• Online copy (HTML)

Description: One-way functions are functions that are easy to compute but hard to invert. Some people conjecture that computing discrete logarithm and inverting RSA are one-way functions.

Importance: If one-way functions do not exist then public key cryptography is impossible. Their existence would imply that many complexity classes are not learnable, and that P is not NP.

Current conjecture: It is assumed but unproven that they do exist.

High performance computing

Source:

Description: Although the speedup theorem from computability theory shows that any computation can be sped up by any desired constant degree, there is no feasible method of gaining such a speedup. It is needed to know what are the techniques and bounds on speedup in various architectures - a single processor, grid, distributed network, etc.

Importance: The speed of computation is the limit to the problems that we can solve.

Current conjecture: Amdahl's law is a partial answer to the question.

How can one build a cluster of N nodes?

Source:

Description: As the number of computers in a cluster rises, the probability of failure in some of the computers rises too. At some point, the mean time between failures is shorter than the recovery and checkpoint times. In such a case, different algorithms and architectures might be needed in order to gain more computing power. It is possible that the higher probability of failure will bound the rate of increased power.

Importance: Clusters are a powerful method of gaining computation power. Therefore, bounds on the cluster size are currently bounds on computational power.

Current conjecture:

What is an optimal UET scheduling algorithm for 3 processors with precedence constraints?

Source:

• Marc Chardon, Aziz Moukrim
• The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders, SIAM J. Discrete Math, Volume 19 (2005), Number 1 pp. 109-121.''

Description: A unit-execution-time (UET) scheduling problem contains tasks all with identical length. When there are precedence constraints then there is a directed graph of dependencies between the UET tasks. To start a task all its direct predecessors must first be completed. Two optimal algorithms are known for UET task systems on 2 processors [GareyJohnson76.

Importance: This problem is fundamentally equivalent to scheduling instructions in a superscalar computer, and to scheduling parallel tasks systems optimally in a multiprocessor with 3 processors. The problem is NP-complete for arbitrary $m$, but complexity for fixed $m\; >\; 2$ is unknown.

Current conjecture:

See also

• List of publications in computer science

Conjectures | Cryptography | Unsolved problems in computer science | Technology-related lists | Lists of unsolved problems | Problemas no resueltos de la informática | 전산학의 미해결 문제 | 計算機科学の未解決問題