C/C++の宿題を片付けます 80代目
■ このスレッドは過去ログ倉庫に格納されています
0348NP 完全って言ってる人
2007/01/05(金) 22:11:40正しい.
>経路を求めるのはFNPにすら属さない問題もありえるわけでしょ?
それはない.FNP に属すのは,FNP の定義とハミルトン閉路問題の
存在判定だけのものが NP に属する証明から明らか.
(こういう風に一般化できるので FNP と NP の混同が正当化できる)
なので,完全が重要というよりも,明らかに完全と分かるものを
わざわざ本来よりも難しいかもしれないと言うのが嫌なだけ.
>詐欺くささ
俺の文章が悪いのだけど,303 は「それほど厳密でない計算量の議論では,
判定問題じゃない問題に対しても NP といってしまうことがある.そして
それを正当化する手が少なくとも二つある」という主張なので,詐欺くさいと
言われるとちょっと心外.303 で微妙といっているのはこのあたりのこと.
まあ今改めて 292 を読むと「NP 困難は証明されている」の一言で
十分だった気はするな.信用できないと言われたので,その弁解で必死だった.
■ このスレッドは過去ログ倉庫に格納されています