アルゴリズムイントロダクションのあれこれ

ある値または値の集合を入力とし、ある値または値の集合を出力として生成する。明確に定義された計算手続き 計算問題で課された全ての制約を満たす入力に対し、

• その出力が正しい場合: アルゴリズムは正当
• その出力が正しくないまたは遂行できない場合: アルゴリズムは正当ではない

• 効率的なアルゴリズムは発見されていないが、そのアルゴリズムが存在しないことは証明されていない問題
• 1つの NP 完全問題に対する効率的なアルゴリズムが発見されれば、全ての NP 完全問題に対する効率的なアルゴリズムが存在することが証明される
• NP 完全問題を少し変更しただけで、効率的なアルゴリズムが存在することが証明される問題もある

例)

• 巡回セールスマン問題
• 点彩色問題