「計算複雑性理論」の版間の差分

NPがPと同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている<ref name="Sipser2006"/>。同じであった場合に都合が悪い影響として、[[暗号理論]]の多くがNPの困難さに依存しているため、Pと同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、[[オペレーションズリサーチ]]における[[整数計画問題]]、物流合理化、[[生物学]]における[[タンパク質構造予測]]、[[純粋数学]]の定理を[[計算機]]で効率的に形式的に証明する可能性などがある<ref>{{cite journal|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.|last=Berger|first=Bonnie A.|coauthors=Leighton, Terrance|journal=Journal of Computational Biology|date=1998年|volume=5|number=1|pages=p27-40}}、[http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=pubmed&dopt=Abstract&list_uids=9541869&query_hl=14&itool=pubmed_docsum PubMed]</ref><ref>{{cite journal|last=Cook|first=Stephen|authorlink=スティーブン・クック|title=The P versus NP Problem|publisher=[[クレイ数学研究所]]|date=2000年|month=April4月|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18}}</ref>。[[クレイ数学研究所]]は[[2000年]]に、この問題を最初に解いた人に100万ドルを支払うと発表した<ref>{{cite journal|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18}}</ref>。