Return to Video

06-18 Accepting Certificate

  • 0:00 - 0:03
    P⊆NPは成り立ちます
  • 0:04 - 0:12
    もしその問題がアルゴリズムSの多項式時間で
    決定され多項式時間で実行される場合
  • 0:12 - 0:14
    入力によりイエスかノーかを正しく導きます
  • 0:15 - 0:20
    検証アルゴリズムを持っていることが
    NPの定義でしたね
  • 0:20 - 0:25
    検証アルゴリズムをA 入力をxとし
  • 0:25 - 0:30
    どのような証明もS(x)に返るとします
  • 0:30 - 0:36
    このアルゴリズムは多項式時間で実行され
    入力と証明を正しく受け入れます
  • 0:36 - 0:44
    どんな証明であっても答がイエスならば
    どんな証明にもイエスを返します
  • 0:44 - 0:50
    どんな証明も与えることができないのなら
    答えはノーということです
  • 0:50 - 0:53
    つまりこのアルゴリズムは単に証明に対して
    答えるだけのものです
  • 0:53 - 0:57
    NPと判断するには2つのことを知る必要があります
  • 0:57 - 1:01
    そしてNPに属するものはすべてNPです
Title:
06-18 Accepting Certificate
Video Language:
English
Team:
Udacity
Project:
CS215 - Intro to Algorithms
Duration:
01:02

Japanese subtitles

Revisions