X
トップページ⇒数学
447コメント132KB
P vs NP
■ このスレッドは過去ログ倉庫に格納されています
0314sage
垢版 |
2017/08/24(木) 00:45:01.27ID:3y090A1B
平面グラフに対する三色問題を高速で解けるとの主張だが、よくわからん。
ttps://www.quora.com/If-I-proved-that-P-NP-would-you-want-to-know-what-that-proof-is
0325１３２人目の素数さん
垢版 |
2017/08/25(金) 15:04:15.27ID:Qo0CVRfU
>>270
ペレルマンのは中華大数学者様が堂々と丸パク論文出版したのに呆れ返ったからだろ

Blumのは誤りの指摘について意見聞かれたRazborovが禿同したのが決め手になった感
0326１３２人目の素数さん
垢版 |
2017/08/25(金) 19:04:23.64ID:mSVjoa1H
ペレルマンはサーストンやハミルトンの功績が無視されたのにぶち切れてたんだよ
本人がそう言ってただろう
0327１３２人目の素数さん
垢版 |
2017/08/25(金) 19:26:09.59ID:NCATUS94
大筋は合ってるラフな論文を行間を埋めて自分達の業績にする

ブルバキグループがさんざんやってきたこと
0341１３２人目の素数さん
垢版 |
2018/05/01(火) 19:29:03.87ID:21rJWgQ2
耳栓をしたら世界が変わってワロタ
0352１３２人目の素数さん
垢版 |
2018/05/20(日) 21:52:16.79ID:N/saMlPT
耳栓をしたら世界が変わってワロタ
0353１３２人目の素数さん
垢版 |
2018/07/11(水) 06:46:55.70ID:UnQmpjGV
これついに証明されたらしいぞ
ニュースになってた
0356１３２人目の素数さん
垢版 |
2018/07/11(水) 14:43:32.85ID:HJQFUmmh
まぁP∈NPかつP≠NPだろうな
まぁP∈NPかつPノットイコールNPだろうな

ノットイコールちゃんと表示されるかな？
0357１３２人目の素数さん
垢版 |
2018/07/11(水) 14:45:01.28ID:HJQFUmmh
流石に幾らJimちゃんねるでも数学板はちゃんと表示されるか
ついでに↓
≒
↑ニアリーイコールテスト
0360１３２人目の素数さん
垢版 |
2020/10/02(金) 16:36:19.23ID:k94hyzCE
真田重雄は地獄へ落ちて幾十年だな
0362◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:09:16.81ID:weJoFrgJ
https://www.nikkei-science.com/201212_060.html

ジグソーパズルの問題、としては解の判定は一瞬でわかるけれども、解に辿り着くまでは、多項式時間、多項式で計算量終わらない気がしますね。

最良のアルゴリズムの定義とかも考えないといけなさそうです。

まずアルゴリズムにおいて最良とは何か？
題意にたいしてどのような値が与えられても必ず解答に辿り着くアルゴリズムの中で最も計算量が少ないもの、と想像がつく。


解けるかは知りませんが続くと思います。
0363◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:10:31.47ID:weJoFrgJ
ジグソーパズルの問題の最良のアルゴリズムは多項式の計算量で表現されるんですかね？
0364◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:17:34.21ID:weJoFrgJ
問題の解を得られるアルゴリズムの集合をAlgと置く。


その中で最小=最良のものは存在する。
0365◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:19:56.01ID:weJoFrgJ
最小(最良)のものをAns
と置く。

P =NPを否定したいなら
検証が一瞬で終わるものの中にAnsが多項式で終わらないものがある事を示す

でいいのだろうか？




まだ自分の理解が不十分な可能性があるが。
0366◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:04:11.40ID:weJoFrgJ
Algの中で最大のものは全探索のアルゴリズムである
これをWorstと置く。
0367◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:23:37.29ID:weJoFrgJ
>>365
検証が一瞬というのはあまり正確な表現ではなく
検証が多項式時間で終わるものの中にAnsが多項式時間より大きな数で表現されるものの存在を示す


と言うのが正確な表現ですかね。
0368◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:29:11.38ID:weJoFrgJ
>>365
最良のアルゴリズムが一つとは限らない。
しかし、計算量は最小である。

この場合どのような手法を取るべきか。
計算量に着目すべきかどうか。
0369◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:32:04.17ID:weJoFrgJ
>>368
多分最小の計算量に着目すべきかも
0370◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:41:46.69ID:weJoFrgJ
問題はWorst が多項式ではないNPの時に、Ansが多項式になるかだ。

abs(Ans)が多項式になるかだ。ここでabs(A)はアルゴリズムAの計算量と定義する。
0371◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:53:17.98ID:weJoFrgJ
解かなくてはならない問題の定義と性質を調べなければならない気がしてきた



問題から生じる最大次数の多項式の集合をKとする


これもおかしいな。
最大計算量が指数計算量だったらこれは成り立たないから、何か性質を付加するなりして、そこら辺の判別も行わないと。
0372◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:53:31.28ID:weJoFrgJ
気になって気になって眠れなくなってきた
0373◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:59:09.52ID:weJoFrgJ
問題の定義は何だ？
0374◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:59:48.69ID:weJoFrgJ
計算量は問題に依存するから問題の定義も何とかしないといけないのかもしれない。
0375◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:05:55.81ID:weJoFrgJ
ジグソーパズルの問題は全探索なら指数時間

ここで何故指数時間になるか考えないと。
指数時間になる問題と多項式時間になる問題の判別は何処だ？
0376◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:07:40.16ID:weJoFrgJ
年齢を当てる問題なら、年齢の上限があるなら、全探索は多項式時間だが、二分探索なら次数が落ちて対数になる。
0377◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:14:36.08ID:weJoFrgJ
要するに全探索で多項式計算量にならないものの中でAnsが多項式計算量にならないものの存在を示せばいい、と言うのがP!=NPか


P!=NPで確定したとは言ってないが
つまりP=NPの可能性も探りつつやります
0378◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:18:23.44ID:weJoFrgJ
命題が定める計算領域の絶対値=abs (Worst)が多項式で収まらないものの中にabs(Ans)が多項式で収まらないものの存在を示す、か、具体的に作るか
0379◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:20:40.02ID:weJoFrgJ
>>378
ここで、計算領域は常に上に有界である
0380◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:22:48.10ID:weJoFrgJ
上に有界な多項式計算量で収まらない計算領域が与えられて、その中にある最良の計算手法、アルゴリズムが存在し(確定)、しかしその計算量は多項式計算量に収まらない命題が存在する、か否か。
0381◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:25:50.52ID:weJoFrgJ
>>380
ここで言う解の定義は何だ？
命題が定める性質を持つ、ある数の組の事か？

ここでの直観、イメージは指数時間の膨大な、巨大な計算領域の中に多項式時間で収まるアルゴリズムなんて本当にあるのだろうか？
0382◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:26:21.07ID:weJoFrgJ
仕事に支障が出るのでもうやめておこう
0383◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:34:11.28ID:weJoFrgJ
全てのNPのAnsはPだったとして矛盾を導く
0384◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:41:43.92ID:5+iuQDKw
問題は、P!=NPを示したい場合、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になるのではないか？


間違っているかもしれませんが、今日はここまで考えました。
0385◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:53:06.39ID:5+iuQDKw
あー、ちょっと間違えたかな。

多項式時間とN!ってどっちが計算量多いんですかね。
0386◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:55:12.38ID:5+iuQDKw
んー、でも一応NPだからいいのか？
0387◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:59:28.13ID:5+iuQDKw
N!は2^Nより大きいからNPか
0388◆Ph05QxAcng
垢版 |
2022/05/11(水) 10:54:24.79ID:G0b+lZKs
>>384
これでP!=NP(P≠NP)の解答になっていませんかね？

何か勘違いしていたらすみません。
0389◆Ph05QxAcng
垢版 |
2022/05/11(水) 23:27:30.89ID:YiWiwdjF
>>384
これでP vs NP終わってませんかね？
このゲームの問題を解くアルゴリズムが最良でも(N-1)!の計算量が必要であり、一方解の検証は即座に終わるのは明らか。よってこの問題はNPであるがPではない。よってP≠NPである。


https://kotobank.jp/word/P対NP問題-156094


反応が欲しいんですけれども。
0390◆Ph05QxAcng
垢版 |
2022/05/11(水) 23:28:00.99ID:YiWiwdjF
もちろん間違っている可能性もありますが。
0391◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:04:21.17ID:VbVOHa6M
本当に気になって気になって仕方がないのですが、何か間違いがあったら指摘して頂きたいです。
0392◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:23:36.02ID:VNiGsFzW
あー、ミスったかも
0393◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:24:38.75ID:VNiGsFzW
二分探索が使えるのかな
0394◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:24:47.33ID:VNiGsFzW
間違えたかもしれません
0395◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:28:08.87ID:VNiGsFzW
あー、ダメっぽいな

撤回かな
0396◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:30:52.72ID:VNiGsFzW
もう一度考えてみます
0397◆Ph05QxAcng
垢版 |
2022/05/13(金) 02:49:01.57ID:LPjiuv4P
俺が考えたP vs NPの問題では
全探索では(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が入ったら指数計算量になる。
0398◆Ph05QxAcng
垢版 |
2022/05/13(金) 23:05:34.68ID:HYyFKuFH
二分探索が使えない設定の問題を作るか、そもそもこの問題で最良のアルゴリズムが多項式で表現出来ない事を示すか、だ。

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)!が最良である事を示すか。
0399◆Ph05QxAcng
垢版 |
2022/05/13(金) 23:05:49.04ID:HYyFKuFH
二分探索が使えない設定の問題を作るか、そもそもこの問題で最良のアルゴリズムが多項式で表現出来ない事を示すか、だ。

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)!が最良である事を示すか。
0400◆Ph05QxAcng
垢版 |
2022/05/13(金) 23:06:01.62ID:HYyFKuFH
一発でb[1]を特定する事は不可能。
この問題はb[1]を最も早く特定する問題に帰着出来るか？それとも一気に複数特定出来る方法があるのか？


b[1]からb[N]までランダムに並べてそれらを特定する、というゲームなら計算量はN!

この問題はb[i]が文字なのか数字なのかでも計算量変わる気がする、と思ったが一行増えるぐらいか？二分探索するなら全て数値化しないといけない。

一文字特定するのに二分探索が最良である事を示す→次に複数の文字列を一気に特定するのは1文字ずつ特定するより計算量が多い事を示す→問題は解ける？


とりあえず一文字特定するには二分探索が最良である事を示したい。→よく考えたらlog Nで多項式より小さい。が、最善のアルゴリズムかは不明。
例えばN=128で二分探索未満の特定する方法は存在するのか？無理だと思うが。
二分探索は計算領域を狭めて行く収束速度を考察すると良いかも知れない。

結局探索においてパソコンは命題の真か偽の判定をするだけである。命題のブール値を返すだけである。
0401１３２人目の素数さん
垢版 |
2022/05/14(土) 00:40:08.69ID:njzFtL4x
log(N!)はo(N^2)だから多項式計算量だけど
多項式ってのは2次式でも3次式でも1000次式でもいい
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況