アカウント名:
パスワード:
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……と組み合わせて数多くの問題を作ることができます。(組み合わせ爆発ですな)
またこの組み合わせで任意の回路が構成できるので、本文に書いた証明の通り決定問題全体(R)と等しくなります。
>> P問題とその論理和・否定を組み合わせることによって任意の論理式を構成することができる。>その論理式のサイズが、入力長の多項式を超えるのなら、もはやPに含まれるかは定かではない。その理解で合っています。更に言うと、この論理式を使った回路族は判定問題を計算する任意のチューリングマシンを模倣できますので、証明の通り決定問題全体(R)と等しくなります。
色々つっこみたいのは山々なのだが、めんどいので一点だけ。この論法に、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問題である判定問題を、論理和で無限個つなぎ合わせた問題について、P問題でないものが存在する』おめでとう、これは実のところ true だ!この場合、全体の証明を正しくするには、第一の条件はこう書き直さなければならない。『P問題である判定問題を、論理和で無限個つなぎ合わせた問題は、すべてNP問題である』しかし残念ながら、これは false なのだ。一つ上の命題の証明となる例、およびこの命題の反例の代表的なものは同一の問題だ。それは、 Halting problem だ。
# 和訳がこんな感じになる教科書とかありそうだなーと思いながら書いた。## はあ、どんだけお人よしなんだ俺は。上のACに従っとけばよかったか。
どうもお疲れ様です。やっぱりここは引っかかりますよね。私も悩みました。
>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
上記の証明では、これがTrueであることを、・P問題の論理和と否定がP問題ならば、P問題の論理和と否定の組み合わせで任意の論理式を構成できること。・回路族の回路を論理式と同様に構成することにより、任意の回路族を構成できること。(任意の回路族がこのように構成した回路族の集合に含まれること)により示しています。後述も参照してください。#必要ならば詳細説明します
>P問題を論理和で組み合わせてPにならないものもあるだろうって?>確かに、無限に組み合わせたら可能性はあるだろう。>ただ、有限個の組み合わせならばPのままだし、上の命題が示しているのはこの場合だ。
この有限・無限の嫌らしい問題をP=NPの仮定の中に押し込むために、(無限列である)回路族を使用しています。
P問題から論理式合成により他のP問題を構成する操作は有限回数に限定されていません(Pの要素がある限り可能)ので、回路族を再帰的に構成することで任意の回路族を作ることができます。#選択公理が必要かな?
つまり、> 『P問題である判定問題を、論理和で無限個つなぎ合わせた問題について、P問題でないものが存在する』という操作を、回路族を再帰的に構成することにより、無限長の論理和を仮定せずに実現しています。ある回路族が実際に存在すれば、その回路族は(P=NPの仮定の元でP問題と論理演算子(¬,∨)の組み合わせで構成された)Pの中に含まれる、ということです。可能無限の世界ですね。#もし構成できない回路族が存在するということでしたら反例をいただけると助かります。
>『P問題である判定問題を、論理和で無限個つなぎ合わせた問題は、すべてNP問題である』上記の通り、計算モデルで扱えない部分は全てP=NPの仮定の中に押しこんでいるので、証明そのものには含まれていません。ですので上記のような条件も不要です。
すみません。ちょっと修正です。>この有限・無限の嫌らしい問題をP=NPの仮定の中に押し込むために
仮定は「P問題x,y,zの論理和x∨y及び否定¬zが全てPに含まれる」ですね。P問題zの否定¬zは全てPに含まれる(第二の条件の証明)ので、実質的に「P問題x,y,zの論理和x∨yが全てPに含まれる」となります。
この矛盾を解消しないまま議論することは無理というもの。
上記の証明では、これがTrueであることを、
#2671878 はどこが間違っているのですか?
あんたは正しかったよ・・・
>>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』>>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。>上記の証明では、これがTrueであることを (略) 示しています。?? ならば、あの死ぬ程シンプル極まりないあの構成的証明 (#2671878) のどの行がどう間違っているのか、示してくれ。結論が異なるなら誤りがあるはずだ。示せないなら、そうだな、普通なら世の人は俺の証明を信じると思うな。
> P問題から論理式合成により他のP問題を構成する操作は有限回数に限定されていません(Pの要素がある限り可能)ので、回路族を再帰的に構成することで任意の回路族を作ることができます。????有限回数でない、すなわち無限回合成ならP問題にならないのはそりゃそうだ、というのは書いたはずだ。そしてそれは元の命題と意味が異なるということも書いたはずだが?「再帰的」と書いている時点で(何について再帰的なのか全くわからんが)、無限からは逃れられない。とりあえず halting problem を解く回路族とやらを構成してみてほしい。できれば有限個のP問題で。そして、回路族とやらをどうやったら(任意の入力長に耐えうる)チューリングマシンの形に戻せるのかも考えてみよう。
いやあほんとに、あんた正しかったよ、 #2671748 のACさん・・・
任意のP問題ABについて、「AまたはB」がP問題になるとしているところそのものが間違いですね。例えば#2672009もコメントしていますが、無限操作(可能無限的な操作も含む)を許すならば「AまたはB」はP問題になりません。
#2672009はこの無限操作があるため証明が成り立たないとしています。しかしこの証明ではこの無限操作を背理法の仮定∀x,y∈P(x∨y∈P)の中に押し込むことによって回避しています(無限操作も含めて背理法で否定している)。ですので、証明自体はチューリングマシン&回路計算の計算モデルと集合論の公理の範疇で成立しています。#背理法は強烈ですね……
大変残念です。#2672060のAC
間違いは#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の日本語も嫌いではありませんが...)
>> 任意のP問題ABについて、「AまたはB」がP問題になるとしているところそのものが間違いですね。>『任意のP問題ABについて、「AまたはB」がP問題になる』自体が証明あるいは否定すべき命題だろうwww証明にあるとおり、『任意のP問題ABについて、「AまたはB」がP問題になる』は偽ですね。よって『P問題ABのどちらかが真となる問題がPに含まれない場合がある』が真となります。
>> 間違いは#2671878が∀x,y∈P(x∨y∈P)の仮定の元でも成り立つとしているところですかね。>これも意味不過ぎて凄い。それは仮定でもなんでもなく証明すべき命題だ。
証明すべき命題は∃x,y∈P(x∨y∉P)ですね。∀x,y∈P(x∨y∈P)=¬∃x,y∈P(x∨y∉P)は上記を証明するための背理法の仮定です。
>上の命題に無限のP問題は存在しない。あるのは有限個のP問題、AとBだけだ。
Pの濃度は有限ではありません。ですので∀x,y∈P(x∨y∈P)の構造の対象となるP問題もまた有限個ではありません。式で示されている構造が有限であったとしても、対象となる集合の構造は有限にはなりません(∀を使っているわけですし)。まあ、その結果矛盾して背理法が成立するわけですが……そのあたりの例は再帰的定義 [wikipedia.org]とか原始再帰関数 [wikipedia.org]とかがそうですね。
>あと、お気に入りの背理法とやら、途中をすっ飛ばしてもいいから「論理式」・「回路族」という言葉を使わずに
#2672083で述べている通り、無限操作の厄介な部分を回避するために背理法や論理式・回路族を使用しています(背理法の仮定∀x,y∈P(x∨y∈P)に無限操作を押し込んでいる)。P問題とその合成でやるのはとても面倒なので止めておきます。この証明自体が否定されている訳ではありませんので、する必要も無いかと思います。
なお、>> 証明では決定問題まで考慮すればいいので>!!!!!決定問題はこの意味 [wikipedia.org]で使用しています。当然停止問題は含みません。『計算理論の基礎』(Michael Sipser著)の定義で言うと『判定可能な問題』ですね。
初級者むけだと、(#2672100でも紹介されていますが)Michael Sipser の『計算理論の基礎』は良い本ですね。『証明のアイディア』という形で証明戦略の概要が説明されていますので、独学に便利です。
あとは集合論の考え方は非常にためになるので、集合論の入門書(竹内外史の『集合とはなにか』とか)もお勧めです。論理学はリチャード・ジェフリーの『形式論理学 その展望と限界』とか良かったです。戸田山和久の『論理学をつくる』の方が良いというコメントもWebで見かけますが、そっちは読みかけたまま積んでるのでコメントできないです……
おはよう! またいろいろなツッコミポイントを提供してくれてありがとう!!ただ、残念ながら暇なのは今日までだし、完全に飽きてきているので、全部ツッコんでいくのは今は控える。
そのかわりに、非常に簡単な以下の4つの命題のそれぞれについて全て、証明か反例をきっちり書いてくれ。repetitive かもしれないが、議論を整理するためにきわめて重要なことだ。
[1] 有理数は、和演算について閉じている。すなわち、任意の有理数 x, y について、 x+y もまた有理数である。[2] 有理数の任意の無限列 x_1, x_2, ... について、 その無限和 \sum_{i=1}^{\infinity} x_i もまた有理数である。[3] 計算量クラスPは、和集合演算について閉じている。すなわち、任意のP問題 A, B について、 「AまたはB」 もまたP問題である 。なおこれは『計算理論の基礎』原著 2nd edition、演習問題7.6 の一部である。"7.6 Show that P is closed under union, concatenation, and complement."[4] P問題の任意の無限列 A_1, A_2, ... について、 その無限論理和 \cup_{i=1}^{\infinity} A_i もまたP問題である。
えええ……面倒くさいなぁ
とりあえず証明と関係あるところだけ。[3]漸近的解析が計算モデルと矛盾していないならば真たぶん、漸近的解析はもっと厳密に扱う必要があると思います。#今回の証明では漸近的解析を使用していません。
それよりもあなたの主張について議論しましょう。証明が成立していないというのならばそちらの方が直接的かと思います。あなたは∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)∧(P≠R)が真だから証明が間違っていると主張していますが、上記が真である(漸近的解析を使わない)証明はありますか?
なお、本証明では、漸近的解析を使わずに計算モデルと集合論の公理で下記を証明しています。#(∃x,y∈P(x∨y∉P))の証明で簡単のため階層定理の系(P≠R)を使用していますが、これも漸近的解析なしで証明可能かと思います。(∃x,y∈P(x∨y∉P))∧(∀z∈P(¬z∈P))
[1][2][3][4]について全部あなたの回答(証明か反例が必要、yesとnoではダメ)を書かない限り、俺との議論は終わりだ。めんどくさいとか言って飛ばしたり煙に巻くのはもう許さない。ついでにアドバイスしておこう。「著名な先生に意見を伺おう!」みたいなことは絶対にするんじゃないぞ。色々と資源がもったいない。そうだな、2chで聞くぐらいなら許してあげよう。ま、フルボッコだろうけどな。普通は俺みたいに優しくないんだからな?さて、お疲れ様。
・・・お人よしだから最後に一言もう言っておこう。ほんとに優しいな俺は!!> ∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)∧(P≠R)> が真だから証明が間違っていると主張していますが、上記が真である(漸近的解析を使わない)証明はありますか?漸近的解析って何を指してんだろ・・・O、Ω、Θのことを言ってるのか? 使っちゃいけない理由が俺には見当もつかないが・・・2番目3番目はあんた自身が証明してるからいいだろう?1つ目はまさに[3]だ。#2671878 をオーダー記法を使わないで書くなら、 func_a func_b の入力長nにおける実行時間上限を p(n) q(n) と置いたとき、pとq は n のpolynomial となり、 func_a_or_b の実行時間上限は p(n) + q(n) + h(n) となる。ただし、f(n) は func_a func_b の実行の切り替えにかかる時間だ。チューリングマシンのモデルなら、func_a で使ったテープをブランクに書き戻し、(最初に一時的にコピー・退避させた)入力を復帰する作業だ。h(n) 、ならびに p(n) + q(n) + h(n) は n の polynomialになる。
やはり議論を理解されていないようですね。
反証に筋違いの部分があります。
1)無限の扱いについて提示していただいた証明はまさしく漸近的解析手法で、定数倍の違いは同じ計算量として扱っています。#更に言うと多項式時間は正確には[p(n^k) + q(n^j) + h(n^l) | k,j,lは定数]ですね。
しかし、∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)のように、背理法の仮定として無限を取り込んだ条件下でこの定数倍の違いを無視することは危険な行為です。P問題の論理和と否定が再びPに属している(Pの要素の論理和と否定の再帰的定義が可能)ため、Pには任意の回路族(任意のTMと等価)が含まれています。その結果、Pは(¬,∨)のクローン [wikipedia.org](更に言うと回路族のクローン)にまで拡大してしまいます。∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)の条件下でしたら、具体的なチューリングマシンを提示して貰えれば、それと等価な回路族がPに属することを示すことが可能です。(可能無限と同じ解釈)∀x,y∈P(x∨y∈P)という無限を取り込んだ仮定により異常な(矛盾した)世界になっているということですね。
今回のあなたとの議論の焦点はまさしくこの部分ですので、反論があるようでしたらこの部分についてお願いいたします。理解できないようでしたら仕方ありませんが……
2)Pの構成について提示して頂いている問題については異論はありません。[1][2] #2672100の通り。[4] #2672009の通り。なので省略します。
しかし、[1][2]と[3][4]の対比は正しくありません。 x∈Pについて x={c1,c2,c3,c4,……} (回路族)であり、[2]で言うところの {1, 0.1, 0.01, 0.001, ……}と同じ構成になることから、[1][2]の違いは[3][4]の違いには当てはまりません。
あなたの主張だと、[1][2]で構成が異なるため∀x,y∈P(x∨y∈P)でも[3][4]が異なるとしていますが、実際には[3]は[4]と同じ構成のためその主張は成り立ちません。ですので、∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)∧(P≠R)とすると、Pの中に[4]という矛盾した世界が生じます。
>1)無限の扱いについて> :> 理解できないようでしたら仕方ありませんが……
別ACだけど、残念ながらあなたの理解が間違っています。
あなたは自分が正しいと思い込んでいるだけです。そして、あなたは周囲からの批判的コメントに対して耐性が全くありません。自分から議論をふっかけておいて、議論が始まると自分から逃げ出しています。話になりません。学問をばかにしています。
貴方が出来ることは2つしかありません* [1][2][3][4]の質問に誠意をもって答える* 自分が正しいと信じて、自分の殻にこもる
さぁ、どっちを選択しますか?
#2672237 #2672328で回答している通り、[1][2] #2672100の通り。[3]漸近的解析が計算モデルと矛盾していないならば真[4] #2672009の通り。です。ここは誰も否定していない内容かと思います。
>別ACだけど、残念ながらあなたの理解が間違っています。とのことですが、具体的にどのように間違っているか反証を示してもらえませんでしょうか?今までのやりとりの中でギャップがあるということでしたら、その部分を示してください。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
192.168.0.1は、私が使っている IPアドレスですので勝手に使わないでください --- ある通りすがり
「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:「P問題のどちらかが真となる問題がPに含まれない」が大嘘だと思うの (スコア:1)
コメントありがとう。
>「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!
そう。ここがこの証明の肝の部分ね。
組み合わせの回数が多項式回数(定数回数かな?)の範囲なら確かに多項式時間アルゴリズムに収まるけど、この操作自体は「回数を制限していない」(指数回数でもOK)ので、多項式時間アルゴリズムになるとは限りません。
実際「AまたはB」の判定問題もまたP問題だから、他のP問題C,D,E……と組み合わせて数多くの問題を作ることができます。
(組み合わせ爆発ですな)
またこの組み合わせで任意の回路が構成できるので、本文に書いた証明の通り決定問題全体(R)と等しくなります。
>> P問題とその論理和・否定を組み合わせることによって任意の論理式を構成することができる。
>その論理式のサイズが、入力長の多項式を超えるのなら、もはやPに含まれるかは定かではない。
その理解で合っています。更に言うと、この論理式を使った回路族は判定問題を計算する任意のチューリングマシンを模倣できますので、証明の通り決定問題全体(R)と等しくなります。
Re:「P問題のどちらかが真となる問題がPに含まれない」が大嘘だと思うの (スコア:1)
色々つっこみたいのは山々なのだが、めんどいので一点だけ。
この論法に、PとNPの代わりにPSPACE (決定性多項式空間) と NPSPACE (非決定性多項式空間) をぶち込んだらどうなる?
それでもし PSPACE != NPSPACE になるのなら、とりあえず計算複雑性理論を頭から全部学びなおすとよいと思う。
Re:「P問題のどちらかが真となる問題がPに含まれない」が大嘘だと思うの (スコア: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のままだし、上の命題が示しているのはこの場合だ。
これは、有理数を有限個足し合わせても有理数だが、無限個足し合わせたら無理数になる可能性があるのと似ている
(πを各桁ごとにバラしてから、また全て足し合わせることを考えてみよう)。
注意してほしいが、ここに「指数個」とか「多項式個」とか言う概念はない。
指数とか多項式って何の? 入力長? チューリングマシンは任意の入力について動くものだ、はじめに入力長など決まっていない。
有限(定数)と無限の区別しかここでは出来ないはずだ。
じゃあ、第三の条件をこう書き換えてみたらどうだろう?
『P問題である判定問題を、論理和で無限個つなぎ合わせた問題について、P問題でないものが存在する』
おめでとう、これは実のところ true だ!
この場合、全体の証明を正しくするには、第一の条件はこう書き直さなければならない。
『P問題である判定問題を、論理和で無限個つなぎ合わせた問題は、すべてNP問題である』
しかし残念ながら、これは false なのだ。
一つ上の命題の証明となる例、およびこの命題の反例の代表的なものは同一の問題だ。
それは、 Halting problem だ。
# 和訳がこんな感じになる教科書とかありそうだなーと思いながら書いた。
## はあ、どんだけお人よしなんだ俺は。上のACに従っとけばよかったか。
Re:もうひとつ補足 (スコア:1)
どうもお疲れ様です。
やっぱりここは引っかかりますよね。私も悩みました。
>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
上記の証明では、これがTrueであることを、
・P問題の論理和と否定がP問題ならば、P問題の論理和と否定の組み合わせで任意の論理式を構成できること。
・回路族の回路を論理式と同様に構成することにより、任意の回路族を構成できること。(任意の回路族がこのように構成した回路族の集合に含まれること)
により示しています。後述も参照してください。
#必要ならば詳細説明します
>P問題を論理和で組み合わせてPにならないものもあるだろうって?
>確かに、無限に組み合わせたら可能性はあるだろう。
>ただ、有限個の組み合わせならばPのままだし、上の命題が示しているのはこの場合だ。
この有限・無限の嫌らしい問題をP=NPの仮定の中に押し込むために、(無限列である)回路族を使用しています。
P問題から論理式合成により他のP問題を構成する操作は有限回数に限定されていません(Pの要素がある限り可能)ので、回路族を再帰的に構成することで任意の回路族を作ることができます。
#選択公理が必要かな?
つまり、
> 『P問題である判定問題を、論理和で無限個つなぎ合わせた問題について、P問題でないものが存在する』
という操作を、回路族を再帰的に構成することにより、無限長の論理和を仮定せずに実現しています。
ある回路族が実際に存在すれば、その回路族は(P=NPの仮定の元でP問題と論理演算子(¬,∨)の組み合わせで構成された)Pの中に含まれる、ということです。可能無限の世界ですね。
#もし構成できない回路族が存在するということでしたら反例をいただけると助かります。
>『P問題である判定問題を、論理和で無限個つなぎ合わせた問題は、すべてNP問題である』
上記の通り、計算モデルで扱えない部分は全てP=NPの仮定の中に押しこんでいるので、証明そのものには含まれていません。ですので上記のような条件も不要です。
Re:もうひとつ補足 (スコア:1)
すみません。ちょっと修正です。
>この有限・無限の嫌らしい問題をP=NPの仮定の中に押し込むために
仮定は
「P問題x,y,zの論理和x∨y及び否定¬zが全てPに含まれる」
ですね。
P問題zの否定¬zは全てPに含まれる(第二の条件の証明)ので、実質的に
「P問題x,y,zの論理和x∨yが全てPに含まれる」
となります。
Re: (スコア:0)
この矛盾を解消しないまま議論することは無理というもの。
>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
上記の証明では、これがTrueであることを、
#2671878 はどこが間違っているのですか?
Re:もうひとつ補足 (スコア:1)
あんたは正しかったよ・・・
>>『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
>>これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
>上記の証明では、これがTrueであることを (略) 示しています。
?? ならば、あの死ぬ程シンプル極まりないあの構成的証明 (#2671878) のどの行がどう間違っているのか、示してくれ。
結論が異なるなら誤りがあるはずだ。示せないなら、そうだな、普通なら世の人は俺の証明を信じると思うな。
> P問題から論理式合成により他のP問題を構成する操作は有限回数に限定されていません(Pの要素がある限り可能)ので、回路族を再帰的に構成することで任意の回路族を作ることができます。
????
有限回数でない、すなわち無限回合成ならP問題にならないのはそりゃそうだ、というのは書いたはずだ。
そしてそれは元の命題と意味が異なるということも書いたはずだが?
「再帰的」と書いている時点で(何について再帰的なのか全くわからんが)、無限からは逃れられない。
とりあえず halting problem を解く回路族とやらを構成してみてほしい。できれば有限個のP問題で。
そして、回路族とやらをどうやったら(任意の入力長に耐えうる)チューリングマシンの形に戻せるのかも考えてみよう。
いやあほんとに、あんた正しかったよ、 #2671748 のACさん・・・
Re:もうひとつ補足 (スコア:1)
任意のP問題ABについて、「AまたはB」がP問題になるとしているところそのものが間違いですね。
例えば#2672009もコメントしていますが、無限操作(可能無限的な操作も含む)を許すならば「AまたはB」はP問題になりません。
#2672009はこの無限操作があるため証明が成り立たないとしています。しかしこの証明ではこの無限操作を背理法の仮定∀x,y∈P(x∨y∈P)の中に押し込むことによって回避しています(無限操作も含めて背理法で否定している)。ですので、証明自体はチューリングマシン&回路計算の計算モデルと集合論の公理の範疇で成立しています。
#背理法は強烈ですね……
Re: (スコア:0)
大変残念です。#2672060のAC
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)
>> 任意のP問題ABについて、「AまたはB」がP問題になるとしているところそのものが間違いですね。
>『任意のP問題ABについて、「AまたはB」がP問題になる』自体が証明あるいは否定すべき命題だろうwww
証明にあるとおり、『任意のP問題ABについて、「AまたはB」がP問題になる』は偽ですね。
よって『P問題ABのどちらかが真となる問題がPに含まれない場合がある』が真となります。
>> 間違いは#2671878が∀x,y∈P(x∨y∈P)の仮定の元でも成り立つとしているところですかね。
>これも意味不過ぎて凄い。それは仮定でもなんでもなく証明すべき命題だ。
証明すべき命題は∃x,y∈P(x∨y∉P)ですね。
∀x,y∈P(x∨y∈P)=¬∃x,y∈P(x∨y∉P)は上記を証明するための背理法の仮定です。
>上の命題に無限のP問題は存在しない。あるのは有限個のP問題、AとBだけだ。
Pの濃度は有限ではありません。ですので∀x,y∈P(x∨y∈P)の構造の対象となるP問題もまた有限個ではありません。式で示されている構造が有限であったとしても、対象となる集合の構造は有限にはなりません(∀を使っているわけですし)。
まあ、その結果矛盾して背理法が成立するわけですが……
そのあたりの例は再帰的定義 [wikipedia.org]とか原始再帰関数 [wikipedia.org]とかがそうですね。
>あと、お気に入りの背理法とやら、途中をすっ飛ばしてもいいから「論理式」・「回路族」という言葉を使わずに
#2672083で述べている通り、無限操作の厄介な部分を回避するために背理法や論理式・回路族を使用しています(背理法の仮定∀x,y∈P(x∨y∈P)に無限操作を押し込んでいる)。
P問題とその合成でやるのはとても面倒なので止めておきます。この証明自体が否定されている訳ではありませんので、する必要も無いかと思います。
なお、
>> 証明では決定問題まで考慮すればいいので
>!!!!!
決定問題はこの意味 [wikipedia.org]で使用しています。当然停止問題は含みません。
『計算理論の基礎』(Michael Sipser著)の定義で言うと『判定可能な問題』ですね。
Re:もうひとつ補足 (スコア:1)
初級者むけだと、(#2672100でも紹介されていますが)Michael Sipser の『計算理論の基礎』は良い本ですね。『証明のアイディア』という形で証明戦略の概要が説明されていますので、独学に便利です。
あとは集合論の考え方は非常にためになるので、集合論の入門書(竹内外史の『集合とはなにか』とか)もお勧めです。
論理学はリチャード・ジェフリーの『形式論理学 その展望と限界』とか良かったです。
戸田山和久の『論理学をつくる』の方が良いというコメントもWebで見かけますが、そっちは読みかけたまま積んでるのでコメントできないです……
Re:もうひとつ補足 (スコア:1)
おはよう! またいろいろなツッコミポイントを提供してくれてありがとう!!
ただ、残念ながら暇なのは今日までだし、完全に飽きてきているので、全部ツッコんでいくのは今は控える。
そのかわりに、非常に簡単な以下の4つの命題のそれぞれについて全て、証明か反例をきっちり書いてくれ。
repetitive かもしれないが、議論を整理するためにきわめて重要なことだ。
[1] 有理数は、和演算について閉じている。すなわち、任意の有理数 x, y について、 x+y もまた有理数である。
[2] 有理数の任意の無限列 x_1, x_2, ... について、 その無限和 \sum_{i=1}^{\infinity} x_i もまた有理数である。
[3] 計算量クラスPは、和集合演算について閉じている。すなわち、任意のP問題 A, B について、 「AまたはB」 もまたP問題である 。
なおこれは『計算理論の基礎』原著 2nd edition、演習問題7.6 の一部である。
"7.6 Show that P is closed under union, concatenation, and complement."
[4] P問題の任意の無限列 A_1, A_2, ... について、 その無限論理和 \cup_{i=1}^{\infinity} A_i もまたP問題である。
Re:もうひとつ補足 (スコア:1)
えええ……面倒くさいなぁ
とりあえず証明と関係あるところだけ。
[3]漸近的解析が計算モデルと矛盾していないならば真
たぶん、漸近的解析はもっと厳密に扱う必要があると思います。
#今回の証明では漸近的解析を使用していません。
それよりもあなたの主張について議論しましょう。
証明が成立していないというのならばそちらの方が直接的かと思います。
あなたは
∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)∧(P≠R)
が真だから証明が間違っていると主張していますが、上記が真である(漸近的解析を使わない)証明はありますか?
なお、本証明では、漸近的解析を使わずに計算モデルと集合論の公理で下記を証明しています。
#(∃x,y∈P(x∨y∉P))の証明で簡単のため階層定理の系(P≠R)を使用していますが、これも漸近的解析なしで証明可能かと思います。
(∃x,y∈P(x∨y∉P))∧(∀z∈P(¬z∈P))
Re:もうひとつ補足 (スコア:1)
[1][2][3][4]について全部あなたの回答(証明か反例が必要、yesとnoではダメ)を書かない限り、俺との議論は終わりだ。
めんどくさいとか言って飛ばしたり煙に巻くのはもう許さない。
ついでにアドバイスしておこう。「著名な先生に意見を伺おう!」みたいなことは絶対にするんじゃないぞ。色々と資源がもったいない。
そうだな、2chで聞くぐらいなら許してあげよう。ま、フルボッコだろうけどな。普通は俺みたいに優しくないんだからな?
さて、お疲れ様。
・・・お人よしだから最後に一言もう言っておこう。ほんとに優しいな俺は!!
> ∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)∧(P≠R)
> が真だから証明が間違っていると主張していますが、上記が真である(漸近的解析を使わない)証明はありますか?
漸近的解析って何を指してんだろ・・・O、Ω、Θのことを言ってるのか? 使っちゃいけない理由が俺には見当もつかないが・・・
2番目3番目はあんた自身が証明してるからいいだろう?1つ目はまさに[3]だ。
#2671878 をオーダー記法を使わないで書くなら、 func_a func_b の入力長nにおける実行時間上限を p(n) q(n) と置いたとき、
pとq は n のpolynomial となり、 func_a_or_b の実行時間上限は p(n) + q(n) + h(n) となる。
ただし、f(n) は func_a func_b の実行の切り替えにかかる時間だ。
チューリングマシンのモデルなら、func_a で使ったテープをブランクに書き戻し、(最初に一時的にコピー・退避させた)入力を復帰する作業だ。
h(n) 、ならびに p(n) + q(n) + h(n) は n の polynomialになる。
Re:もうひとつ補足 (スコア:1)
やはり議論を理解されていないようですね。
反証に筋違いの部分があります。
1)無限の扱いについて
提示していただいた証明はまさしく漸近的解析手法で、定数倍の違いは同じ計算量として扱っています。
#更に言うと多項式時間は正確には[p(n^k) + q(n^j) + h(n^l) | k,j,lは定数]ですね。
しかし、
∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)
のように、背理法の仮定として無限を取り込んだ条件下でこの定数倍の違いを無視することは危険な行為です。
P問題の論理和と否定が再びPに属している(Pの要素の論理和と否定の再帰的定義が可能)ため、Pには任意の回路族(任意のTMと等価)が含まれています。その結果、Pは(¬,∨)のクローン [wikipedia.org](更に言うと回路族のクローン)にまで拡大してしまいます。
∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)の条件下でしたら、具体的なチューリングマシンを提示して貰えれば、それと等価な回路族がPに属することを示すことが可能です。(可能無限と同じ解釈)
∀x,y∈P(x∨y∈P)という無限を取り込んだ仮定により異常な(矛盾した)世界になっているということですね。
今回のあなたとの議論の焦点はまさしくこの部分ですので、反論があるようでしたらこの部分についてお願いいたします。
理解できないようでしたら仕方ありませんが……
2)Pの構成について
提示して頂いている問題については異論はありません。
[1][2] #2672100の通り。
[4] #2672009の通り。
なので省略します。
しかし、[1][2]と[3][4]の対比は正しくありません。
x∈Pについて
x={c1,c2,c3,c4,……} (回路族)
であり、[2]で言うところの
{1, 0.1, 0.01, 0.001, ……}
と同じ構成になることから、[1][2]の違いは[3][4]の違いには当てはまりません。
あなたの主張だと、[1][2]で構成が異なるため∀x,y∈P(x∨y∈P)でも[3][4]が異なるとしていますが、実際には[3]は[4]と同じ構成のためその主張は成り立ちません。
ですので、∀x,y∈P(x∨y∈P)∧∀z∈P(¬z∈P)∧(P≠R)とすると、Pの中に[4]という矛盾した世界が生じます。
Re: (スコア:0)
>1)無限の扱いについて
> :
> 理解できないようでしたら仕方ありませんが……
別ACだけど、残念ながらあなたの理解が間違っています。
あなたは自分が正しいと思い込んでいるだけです。
そして、あなたは周囲からの批判的コメントに対して耐性が全くありません。
自分から議論をふっかけておいて、議論が始まると自分から逃げ出しています。話になりません。学問をばかにしています。
貴方が出来ることは2つしかありません
* [1][2][3][4]の質問に誠意をもって答える
* 自分が正しいと信じて、自分の殻にこもる
さぁ、どっちを選択しますか?
Re:もうひとつ補足 (スコア:1)
#2672237 #2672328で回答している通り、
[1][2] #2672100の通り。
[3]漸近的解析が計算モデルと矛盾していないならば真
[4] #2672009の通り。
です。
ここは誰も否定していない内容かと思います。
>別ACだけど、残念ながらあなたの理解が間違っています。
とのことですが、具体的にどのように間違っているか反証を示してもらえませんでしょうか?
今までのやりとりの中でギャップがあるということでしたら、その部分を示してください。