List of open problems in computer science
This is a list of unsolved 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.
| Contents |
Computational complexity theory
- 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 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
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 shorter 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: