IT資格用語解説応用情報技術者試験・計算量
NP（Non- deterministic Polynomial）問題
更新日:
用語解説
NP問題は、答えの候補が与えられたとき、それが正しいかを多項式の時間で確かめられる問題の集まりです。
■ 試験で押さえるポイント
解くのは難しくても、確かめるのは簡単な問題を含みます。
P問題はNP問題に含まれます。
■ 過去問での着眼点
「解ける」ではなく「確かめられる」問題である点を押さえます。
例: 巡回の経路の候補が示されれば、その長さが基準以下かは簡単に確かめられます。