 |
Please help improve this article by expanding it. Further information might be found on the talk page. (August 2008) |
 |
This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (February 2007) |
This article is a list of unsolved problems in computer science. Solutions to the problems in this list would have a major impact on the field of study to which they belong.
Contents |
P = NP?
Main article: P and NP
- Field
- Theory of computation
- 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 (if it exists) 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 also 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 probably hard.
- Conjecture
- Though the question is far from being settled, most experts believe that the classes are different.[1]
The existence of one-way functions
Main article: One-way function
- Field
- 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 easy to compute but hard to invert. Although there are several candidates for which no good (i.e. quick) reverse algorithms are currently known, it has not yet been proven that any function exists for which no such reverse algorithms exist.
- Importance
- If one-way functions do not exist then secure public key cryptography is impossible. Their existence would imply that many complexity classes are not learnable, and that P≠NP. P≠NP does not imply that one-way functions exist, however.
- Conjecture
- It is assumed but unproven that they do exist. Several encryption systems are based on the assumption that modular exponentiation is a one-way function.
Scheduling algorithm deadlines greater than periods
Field Theory of Scheduling
Description Finding an optimal static-priority scheduling algorithm when deadlines are greater than periods is an open problem.
Importance High, to allow complex architecture in Software Industry
See also
References
- Theoretical Computer Science at Open Problem Garden The collection of open problems in mathematics and Computer Science build on the principle of user editable ("wiki") site
- ^ Gasarch, William (2002). "The P=?NP Poll" (PDF). SIGACT News (ACM Press) 33 (2): 34–47. doi:. ISSN: 0163-5700. http://www.cs.umd.edu/~gasarch/papers/poll.pdf. Retrieved 2007-06-12.
|
|||||
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
