計算量の概念

コンピュータサイエンスの基礎概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

計算量クラス

計算量クラス

• 多項式時間 (P)
• 非決定性多項式時間 (NP)
• NP完全
• NP困難

P（多項式時間）

複雑さクラス -->	P（多項式時間）
意味	高速かつ効率的に解ける
例	リストのソート
たとえ	「書類を五十音順に並べる」
要点	計算量的に「易しい」

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

NP（非決定性多項式時間）

複雑さクラス -->	NP（非決定性多項式時間）
意味	解の検証は容易。新たな解の発見は難しい
例	数独の解が正しいかの検証
たとえ	「情報が欠けた状態で特定の書類を探す」
要点	検証は「易しい」が、発見は難しい

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

NP完全

複雑さクラス -->	NP完全
意味	NPで最も難しい。全NPを代表
例	巡回セールスマン問題
たとえ	「難解なジグソー：確認は易しいが解くのは難しい」
要点	効率的解法は未発見。見つかれば全NPが解ける

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

NP困難

複雑さクラス -->	NP困難
意味	NP完全と同等以上に難しい
例	複雑依存の最適スケジューリング（検証不可）
たとえ	「制約だらけの最適会議時間の決定（迅速に検証不可）」
要点	実用的解法が事実上不可能な場合あり

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

P=NP の大問題

Let's practice!

コンピュータサイエンスの基礎概念