一旦メモ
用語の整理
| 概要 | |
|---|---|
| 多項式時間アルゴリズム | 時間計算量がnの多項式関数であるアルゴリズム O(1), O(N),O(N^2),... |
| 指数時間アルゴリズム | 時間計算量がnの指数関数 O(2^n), O(n!),.... |
| 複雑性クラス | |
| P問題 | 複雑性クラス(wikipedia)の一つ。多項式時間で解を求めることが出来る問題 |
| NP問題 | 複雑性クラスの一つ。解の正当性を多項式時間的に確かめることが出来る問題 |
| NP完全問題 | 指数時間アルゴリズムは存在するが、取って代わる多項式時間アルゴリズムは存在しないと予想されている問題 (ex 巡回セールスマン問題) ここでいう完全とは「そこで閉じている」という意味。 |
| P≠NP予想 | NP完全問題として考えられている問題は、P問題になりえないという予想 |
NP完全問題
P問題になりえないと予想されているNP問題
- 巡回セールスマン問題
- ハミルトン路
上記それぞれ解の正当性は直ぐに判別することが出来るが、
その解を導出するアルゴリズムは、指数時間となるアルゴリズムしか見つかっていない。