# Unsolved problems in computer science

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.

## P = 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

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.

## References

1. ^ Gasarch, William (2002). "The P=?NP Poll" (PDF). SIGACT News (ACM Press) 33 (2): 34–47. doi:10.1145/564585.564599. ISSN: 0163-5700. Retrieved 2007-06-12.
• ソーシャルブックマークに追加：

gooウェブ検索 急上昇ランキング (総合)

カムチャツカ沖でM8・3の地震

gooのお知らせ
gooヘルスケア「おもいやり食堂」ヘルシー美味しい社員食堂に「おもいやり」。健康に配慮した人への“食”を通じた「おもいやり」。
gooトップページさらに使いやすくなった「スマホ版gooトップページ」の使い方をご紹介。実は60種類以上のデザインが選べるんです
gooブログのスマホアプリgooブログのスマホアプリを使えばいつでもどこでもブログが書ける♪今日を明日の思い出にしよう！

goo電子書籍特集「キミと話がしたいのだ。」何気ないしあわせ、疲れたココロに染みわたる、珠玉のショートストーリー。
Wikipedia記事検索について
gooサービス