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

Computational complexity theory

P versus NP

Source:

• S. A. Cook
• 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 untractable. If they are not, then NP-complete problems are problems that are probably hard.

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

Cryptography

Do one way functions exist?

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 exist then public key cryptography is secure. Their existence would also imply that many complexity classes are not learnable. If they do not exist, the results are opposite.

Current conjecture: Most researchers conjecture that one way functions exist.

High performance computing

To what degree can one speed up a computation?

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 raises the probability of failure in some of the computers raises too. At some point, the mean time between failures is larger than the recovery and checkpoint times. In such a cases, 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:

How can one deal with the memory wall ?

Source:

Description: In today's computers memory access is becoming very slow when compared to CPU cycles. Hence, the memory access, like hard disk access, might become the term that bounds computation speed.

Importance: This is another important bound on fast computations.

Current conjecture:

See also

• List of publications in computer science