From Wikipedia, the free encyclopedia
This article is a list of open 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.
- Field
- Theory of computation
- Article
- Complexity classes P and 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 found in polynomial time with a non-deterministic algorithm or, equivalently, whose solution can be deterministically verified in polynomial time. Naturally, any problem in P is also in NP. The P versus NP question is whether NP is a subset of P, and hence whether 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.
- Conjecture
- Though the question is far from being settled, it seems that the classes are different.
[edit] The existence of one-way functions
- Field
- Cryptography
- Article
- One-way function
- 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 easy to compute but hard to invert. Although there are several candidates with no known good (ie quick) reverse algorithms, it hasn't been proven that none such exist.
- 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≠NP.
- Conjecture
- It is assumed but unproven that they do exist. Several encryption systems are based on the belief that modular exponentiation is a one-way function.
[edit] To what degree can one speed up a computation?
- Field
- High-performance computing
- 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.
- Conjecture
- Amdahl's law is a partial answer to the question.
[edit] See also
