アカウント名:
パスワード:
func_a(x) : 判定問題Aを入力の長さの多項式時間以内に判定できる関数func_b(x) : 判定問題Bを(ry
func_a_or_b (x) { return func_a(x) || func_b(x);}「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!(多項式を2つ加えても明らかに多項式のままだから、と一応念のため)
あと、ついでに。> P問題とその論理和・否定を組み合わせることによって任意の論理式を構成することができる。その論理式のサイズが、入力長の多項式を超えるのなら、もはやPに含まれるかは定かではない。
コメントありがとう。>「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!
そう。ここがこの証明の肝の部分ね。
組み合わせの回数が多項式回数(定数回数かな?)の範囲なら確かに多項式時間アルゴリズムに収まるけど、この操作自体は「回数を制限していない」(指数回数でもOK)ので、多項式時間アルゴリズムになるとは限りません。実際「AまたはB」の判定問題もまたP問題だから、他のP問題C,D,E……と組み合わせて数多くの問題を作ることができます。(組み合わせ爆発ですな)
またこの組み合わせで任意の回路が構
色々つっこみたいのは山々なのだが、めんどいので一点だけ。この論法に、PとNPの代わりにPSPACE (決定性多項式空間) と NPSPACE (非決定性多項式空間) をぶち込んだらどうなる?それでもし PSPACE != NPSPACE になるのなら、とりあえず計算複雑性理論を頭から全部学びなおすとよいと思う。
そうそう。それが厄介な部分。この手法だとPSPACE≠NPSPACEで分離できちゃうんだよね。手法の切れ味が良すぎてSAVITCHの定理と矛盾してしまうという……
ただ、この証明自体はチューリングマシン&回路族の計算モデルと集合論の理論しか使っていないので、この証明が矛盾を抱えているというのも考えにくい。
まあ、P≠NPならば中間領域の問題クラスの存在も示されているので、この結果はその一つの表れなのかもしれません。最悪、(SAVITCHの定理が公理としている)漸近的解析による複雑性クラスがチューリングマシン・回路計算量のモデルと矛盾しているという可能性もありますが、それは引き続き研究しないと結論付けできないと思います。
SAVITCHの定理は NSPACE(f(n)) ⊂ SPACE(f^2(n))だから、違いがある可能性はあるんだよね。漸近的解析の曖昧さがこの違いを吸収しているだけで……
「漸近的解析による複雑性クラスがチューリングマシン・回路計算量のモデルと矛盾しているという可能性」ですが、別の可能性として、「漸近的解析による複雑性クラスは曖昧すぎて集合として扱うことができない可能性」というのがあります。この場合、複雑性クラスは集合の公理系(ZFなど)で扱えないので、数学の枠組みでは証明不可になりそうですね。
根本的な理解が間違っている、あるいは間違いを無視しているとしか思えない。端的に言ってもわかってもらえないみたいなのでちゃんと書く。
第三の条件を日本語で書くとこうだな?『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。だからそもそも証明が成り立っていない。
P問題を論理和で組み合わせてPにならないものもあるだろうって?確かに、無限に組み合わせたら可能性はあるだろう。ただ、有限個の組み合わせならばPのままだし、上の命題が示しているのはこの場合
どうもお疲れ様です。やっぱりここは引っかかりますよね。私も悩みました。
>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
上記の証明では、これがTrueであることを、・P問題の論理和と否定がP問題ならば、P問題の論理和と否定の組み合わせで任意の論理式を構成できること。・回路族の回路を論理式と同様に構成することにより、任意の回路族を構成できること。(任意の回路族がこのように構成した回路族の集合に含まれること)により示しています。後述も参照して
あんたは正しかったよ・・・
>>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』>>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。>上記の証明では、これがTrueであることを (略) 示しています。?? ならば、あの死ぬ程シンプル極まりないあの構成的証明 (#2671878) のどの行がどう間違っているのか、示してくれ。結論が異なるなら誤りがあるはずだ。示せないなら、そうだな、普通なら世の人は俺の証明を信じると思うな。
> P問題から論理式合成により他のP問題を構成する操作は有限回数
間違いは#2671878が∀x,y∈P(x∨y∈P)の仮定の元でも成り立つとしているところですかね。
無限操作は∀x,y∈P(x∨y∈P)の中に含まれていますので、(仮定の下では)無限操作と類似の操作を実現できます。(背理法で異常な状態を引き起こしているのですから当たり前ですが……)しかし、証明自体には(∀x,y∈P(x∨y∈P)の仮定以外で)無限操作を行っていませんので、#2671878の主張は間違っています。
>とりあえず halting problem を解く回路族とやらを構成してみてほしい。証明では決定問題まで考慮すればいいので、帰納的可算集合よりも大きい問題を構成する必要はありません。
上記は#2672009の『P問題である判定問題を、論理和で無限個つなぎ合わせた問題は、すべてNP問題である』というが必要という仮定から要求されていますが、そもそもこの証明ではこの条件を満たす必要はありませんので、halting problem を解く回路族も不要です。
残念なのは俺もさ。でも・・・
> 任意のP問題ABについて、「AまたはB」がP問題になるとしているところそのものが間違いですね。くっそ笑ったから許すwww『任意のP問題ABについて、「AまたはB」がP問題になる』自体が証明あるいは否定すべき命題だろうwwwそのものが間違いっていったいどういうことなんだぜwwwww普通間違いを指摘するなら、証明のこの行のこの記述、導出、仮定が間違ってるって書くだろwwwww
> 間違いは#2671878が∀x,y∈P(x∨y∈P)の仮定の元でも成り立つとしているところですかね。これも意味不過ぎて凄い。それは仮定でもなんでもなく証明すべき命
全くの分野外なので、NPSPACEは考える必要がないこと等、いくらかためになる部分もありました。よろしければよい参考書などを紹介していただけませんか?#2672060のAC
ガチで計算複雑性理論を勉強するなら(オートマトンから!)、Michael Sipser の『計算理論の基礎』はよい教科書だと思う。分厚いし(今は3分冊だと!?)、読んだの昔だからどこまで網羅してるか忘れたけど。少なくとも初版では、日本語訳も読みやすかった(SICPやK&Rとは違う)。
あとどうでもよいけど、こんな入試問題があったとは。やるな、上智。http://izu-mix.com/math/exam/jouchi/2005_1.html [izu-mix.com]
ありがとうございます!おつかれさま。#2672060のAC(SICPの日本語も嫌いではありませんが...)
初級者むけだと、(#2672100でも紹介されていますが)Michael Sipser の『計算理論の基礎』は良い本ですね。『証明のアイディア』という形で証明戦略の概要が説明されていますので、独学に便利です。
あとは集合論の考え方は非常にためになるので、集合論の入門書(竹内外史の『集合とはなにか』とか)もお勧めです。論理学はリチャード・ジェフリーの『形式論理学 その展望と限界』とか良かったです。戸田山和久の『論理学をつくる』の方が良いというコメントもWebで見かけますが、そっちは読みかけたまま積んでるのでコメントできないです……
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
人生の大半の問題はスルー力で解決する -- スルー力研究専門家
「P問題のどちらかが真となる問題がPに含まれない」が大嘘だと思うの (スコア:1)
func_a(x) : 判定問題Aを入力の長さの多項式時間以内に判定できる関数
func_b(x) : 判定問題Bを(ry
func_a_or_b (x) {
return func_a(x) || func_b(x);
}
「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!
(多項式を2つ加えても明らかに多項式のままだから、と一応念のため)
あと、ついでに。
> P問題とその論理和・否定を組み合わせることによって任意の論理式を構成することができる。
その論理式のサイズが、入力長の多項式を超えるのなら、もはやPに含まれるかは定かではない。
Re: (スコア:1)
コメントありがとう。
>「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!
そう。ここがこの証明の肝の部分ね。
組み合わせの回数が多項式回数(定数回数かな?)の範囲なら確かに多項式時間アルゴリズムに収まるけど、この操作自体は「回数を制限していない」(指数回数でもOK)ので、多項式時間アルゴリズムになるとは限りません。
実際「AまたはB」の判定問題もまたP問題だから、他のP問題C,D,E……と組み合わせて数多くの問題を作ることができます。
(組み合わせ爆発ですな)
またこの組み合わせで任意の回路が構
Re: (スコア:1)
色々つっこみたいのは山々なのだが、めんどいので一点だけ。
この論法に、PとNPの代わりにPSPACE (決定性多項式空間) と NPSPACE (非決定性多項式空間) をぶち込んだらどうなる?
それでもし PSPACE != NPSPACE になるのなら、とりあえず計算複雑性理論を頭から全部学びなおすとよいと思う。
Re: (スコア:1)
そうそう。それが厄介な部分。
この手法だとPSPACE≠NPSPACEで分離できちゃうんだよね。
手法の切れ味が良すぎてSAVITCHの定理と矛盾してしまうという……
ただ、この証明自体はチューリングマシン&回路族の計算モデルと集合論の理論しか使っていないので、この証明が矛盾を抱えているというのも考えにくい。
まあ、P≠NPならば中間領域の問題クラスの存在も示されているので、この結果はその一つの表れなのかもしれません。最悪、(SAVITCHの定理が公理としている)漸近的解析による複雑性クラスがチューリングマシン・回路計算量のモデルと矛盾しているという可能性もありますが、それは引き続き研究しないと結論付けできないと思います。
ちょっと補足 (スコア:1)
SAVITCHの定理は
NSPACE(f(n)) ⊂ SPACE(f^2(n))
だから、違いがある可能性はあるんだよね。
漸近的解析の曖昧さがこの違いを吸収しているだけで……
もうひとつ補足 (スコア:1)
「漸近的解析による複雑性クラスがチューリングマシン・回路計算量のモデルと矛盾しているという可能性」ですが、別の可能性として、「漸近的解析による複雑性クラスは曖昧すぎて集合として扱うことができない可能性」というのがあります。
この場合、複雑性クラスは集合の公理系(ZFなど)で扱えないので、数学の枠組みでは証明不可になりそうですね。
Re: (スコア:1)
根本的な理解が間違っている、あるいは間違いを無視しているとしか思えない。
端的に言ってもわかってもらえないみたいなのでちゃんと書く。
第三の条件を日本語で書くとこうだな?
『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
だからそもそも証明が成り立っていない。
P問題を論理和で組み合わせてPにならないものもあるだろうって?
確かに、無限に組み合わせたら可能性はあるだろう。
ただ、有限個の組み合わせならばPのままだし、上の命題が示しているのはこの場合
Re: (スコア:1)
どうもお疲れ様です。
やっぱりここは引っかかりますよね。私も悩みました。
>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
上記の証明では、これがTrueであることを、
・P問題の論理和と否定がP問題ならば、P問題の論理和と否定の組み合わせで任意の論理式を構成できること。
・回路族の回路を論理式と同様に構成することにより、任意の回路族を構成できること。(任意の回路族がこのように構成した回路族の集合に含まれること)
により示しています。後述も参照して
Re: (スコア:1)
あんたは正しかったよ・・・
>>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
>>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
>上記の証明では、これがTrueであることを (略) 示しています。
?? ならば、あの死ぬ程シンプル極まりないあの構成的証明 (#2671878) のどの行がどう間違っているのか、示してくれ。
結論が異なるなら誤りがあるはずだ。示せないなら、そうだな、普通なら世の人は俺の証明を信じると思うな。
> P問題から論理式合成により他のP問題を構成する操作は有限回数
Re: (スコア:1)
間違いは#2671878が∀x,y∈P(x∨y∈P)の仮定の元でも成り立つとしているところですかね。
無限操作は∀x,y∈P(x∨y∈P)の中に含まれていますので、(仮定の下では)無限操作と類似の操作を実現できます。(背理法で異常な状態を引き起こしているのですから当たり前ですが……)
しかし、証明自体には(∀x,y∈P(x∨y∈P)の仮定以外で)無限操作を行っていませんので、#2671878の主張は間違っています。
>とりあえず halting problem を解く回路族とやらを構成してみてほしい。
証明では決定問題まで考慮すればいいので、帰納的可算集合よりも大きい問題を構成する必要はありません。
上記は#2672009の
『P問題である判定問題を、論理和で無限個つなぎ合わせた問題は、すべてNP問題である』
というが必要という仮定から要求されていますが、そもそもこの証明ではこの条件を満たす必要はありませんので、halting problem を解く回路族も不要です。
Re: (スコア:0)
残念なのは俺もさ。でも・・・
> 任意のP問題ABについて、「AまたはB」がP問題になるとしているところそのものが間違いですね。
くっそ笑ったから許すwww
『任意のP問題ABについて、「AまたはB」がP問題になる』自体が証明あるいは否定すべき命題だろうwww
そのものが間違いっていったいどういうことなんだぜwwwww
普通間違いを指摘するなら、証明のこの行のこの記述、導出、仮定が間違ってるって書くだろwwwww
> 間違いは#2671878が∀x,y∈P(x∨y∈P)の仮定の元でも成り立つとしているところですかね。
これも意味不過ぎて凄い。それは仮定でもなんでもなく証明すべき命
Re:もうひとつ補足 (スコア:0)
全くの分野外なので、NPSPACEは考える必要がないこと等、いくらかためになる部分もありました。
よろしければよい参考書などを紹介していただけませんか?#2672060のAC
Re:もうひとつ補足 (スコア:1)
ガチで計算複雑性理論を勉強するなら(オートマトンから!)、Michael Sipser の『計算理論の基礎』はよい教科書だと思う。
分厚いし(今は3分冊だと!?)、読んだの昔だからどこまで網羅してるか忘れたけど。
少なくとも初版では、日本語訳も読みやすかった(SICPやK&Rとは違う)。
あとどうでもよいけど、こんな入試問題があったとは。やるな、上智。
http://izu-mix.com/math/exam/jouchi/2005_1.html [izu-mix.com]
Re: (スコア:0)
ありがとうございます!おつかれさま。#2672060のAC(SICPの日本語も嫌いではありませんが...)
Re:もうひとつ補足 (スコア:1)
初級者むけだと、(#2672100でも紹介されていますが)Michael Sipser の『計算理論の基礎』は良い本ですね。『証明のアイディア』という形で証明戦略の概要が説明されていますので、独学に便利です。
あとは集合論の考え方は非常にためになるので、集合論の入門書(竹内外史の『集合とはなにか』とか)もお勧めです。
論理学はリチャード・ジェフリーの『形式論理学 その展望と限界』とか良かったです。
戸田山和久の『論理学をつくる』の方が良いというコメントもWebで見かけますが、そっちは読みかけたまま積んでるのでコメントできないです……