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

複雑性クラス [[P (計算複雑性理論)|'''P''']] は、[[チューリング機械]]で[[多項式時間]]で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である<ref name="Sipser2006">{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation|edition=2nd edition|chapter=Time Complexity|yeardate=2006年|publisher=Thomson Course Technology|location=USA|id=ISBN 0-534-95097-3}}</ref>。

'''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|yeardate=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=[[クレイ数学研究所]]|yeardate=2000年|month=April|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>。

上の問題に関連して、'''NP'''クラスに属する問題で'''P'''クラスには属しないが'''NP'''完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、多項式時間に還元できない問題ということである。そのような問題で'''NP'''完全かどうかが不明な問題として、[[同型グラフ|グラフ同型問題]]がある。'''P'''<nowiki> ≠ </nowiki>'''NP'''であることが示されれば、そのような問題が存在することが確定する<ref name="DuKo2000">{{cite book|last=Du|first=Ding-Zhu|coauthors=Ko, Ker-I|title=Theory of Computational Complexity|publisher=John Wiley & Sons|yeardate=2000年|country=USA|id=ISBN 978-0-471-34506-0}}</ref>。