5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

山口人生〜ストリートダンスの連中に絡まれるの巻 Part21

205 :132人目の素数さん:2005/05/12(木) 13:28:48
先生のページからリンクされているNPの定義を見てみましたが

入力を多項式時間で判定できるTMが存在し,
正解入力に対してはある証拠が存在して, それが証拠であることを
そのTMを用いて判定できる.
不正解入力に対してはそのTMを用いて証拠であると
判定されてしまうような(そのTMの)入力は存在しない

という定義ですよね
ここで>>126をみると(6)は不正解の拒否も多項式時間でできるように
書いていますが, 上の定義では拒否については多項式時間でできる
とは限らないようになっていて, ここが(5)と(6)の本質的な違いになって
いるという理解でよいですよね?

290 KB
★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)