ニコニコ大百科: 「P≠NP予想」について語るスレ 61番目から30個の書き込み

P≠NP予想

について語るスレ

記事をみる

100

3/4

61 ななしのよっしん非表示

2014/08/16(土) 03:16:35 ID: IGUn6q/Gwt

最後に。
>>55から一貫してそうですが、私は単純に「記事分割の前には提案を　“行った”　'方が'　“よかった”　のではないか」と疑問に思い、また他の読者・編集者はどのように思うかが知りたくて書き込んだに過ぎず、
「アルゴリズム」と「P≠NP予想」の2記事に関して「　“これから“　どうす　'べき'　か」ということを言いたいのではありません。
deadbullさん、あるいは他の編集者の方に、両記事を「戻してほしい」とか「こう編集してほしい」などと思っている訳では、一切ないのです。

ですので、「完全なる実現」をすべき私の「主張」というものは、特にありません。
敢えて言えば「私一人ではなく、もっと多くの人の考えを聴く機会（例えば時間的猶予）を設けた方がいいのでは」、くらいでしょうか。（もちろん、これも「両記事を今後このようにしてほしい」という「主張」ではありません）
👍
0
👎
0
62 ななしのよっしん非表示

2014/08/16(土) 11:24:09 ID: I4k3lAeepk

>>61
> また他の読者・編集者はどのように思うかが知りたくて書き込んだ
>>55は反語表現にあたると思いますが、趣旨は了承しました。

>私は単純に「記事分割の前には提案を　“行った”　'方が'　“よかった”　のではないか」と疑問に思い、

やらないよりはやった方がいいに決まっているので、そういう恣意的な質問のを立て方をした時点であなたの中ではもう結論が決まっているように思いますが、
>>59で既に釈明しているように、本件では必須ではない(1.やるべき, 2.やった方がよいがやらなくてもよい,3.やってもやらなくてもよい,4.やらない方がよいがやってもよい,5.やるべきでない、のうちの2〜3番目)というのが当方の見解です。

>敢えて言えば「私一人ではなく、もっと多くの人の考えを聴く機会（例えば時間的猶予）を設けた方がいいのでは」、くらいでしょうか。

[「完全なる実現」をすべき私の「主張」]ではない感想として受け取りました。
>>56で示した期間の経過を以てご指摘の機会(もしくは機会を提供する機会)は提供されたものとして編集を再開いたします。
👍
0
👎
0
63 ななしのよっしん非表示

2014/10/07(火) 12:02:57 ID: l1m7NHy/y7

記事の内容は素晴らしいと想うのだけど、掲示板やらお気に入りやらの継承の点からも、
なんでこんな面倒な移動やら改名やらをしたのか意図がよく解んないなー。

あと編集者は威圧的過ぎね。たとえそういう心算が無くても、傍目にゃ十分そう視えます。
もうちっとほんわかレスを念頭に頼んますわ。
👍
0
👎
0
64 ななしのよっしん非表示

2014/11/03(月) 01:22:41 ID: c2wK8BadNo

わかりやすくて読みやすい記事だな～、と思いました。
こりゃすげーや、書いた方乙です
👍
0
👎
0
65 ななしのよっしん非表示

2014/12/23(火) 17:05:44 ID: PvmaIIfsV1

> 不正確な表現を許すなら「難しい問題を簡単に解く方法は存在しない」という予想
不正確すぎじゃね、「簡単に解く方法が存在しない難しい問題が存在する」とかだろ
👍
0
👎
0
66 ななしのよっしん非表示

2015/03/07(土) 20:08:23 ID: /yQWQ+pjr7

>>65
それだとNP困難の説明が近いのでは？
「解くことに比べて、正答であることを証明することが困難な問題がある」という予想
もしくは
「解くことは簡単だが、逆算が困難である問題がある」という予想
じゃないかな

数学的には因数分解が代表例で
「13 * 17 = 221」は簡単に計算できるけれど、221の因数分解はそれに比べて難解である
👍
0
👎
0
67 濱崎理優非表示

2015/04/01(水) 20:38:50 ID: 39yrU5CQWZ

66番さん分かりやすい解説ありがとう。
この感謝の気持ちを伝えるには余白が狭すぎ・・・おっと誰かきたようだ。
👍
0
👎
0
68 ななしのよっしん非表示

2015/09/21(月) 04:26:15 ID: Vh/dPrg8Le

言っちゃ悪いけど、うまくたとえたりしようとして逆にいろいろずれてきてわかりにくくなってる記事だなあ・・・

リンクになっちゃうけどhttp://www.nikkei-science.com/201212_060.htmlみたいな方が明快でいいとおもう
👍
0
👎
0
69 ななしのよっしん非表示

2016/02/18(木) 23:03:21 ID: 8/UJzF0G/F

そうか？この記事のほうが分かりやすいぞ
👍
0
👎
0
70 ななしのよっしん非表示

2016/02/26(金) 02:12:44 ID: BOpNY1aTGm

数学全然やってないけど俺も>>68のほうがわかりやすい……。
答えが分かっている人間だったら｢ああ、ここはあれを噛み砕いて言ってるんだな｣って分かると思うんだけど、全くの初心だとP≠NP予想って言葉が何を示すのか全く分からないし、解説で出てくる言葉も分からないから、各章で出てくるそれぞれの単語に対応してるのか？って思いながら読んだ。(順を追うにしてもどこが終着か分からないから全ての項目にP≠NP予想の核心があると思いながら読む)
各章毎にP≠NP予想ってこれか？違うのか？これか？違うのか？ってのを最後のNP≠P？の項目を読むまで繰り返してる状態。(これNP問題状態？)

>>68みたいに簡潔に結論言ってくれた後にこの記事の東京駅から大阪駅に着くには総当りみたいな例示なら分かりやすいと思う。
👍
0
👎
0
71 ななしのよっしん非表示

2016/02/29(月) 12:21:24 ID: ZgxmkwZbrN

図らずもこの記事文章に関してもP≠NP問題みたいのことになってるのな
👍
0
👎
0
72 ｎの３乗非表示

2016/07/09(土) 21:40:29 ID: fAGxrQumeV

P=NPだとしたら、ビジービーバー関数がどこまで求められるかわかるはずだと思う
👍
1
👎
0
73 ななしのよっしん非表示

2016/07/13(水) 12:46:30 ID: 8pvMa11QHm

わかりやすい記事を作るのには試行錯誤しなきゃいけないけど、その記事がわかりやすいかは上から読むだけでわかるってのがNPってことでおｋ？
👍
0
👎
0
74 P≠NP予想は半分だけ解けたが、それ以上が謎である。非表示

2016/08/20(土) 15:09:52 ID: 280zJmGnbM

P≠NPの証明式を組み替えればP=NPの証明も可能である事は証明できる
👍
0
👎
0
75 ｎの３乗非表示

2016/09/15(木) 17:02:52 ID: fAGxrQumeV

ビジービーバー関数をΣ(n)とすると、
Σ(0)=0
Σ(1)=1
Σ(2)=4
Σ(3)=6
Σ(4)=13
という既知の値が求められている模様

Σ(5)は4098以上らしいので、
P≠NP予想が正しいとすれば、
Σ(4098)の値も簡単に計算できそう
👍
0
👎
0

76 ななしのよっしん非表示

2016/10/06(木) 02:23:49 ID: 0142LYDCnq

適当
タイトル:P≠NPの時の集合
77 ｎの３乗非表示

2016/10/20(木) 05:51:07 ID: fAGxrQumeV

ゼロ除算がWell-Defined出来ればP≠NPが正しいはず・・・
👍
0
👎
0
78 ななしのよっしん非表示

2017/02/04(土) 07:41:52 ID: iKBtQfFAPw

「時間」によって定義したほうが個人的には好き。

P問題とは、解き方が与えられた時に、解けるまでにかかる最大時間が計算しやすい問題。
NP問題とは、ある解答が与えられた時に、解答の正しさの証明までにかかる最大時間が計算しやすい問題。

具体例
「72899は２つの素数の積であるか」という問題について考える。

P問題であるかを考える。
これは、「０以上72899以下の素数を総当りでかける」解き方が存在し、それが解けるまでの時間を計算しやすいのでP問題。

NP問題であるかを考える。
これは、「０以上72899以下の素数のうち、いずれか２つの積である」という解答があったとき、これを確かめるまでにかかる時間を予想しやすいのでNP問題。

P≠NP予想とは、解き方と解答は別であるという予想であり、多くの数学者はこれが正しいと支持している
👍
0
👎
0
79 ななしのよっしん非表示

2017/02/04(土) 07:48:44 ID: iKBtQfFAPw

「最大時間が計算しやすい」という言葉について、少しだけ厳密に定義しておくと、「多項式時間である」ということ。

xを問題の長さとした時、
多項式時間：　x^2　など
指数関数時間：　10^x　など　

計算時間が指数関数時間となる問題は、x(問題の長さ)が増えるにつれて爆発的に時間が増えるので計算には適さない。
👍
0
👎
0
80 ななしのよっしん非表示

2017/02/12(日) 00:22:02 ID: 0142LYDCnq

でも非決定性チューリングマシンで多項式時間かどうか論じる必要があるっていうね…
👍
0
👎
0
81 ななしのよっしん非表示

2017/02/13(月) 22:08:52 ID: S7d2jNA4xe

P＝NPもP≠NPも両方証明可能って聞いたけどどうなん？
👍
0
👎
0
82 ななしのよっしん非表示

2017/03/12(日) 19:18:09 ID: +AQ8yzQXWf

量子コンピュータで全部解決（思考放棄）
👍
0
👎
0
83 ななしのよっしん非表示

2017/03/18(土) 20:19:18 ID: 0142LYDCnq

量子コンピュータも決定性チューリングマシンなんやで…
👍
0
👎
0
84 ななしのよっしん非表示

2017/04/22(土) 22:09:20 ID: 54Pw9wZ2Al

>>81
オラクルを使ったDTMで、そうなるみたいだね。
NPやらNP困難みたいなクラスの階層まで表現する言語なんて、
ちょっと考えてみても既存の数学なり常識を
刷新する物だろうから、当然なんだろうけど。

つまりP=NPか、P≠NPに関する言語のどちらかが、古典になる
（これまでの数学、常識、価値観、引いては自然解釈）。
この事からも、P≠NP予想は異質な未解決問題。

そしてやはり当然ながら、より具体的なクラス
（SPACEとかTIME）からのアプローチが成されても、
扱いたい問題が難しすぎて（しらみ潰し問題以上に難しい）、P≠NP予想に繋がらない。
👍
0
👎
0
85 ななしのよっしん非表示

2017/08/15(火) 18:58:06 ID: +UNfekPd/3

https://arxiv.org/pdf/1708.03486.pdf
信じがたいことだが、証明されたらしい。誰か英語の読める猛者はおらぬか…？
👍
0
👎
0
86 ななしのよっしん非表示

2017/08/17(木) 22:21:45 ID: UKvsb/6mQV

英語はチョットデキルけど数学がよぐわがんにゃいです
というか計算機科学分野の最先端なんだから分野外の人間が読んでも証明の妥当性の検討なんてできないってそれいち
あとその論文が投稿されたサイトは査読なしらしいからそこまで確実性はないよ
👍
0
👎
0
87 ななしのよっしん非表示

2017/08/18(金) 04:18:15 ID: +UNfekPd/3

↑うん知ってる。でも他でもないグリゴリー・ペレルマンというとんでもねー例外がおるのでな。
👍
0
👎
0
88 ななしのよっしん非表示

2017/08/18(金) 05:16:05 ID: vKq1Ikea2u

準最適解が求められればそれでいいや
👍
0
👎
0
89 ななしのよっしん非表示

2019/09/11(水) 19:44:04 ID: P3i1i75OhM

東京から大阪にインド経由で行くやつ

響良牙かな?
👍
0
👎
0
90 ななしのよっしん非表示

2021/02/01(月) 17:58:17 ID: 8vQG5dX6U1

>このように、「コンピュータに解かせるには難しすぎるアルゴリズムしかない問題」のことをNP問題という。

この説明だとPに含まれる任意の決定問題、それどころか例えば与えられた自然数が偶数かどうかを問う判定問題すらも「コンピュータに解かせるには難しすぎるアルゴリズムしかない問題」とやらになるけどそれでいいんですかね。(というかすぐ↓の説明と明らかに相反する説明...。)

>もっと厳密に言えば、非決定性チューリングマシンによって(多項式時間[1])解ける問題のことをNP問題という。
👍
0
👎
0

3/4

TOP