What we talk about when we talk about Technology

技術について語ります。

巡回せぇるすまん

  • P:入力のサイズの多項式で表せる時間で解決できる問題。
  • 証拠:問題に対する解。
  • NP:入力のサイズと証拠のサイズの多項式で表せる時間で証拠が解であることを確かめることのできる問題。
  • NP困難:その問題を多項式時間に解決できるアルゴリズムがあれば、NPのすべての問題をその問題に変換することで、多項式時間で解決できるという条件を満たす問題。
  • NP完全:NP困難かつNPな問題。

...わからない。。