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

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

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

249 :132人目の素数さん:2005/05/12(木) 17:59:29
上記で引用されてるCookのreviewだけどさ。>>126の(1)-(6)の件に
話を戻すと、page 2に書いてある通り、確かにPは(2)型で定義されてる
と考えて良いのかな?

でも、NPはやっぱり(5)型なんじゃないの? 下から6行目にある通り、
w∈L ⇔ ∃y ( |y| < |w| ^k and R(w, y))
ということなんだから、wがLに属するときにのみ、wの長さの多項式
で押さえられるような長さのrelation "y"が存在すれば良いんでしょ?
「wがLに属さないときには、yはいくら長くても良い」ということなん
ではなくて?

いや、俺ぁ計算機は素人だかんね、間違ってても驚きゃしないが。でも
もし上記が特に間違ってないんだとすると、NPに関する一連のナニは、
あまりにも間抜けな誤解なんではないかのう、と思ってさ。

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

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