探検
P vs NP
■ このスレッドは過去ログ倉庫に格納されています
ニュースになってた
https://www.zaikei.co.jp/article/20170817/392615.html
https://mobile.twitter.com/hyuki/status/897343435329257472?p=p
ダメだったとさ
新しい証明はどんどん出てるよ。
まぁP∈NPかつPノットイコールNPだろうな
ノットイコールちゃんと表示されるかな？
ついでに↓
≒
↑ニアリーイコールテスト
ジグソーパズルの問題、としては解の判定は一瞬でわかるけれども、解に辿り着くまでは、多項式時間、多項式で計算量終わらない気がしますね。
最良のアルゴリズムの定義とかも考えないといけなさそうです。
まずアルゴリズムにおいて最良とは何か？
題意にたいしてどのような値が与えられても必ず解答に辿り着くアルゴリズムの中で最も計算量が少ないもの、と想像がつく。
解けるかは知りませんが続くと思います。
その中で最小=最良のものは存在する。
と置く。
P =NPを否定したいなら
検証が一瞬で終わるものの中にAnsが多項式で終わらないものがある事を示す
でいいのだろうか？
まだ自分の理解が不十分な可能性があるが。
これをWorstと置く。
検証が一瞬というのはあまり正確な表現ではなく
検証が多項式時間で終わるものの中にAnsが多項式時間より大きな数で表現されるものの存在を示す
と言うのが正確な表現ですかね。
最良のアルゴリズムが一つとは限らない。
しかし、計算量は最小である。
この場合どのような手法を取るべきか。
計算量に着目すべきかどうか。
多分最小の計算量に着目すべきかも
abs(Ans)が多項式になるかだ。ここでabs(A)はアルゴリズムAの計算量と定義する。
問題から生じる最大次数の多項式の集合をKとする
これもおかしいな。
最大計算量が指数計算量だったらこれは成り立たないから、何か性質を付加するなりして、そこら辺の判別も行わないと。
ここで何故指数時間になるか考えないと。
指数時間になる問題と多項式時間になる問題の判別は何処だ？
P!=NPで確定したとは言ってないが
つまりP=NPの可能性も探りつつやります
ここで、計算領域は常に上に有界である
ここで言う解の定義は何だ？
命題が定める性質を持つ、ある数の組の事か？
ここでの直観、イメージは指数時間の膨大な、巨大な計算領域の中に多項式時間で収まるアルゴリズムなんて本当にあるのだろうか？
横一列の
a[1],,,,a[N]を与えて(これは1からNまで昇順に並んでいる)
a[1]=1だけ与えられて、
次にb[2],,,b[N]が与えられてそれぞれには2以上N以下の数字が入ってるが何が入ってるかは不明。他の情報は全てブラックボックス。a[1]の右隣当てられたら次はそのさらに右隣を当てて行ってb[N]の数列を確定させる、ジグソーパズルの一次元版を考える。置こうとしてるマス目の値が前のマスの値+1になってたらTrueを返して、違ったらFalseを返すゲーム。
これだとプレイヤーはどう足掻いても(N-1)!の計算量から逃れられないのではないだろうか。最良のアルゴリズムの計算量も(N-1)!で、P!=NPになるのではないか？
間違っているかもしれませんが、今日はここまで考えました。
多項式時間とN!ってどっちが計算量多いんですかね。
これでP!=NP(P≠NP)の解答になっていませんかね？
何か勘違いしていたらすみません。
これでP vs NP終わってませんかね？
このゲームの問題を解くアルゴリズムが最良でも(N-1)!の計算量が必要であり、一方解の検証は即座に終わるのは明らか。よってこの問題はNPであるがPではない。よってP≠NPである。
https://kotobank.jp/word/P対NP問題-156094
反応が欲しいんですけれども。
撤回かな
全探索では(N-1)!だが
二分探索ではlog ((N-1)!)の計算量になるが、
この問題ではどう足掻いても、どんなにアルゴリズムを改良して、最高、最良のアルゴリズムを作っても多項式計算量にはならないと思う。
log (N!)と多項式計算量N^aはどっちが大きいんだ？→直観でわからないならNを莫大な数にしてさっさと計算させれば良い、というか単純にlog(N!)とNを比べれば良い。明らかに前者。
俺の作った問題で多項式計算量のアルゴリズムが存在しない事を示せば良いか。今作った問題で多項式計算量のアルゴリズムAnsが存在したとする。次にAnsの次数かつ定数aが存在する。a<=N-1である。そして明らかにa=f(N)となる関数fが存在する。fは問題によって定まる。というか、定数ならどんなNが来ても定数なのだから、N=1だった場合0か1が返ってくるから候補として0が与えられるが、そんなわけないので矛盾するから多項式計算量のアルゴリズムは存在しない？
多項式計算量のアルゴリズムってどんな集合だ？
forで回す箇所が有限個の問題だ。
全探索の試行回数がNが増加するにつれてどれくらい大きくなるのか、によって最良のアルゴリズムがどの程度のものか、 測るというのはどうだろうか？
多項式で終わるなら次数もNの関数になる？そこはどうなんだ？いや違う。定数だ。次数にNが入ったら指数計算量になる。
b[N]の並びが最悪の場合で多項式計算量で求まったとして、
要素を追加したb[N+1]を追加したら、計算量の増加はa-1次の多項式で表現出来るのか？増加量も多項式にならないといけない。N=2^nとする。
そもそも多項式計算量で済む問題って選択、試行回数がNに依存しない問題だけではないだろうか。
本当に1からNまでのランダムの並びであるb[N]の並びをYes/Noでしか判定出来ない問題を、全て特定する為に多項式計算量で押さえられるだろうか？普通に考えて、常識的な感覚ならどう見ても無理。ここの矛盾を示したい。というか、これは要するに暗号を解くのは指数時間以上いる事を示すのと同値か。暗号を多項式時間では解けない事を示す。
というか、1文字特定するとか、回数に制限があれば、多項式で抑えられる。しかし試行回数がNの関数だと多項式で抑えられないと思う。そこをどう表現するか、なのだろうか。二分探索の5以上か否かの判定を組み込めない問題は作っていいのか？完全に一致した時以外を返さない問題は作れないだろうか。
まず、試行回数がNの関数になってるのと有限回なので本質的に問題の構造が異なる？問題なのか計算量なのか。
最良のアルゴリズムの計算量の式を
p(N)と置く。ここでpは多項式である。
Nが∞に近づくとp(N+1)/p(N)が1より大きな数に収束する事を示す？あるいは1に収束したと仮定して矛盾を導く？
もし、1に収束したら、問題を解く難易度がほとんど変わらない、という意味だと思う。が、そんなわけある筈ない。ここで難易度の定義や多寡が計算量に依存していると示唆される。N=1,2で全然量が違う。
WorstはN!である。
或いは二分探索よりよいアルゴリズムがないか、とか。問題を二分探索より早く解くアルゴリズムが存在しない、すなわち計算量はlog (N-1)!が最良である事を示すか。
b[N]の並びが最悪の場合で多項式計算量で求まったとして、
要素を追加したb[N+1]を追加したら、計算量の増加はa-1次の多項式で表現出来るのか？増加量も多項式にならないといけない。N=2^nとする。
そもそも多項式計算量で済む問題って選択、試行回数がNに依存しない問題だけではないだろうか。
本当に1からNまでのランダムの並びであるb[N]の並びをYes/Noでしか判定出来ない問題を、全て特定する為に多項式計算量で押さえられるだろうか？普通に考えて、常識的な感覚ならどう見ても無理。ここの矛盾を示したい。というか、これは要するに暗号を解くのは指数時間以上いる事を示すのと同値か。暗号を多項式時間では解けない事を示す。
というか、1文字特定するとか、回数に制限があれば、多項式で抑えられる。しかし試行回数がNの関数だと多項式で抑えられないと思う。そこをどう表現するか、なのだろうか。二分探索の5以上か否かの判定を組み込めない問題は作っていいのか？完全に一致した時以外を返さない問題は作れないだろうか。
まず、試行回数がNの関数になってるのと有限回なので本質的に問題の構造が異なる？問題なのか計算量なのか。
最良のアルゴリズムの計算量の式を
p(N)と置く。ここでpは多項式である。
Nが∞に近づくとp(N+1)/p(N)が1より大きな数に収束する事を示す？あるいは1に収束したと仮定して矛盾を導く？
もし、1に収束したら、問題を解く難易度がほとんど変わらない、という意味だと思う。が、そんなわけある筈ない。ここで難易度の定義や多寡が計算量に依存していると示唆される。N=1,2で全然量が違う。
WorstはN!である。
或いは二分探索よりよいアルゴリズムがないか、とか。問題を二分探索より早く解くアルゴリズムが存在しない、すなわち計算量はlog (N-1)!が最良である事を示すか。
この問題はb[1]を最も早く特定する問題に帰着出来るか？それとも一気に複数特定出来る方法があるのか？
b[1]からb[N]までランダムに並べてそれらを特定する、というゲームなら計算量はN!
この問題はb[i]が文字なのか数字なのかでも計算量変わる気がする、と思ったが一行増えるぐらいか？二分探索するなら全て数値化しないといけない。
一文字特定するのに二分探索が最良である事を示す→次に複数の文字列を一気に特定するのは1文字ずつ特定するより計算量が多い事を示す→問題は解ける？
とりあえず一文字特定するには二分探索が最良である事を示したい。→よく考えたらlog Nで多項式より小さい。が、最善のアルゴリズムかは不明。
例えばN=128で二分探索未満の特定する方法は存在するのか？無理だと思うが。
二分探索は計算領域を狭めて行く収束速度を考察すると良いかも知れない。
結局探索においてパソコンは命題の真か偽の判定をするだけである。命題のブール値を返すだけである。
多項式ってのは2次式でも3次式でも1000次式でもいい
どうやるんですかね、後で考えてみますね
b[N]が多項式計算量で収まったとすると、最高次数aが存在し、またその最高次数aと同じ計算量の、有限個のk個を特定する問題b[k]を求めよ、という問題が生まれる。ところがどう見てもb[N]を特定する問題はそれより計算量が多いので矛盾する。よってb[N]を求めるアルゴリズムは多項式計算量で収まらないので検証は一瞬だがNP問題に含まれる問題の存在が示されたのでP≠NPが示された？のでいいのか？
この問題がNP完全でないとダメ
https://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3
> P≠NP予想との関係
> もし、いずれかのNP困難な問題を多項式時間で解くアルゴリズムが存在したなら、
> NPの全ての問題について多項式時間で解けることになり、P=NPが成り立つ。
> ところが、P=NPが成立しても「任意のNP困難な問題が多項式時間で解ける」とは言えない。
ありがとうございます。
ちょっとずつ問題の概要がわかってきました
NP完全がPなのかそうでないのかに集約される。
今わかってる事
問題AがNP完全という条件
AがNPである事(検証だけは多項式計算量で終わる。解くのにはどれくらいかは不明)
全てのNP問題がAに多項式還元可能
そしてNP完全の問題は
彩色問題
ぷよぷよ
部分和問題
テトリス
などが存在する。
これらがPでない事を示すか、Pである事を示せば良い。
もっと抽象化してNP完全の一般的な性質を調べてみよう。
わかっている事
AがNPである事
全てのNP問題がAに多項式還元可能
AがPかそうでないかを判定すればよい。
究極的に一般的な話だけで問題を攻略したい。
今AがPであると仮定する。(これで矛盾が導ければP!=NPである)
或いはそうでないと仮定する。その時どんな性質が出てくる？
こういう考え方は宿命の二人が一つになる方法を導いたのと全く同じような話だ。でもそっちの方が多分一般的な話をしているからそれでいいのだろうけど。
P!=NP
Pだと仮定する。
すると全てのNPはPになる。この時矛盾が生じる事を示す。１つは、この時どう足掻いてもPにならない問題の存在を示せば良い。
個人的にはこっちで話を進めて行きたい。
アルゴリズムを具体的に特定する事は難しいのであれば、宿命の二人が一つになる方法を作り上げたように純粋に言語的性質操作で出来るかもしれない。あの問題は言語の定義や性質を如何に深く理解してるかが問題を解く鍵だった。徹底した定義に対する理解の深さで知識量の多さではなかった。
NP完全の問題は沢山あるようなので最も本質に迫るには最も本質的な定義や性質をいじっていくべきな気がする。
Pではないと仮定すると全てのNPはPでないので、これの矛盾を示すには、どれか一つPになるNPを示せば良い。あるいはNP完全のどれか一つでも良いので多項式計算量で解ける事を示すか。
二分探索で劇的に計算量が減った事も考えよ
文字列特定は全探索のN!から二分探索でlog N!でN^2まで計算量落ちた。N!<N^Nでlog N^N=Nlog N<N^2)
これはおそらく最大の計算量と考えられるものから、多項式計算量までスリムに出来た。
N^N以上の計算量のものは存在するだろうか？
アルゴリズムの改良で減る計算量は具体的にどのくらいか考える？
全ての問題は本質的に全て同じではないか？
全ての問題がP問題ならば、全てのP問題は、本質的にある一つのP問題の変形でその問題から有限回？の変更を施せば全ての問題が得られる？
或いは逆にどのようなP問題を用意しても、本質的にNPの問題には届かない事を示す？
P!=NPならば、
PとNPを本質的に分ける何かがある筈。ある一つの属性か何かかはわからないが。
そもそも、操作が有限回の操作なわけだから、何が原因で指数計算量以上に跳ね上がるのだろうか？
P=NPではないだろうか？そうであればPとNPを本質的に分けるものはないという事だと思うが。
二分探索が使える問題は全てPに還元出来る？使えない問題はどうなんだ？
NPにばかり注目しているがPに注目するのはどうだろうか？
P=NPを示したいならPとNPが構造的に同質である事を示すのだろうか。P問題が作れられる構造とぷよぷよが論理構造の点で一対一対応している事を示すのはどうだろうか。やり方は全くわからないが。
多項式時間で解ける問題とはどういう集合だろうか。
というか、多項式とはなんだろうか？
P!=NPだったらその逆か？
本の知識を勉強するより、P vs NPに関して、俺の数学理論を構築した方がいい気がする。
p vs npでわかっている情報が
問題AがNP
Aに多項式還元される
の二つしかない為皆目見当がつかないので、P=NPとP!=NPでどっちが美しい世界が広がるか、で方向性を考えるようにしたらどうだろうか。
真理値が与えられるものだろうか？
コンピュータで解かれる問題は有限個の要素がある命題である。無限個あったら特定出来ない？少なくとも一生計算しても解を特定出来ない可能性がある？それでも特定出来るアルゴリズムがあるのか？
解を特定するアルゴリズムが最悪でも有界の計算量で終わる命題の集合をSolvableあるいはSと置く。ここで計算量は指数でも構わない。ここでSは特にどんな問題かは特定していない。SがPである事を示す？
Pでないと仮定する。少なくともそのような命題Aが存在したとする。
大きい、の定義は、+∞の極限を取った時に((問題Aの計算量)/有限次数多項式計算量)が無限大に発散する事と定義する。
とした場合、
二分探索による解への収束速度は2の冪乗であり、一回の試行で情報の半分が削れる。他方で、全探索のアルゴリズムは一つ一つ消していくから効率が悪い。
つまり指数収束、指数量の情報量が削れるアルゴリズムであれば、指数計算量のものでも多項式計算量に落とし込める？
https://zenn.dev/senk/articles/cd8b454f14825dcaf7ec
計算複雑性にまつわる10の誤解
http://dopal.cs.uec.ac.jp/okamotoy/PDF/2013/complexity10confusions.pdf
> NP完全問題をもとにして作られた暗号 (例)
> Merkle-Hellmanのナップサック暗号系 '78
> 破られる (Shamir '84)
> その後も
> ナップサック問題(とその変種)に基づく多くの暗号系
> ほとんど破られている
> なぜ破られるのか？
> NP完全性は「最悪時」の困難性に関する概念
> 暗号は「平均時」や「ほとんどすべて」の困難性が必要
命題
問題のクラスと同じクラスのアルゴリズムは存在する
と表現する方が美しい。
万物の理論に届いたのだからp=npだと思う。
命題
全ての問題に対して問題と同じクラス(型 全探索の計算量が問題の本質的型、輪郭であると思われる)のアルゴリズムが存在する
仮にある問題に対して存在しないとする。
ところが全ての根源が美である事に実数時間、有限回の操作内で届くアルゴリズムは存在すると思われる。常識的に考えれば明らかにそちらの方が大きそうだからP=Npが言えそうだ。
全てを有限時間内で知る事は出来ない→万物の根源は知る事が出来ない、となる？
万物の根源=無矛盾性
そもそも人間の抽象化とコンピュータによる計算は異なるからこれは成り立たない？
夢が叶うのは奇跡ではない、手が届くように空間は曲がっている
というのが佐々木亮介氏の主張だが、この主張が真理ならばP=NPではないだろうか。
そもそも最大の計算量の問題はなんだろうか。それが実数時間で解けたら全ての問題は実数時間で解けるになると思われるが。推測では無矛盾性をどうやって示すか、になりそうだが。
という命題はP=NPの拡張、一般化である、と思われる。
これが真でないとすると、この世界が無矛盾である事を実数時間で解く事は出来ないと思う。
表現を変えるならば、不可能はない。
問題と同じクラスのアルゴリズムが存在する
という命題は非常に深い問題だ。何故なら全ての問題は実数時間で解ける事を意味するからだ。数学的にも哲学的にも。
即座に数学的証明が出来なくても、哲学的、言語的証明が出来た後で思考を深め洗練させれば数学的証明も出来ると思う。
全ての問題は実数時間内で解ける
になると思う。
もし仮に実数時間内で解けない命題があると、それは無矛盾性に反するのではないだろうか。とすると矛盾するから全ての命題は実数時間内で解ける事になり、
全ての問題に対して問題と同じクラスのアルゴリズムは存在する
は示されたような気はするがまだ何処か穴はあるだろうか。
をさらに拡張すると
全ての命題に対して問題と同じクラスのアルゴリズム、解が存在する
は真か否か→連続体仮説から言えば偽かもしれないが、どちらでもない、も解に含めた場合、真実ではないか？
少なくともp vs npでは言わない。多項式で計算量が抑えられるという意味だ。
命題が真か偽か判定不能か分類わけが出来る、と定義する、のだろうか。少なくとも問題がどういう状況か完全に判別されている状況を指すと思われる。
今日は「P対NP問題」だ。
と予想されるが正しいか？反例はないか？
全探索は十分条件。二分探索は必要十分？
全探索は解よりももっと大きな計算を行う→十分条件
必要十分の解法は設定そのものに対するアプローチ？
解とそれ以外の候補の外見、条件が対称で見分けがつかない。
大きかったなら、証明は記述し終えることはできない。
つまり証明可能であったとしても実際にそれを読み尽くすことができないのだ。
巡回ハミルトン路の存在判定の問題も、たとえばグラフを隣接行列で
表してやれば、それは可付番であるから、グラフｇに対して自然数ｎを
対応させる写像ｆが存在する。そうして、いま無限長の二値配列Aであって、
グラフｇにハミルトン路があるなしによって配列の要素A[f(g)]の値として
1と0が入って居る、そのような配列Aが存在する。
すると、グラフｇが任意に与えられたときn=f(g)を計算する。
この計算は多項式時間でできるだろう。
そうして配列Aのｎ番目の要素をO(1)の計算量で取り出すと、
グラフｇがハミルトン路を持てば1であり、そうでなければ0なのであるから、
結局ハミルトン路の存在判定は多項式時間で可能になるのだ。
＃ただし、配列Aを具体的に構成することはおそらく多項式時間では
できないのだと思う。配列の要素数が無限大ではナンセンスだという
批判もありうるだろうが、かりにf(n)の値がある上限N以下になる
ようなグラフに対してだけ判定を行えば良いのならば、配列Aの要素数は
有限N＋1個で良くなるだろう。
僕に対するコメントですか？
通常のN=NPであるか？という問いは、何かの仮定が欠けている設問なのかもしれない。
「オラクル」があれば或る意味NP困難でもPで確率論的には解けるんじゃなかったっけ？
出題者を攻略して答えを聞き出すのが手間が少ない場合がある。
おとなしく応じなければ、拷問したり、
あるいはもっと紳士的に自白剤を使うとか。
将来は脳内電磁信号をニューラルネットで解析することにより、
暴力や薬物を使わずに、脳内の記憶を引きだすことができる
ようになるかもしれないな。
困難な20文字からなるパスワードもソフトあるいは
ハードでクラックするのではなくて、ユーザー自身に
その意志に反してでも語らせれば良いのだ。
https://i.imgur.com/orxbN7G.jpg
https://i.imgur.com/RCZ3IIj.jpg
https://i.imgur.com/aJkAe4K.jpg
https://i.imgur.com/fX8Aue3.jpg
https://i.imgur.com/QGXOkdy.jpg
https://i.imgur.com/iYizOxr.jpg
https://i.imgur.com/UF3FpxL.jpg
https://i.imgur.com/opQDtAV.jpg
https://i.imgur.com/sYywMwS.jpg
https://i.imgur.com/XsITHEB.jpg
https://i.imgur.com/lO0blaS.jpg
■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 政府、コロナワクチン啓発に「YouTuber起用動画9本・3200万円支出」認める「接種の重要性など、正しい情報を知っていただくために」 ★2 [Hitzeschleier★]
- 「ドンドンショボくなる」大阪万博にまたまた“ガッカリ”報道、軟弱地盤のため「乗り物型」展示ゼロ [バイト歴50年★]
- 他候補者に「おい売国奴」拡声器で罵声、「凸」と称して迷惑行為も…東京15区補選で何が起きているのか [バイト歴50年★]
- 【鉄道】女性「電車で隣に座ってくる男キモい」SNS“炎上”…男女で《賛否》真っ二つ、それぞれの言い分とは ★3 [ぐれ★]
- 【文春】「相合い傘で自宅マンションへ…」内田理央と人気YouTuberヒカルの寿司デート＆お泊まり愛“スクープ撮 [Ailuropoda melanoleuca★]
- コロナワクチン啓発に「ＹｏｕＴｕｂｅｒ起用動画9本・３２００万円支出」政府認める はじめしゃちょーは「広告案件」を否定 [ひかり★]
- あえ・・・・・？？？？？ …おいたんたち、おねんねちないの？？？？？
- 長谷川亮太 ちばけんま 唐澤貴洋 無能弁護士
- 【悲報】日本のテレビアニメが北朝鮮製だった問題、思ったよりもヤバそう [455830913]
- 二次元以上の正常な哺乳類でなく、その行為は非倫理的に言えば生肉君もヴィーガンだけど
- あむあむと俺どっちか一人だけ助けられます
- スクリプとに負けないお🏡!