「計算複雑性理論」の版間の差分
削除された内容 追加された内容
m →決定問題: 内部リンクの修正 |
|||
38行目:
ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、''IS-COMPOSITE''問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、''IS-PRIME''問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラス'''[[NP]]'''と'''[[co-NP]]'''などで重要となる。
計算複雑性理論の重要な成果の1つとして、ある難しい問題があったとき（それがいかに大量の時間資源や空間資源を要したとしても）、それよりさらに難しい問題が必ず存在するという事実がある。時間計算量については
== 計算資源 ==
| |||