アルゴリズム理論

アルゴリズム関連スレが無いので立ててみました。

グラフ、近似、量子、オンライン、ゲーム理論、Embedding,
アルゴリズムに関連する話題ならなんでもOK。

STOC, FOCS などの最近の結果について語れたらうれしいなぁ。

さっそく自分で２ゲッツ！

今丁度マイアミでSODAが開かれていますね。

プログラムを見た感じでは、最近の流行は
* Algorithmic Game Theory
* Graph Embedding
* Property Testing
ってところでしょうか。
Exact Algorithm の結果が増えてきているのも注目です。

とりあえず参考書

アルゴリズムイントロダクション
http://www.kindaikagaku.co.jp/bookdata/ISBN4-7649-0245-1.htm

近似アルゴリズム
http://www.springer-tokyo.co.jp/content/isbn4-431-70991-6.html

組合せ最適化
http://www.springer-tokyo.co.jp/content/isbn4-431-71183-X.html

離散幾何学講義
http://www.springer-tokyo.co.jp/content/ISBN4-431-71041-8.html

下の二つは最近でた訳書。

これって数学なの？

数学だよ。

上に上げた
> * Algorithmic Game Theory
> * Graph Embedding
> * Property Testing
や近似不可能性の理論なんかは、十分数学的に深みのある分野だと思っている。

数学ではないかもしれないけど、やるとしたらこの板しかない現実。

確かにぬるぽだな

情報システム
http://science4.2ch.net/infosys/

そこはSE板だよ

いまだにクヌースの本がバイブルなの？

いま Vol.4 書いてて、一部の章は既に出版されてるよね＞Knuth御大

同じ内容を扱った、より良い本が出ていないのか？
という意味なら、無いと思う。
これだけの質と量の本は見たことが無い。

内容が古びてないか、という意味なら、それも無い。
アルゴリズムやる上での必修科目みたいなもんだからね。

あんま実践で使わんけどな

http://sidhes.hp.infoseek.co.jp/alg.htm
↑アルゴリズムこうしん

http://sidhes.hp.infoseek.co.jp/alg3.htm
↑アルゴリズムたいそう

5 名前：１３２人目の素数さん[sage] 投稿日：2006/01/22(日) 20:50:07
数学だよ。 (ry

6 名前：１３２人目の素数さん[sage] 投稿日：2006/01/22(日) 23:23:24
数学ではないかもしれないけど (ry

どっちよ？

数学だよ。

数学じゃないよ

ど、ど、どっちなんだよぉ・・ｳﾜｧｧ━━━━━｡ﾟ(ﾟ´Д｀ﾟ)ﾟ｡━━━━━ﾝ!!!!

計算機代数やってる俺もここでいいのかな？

DP がキャッシュつき再帰にできない例ってありますか？

再帰で解けるってのがDPの本質だし、
キャッシュをするかどうかはこっちの自由だから、
「できない」っことは無いんじゃない？

それで、これは数学なの？

数学っすよ。

数学じゃないっすよ。

そんなのどっちでもいいじゃん。なんかネタないの？

692

まず、簡潔に表現するために、以下の図形を付け加えます。
2，3，4，5，6，7，8，9
さらに、通常の数項の表し方と同じ記号で紛らわしいですが、0，1をあわせて、数字とでも呼んでおきましょう。
次に、数図形というものを、以下のように帰納的に定義します。
（１）数字は数図形である。
（２）Ａが0でない数図形で、qが数字の時、Ａqは数図形である。
数図形は１つ以上の数字が並んだ図形で、一番左が0でないものになります。
この並んでいる数字の個数を数図形の長さと呼びましょう。
数図形の長さが1の時、数図形は数字であり、数図形Ａの長さが1でない時、
Ａ＝Ａ｀q，Ａは0でない数図形。
と表すことができます。このとき、Ａ｀の長さはＡの長さより小さくなります。

失敗。もう一度最初から。
自然数に数項ってのがありますよね。
（１）0，1は数項である。
（２）xが0でない数項の時、x＋1も数項である。
で帰納的に定義されるものです。（書いてないですが、慣例的に『以上でできるもののみが数項である』という意味も含まれています）以下では、数項は必ず（）で括って書くことにします。
（（0），（1），（1＋1＋1）,（x）のように）
実は、この数項を短く簡潔に表現するアルゴリズムを考えました。ちょっと見てみてください。


まず、簡潔に表現するために、以下の図形を付け加えます。
2，3，4，5，6，7，8，9
さらに、通常の数項の表し方と同じ記号で紛らわしいですが、0，1をあわせて、数字とでも呼んでおきましょう。
次に、数図形というものを、以下のように帰納的に定義します。
（１）数字は数図形である。
（２）Ａが0でない数図形で、qが数字の時、Ａqは数図形である。
数図形は１つ以上の数字が並んだ図形で、一番左が0でないものになります。
この並んでいる数字の個数を数図形の長さと呼びましょう。
数図形の長さが1の時、数図形は数字であり、数図形Ａの長さが1でない時、
Ａ＝Ａ｀q，Ａは0でない数図形。
と表すことができます。このとき、Ａ｀の長さはＡの長さより小さくなります。

そして、数字から数図形への対応として、

s^*（0）＝1
s^*（1）＝2
s^*（2）＝3
s^*（3）＝4
s^*（4）＝5
s^*（5）＝6
s^*（6）＝7
s^*（7）＝8
s^*（8）＝9
s^*（9）＝10

と定めます。
このs^*を用いて、数図形間の対応sを、以下のように定めます。
s（Ａ）＝s^*（Ａ） （Ａが数字の時）
s（Ａ）＝Ａ｀s（q）（Ａ＝Ａ｀q、qはq≠9である数字の時）
s（Ａ）＝s（Ａ｀）0（Ａ＝Ａ｀9の時）

以上で準備ができました。数項(x)について、Rep（(x)）を以下のように定義します。
（１）Rep（(0)）＝0
（２）Rep（(1)）＝1
（３）Rep（(x＋1)）＝s（Rep（(x)））

例えば、

Rep（(1＋1＋1)）＝s（Rep（(1＋1)））＝s（s（Rep（(1)）））＝s（s（1））＝s(2)＝3
となり、

Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）
＝s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））
＝s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））
＝s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））
＝s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））
＝s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））
＝s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））
＝s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））））
＝s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））））
＝s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））））））
＝s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1)）））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1)）））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1)））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1)）））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1)））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1)）））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1)））））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1)）））））））））））））））））））））

＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（1））））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（2）））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（3））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（4）））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（5））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（6）））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（7））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（8）））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（9））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（10）））））））））））

＝s（s（s（s（s（s（s（s（s（s（1s（0）））））））））））
＝s（s（s（s（s（s（s（s（s（s（11））））））））））
＝s（s（s（s（s（s（s（s（s（1s（1））））））））））
＝s（s（s（s（s（s（s（s（s（12）））））））））
＝s（s（s（s（s（s（s（s（1s（2）））））））））
＝s（s（s（s（s（s（s（s（13））））））））
＝s（s（s（s（s（s（s（1s（3））））））））
＝s（s（s（s（s（s（s（14）））））））
＝s（s（s（s（s（s（1s（4）））））））
＝s（s（s（s（s（s（15））））））
＝s（s（s（s（s（1s（5））））））
＝s（s（s（s（s（16）））））
＝s（s（s（s（1s（6）））））
＝s（s（s（s（17））））
＝s（s（s（1s（7））））
＝s（s（s（18）））
＝s（s（1s（8）））
＝s（s（19））
＝s（s（1）0）
＝s（20）
＝2s（0）
＝21

となります。

同様にして、
Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1）＝114
となります。
特に下の例のように、多くの場合、数項(x)をRep（(x)）で表せば、
非常に短く簡単に数項が表現できます。実際には、メモリーに記憶
させておくなど、さらに効率を上げる手段を併用しておくといいか
と思います。
私はこの発明を広く世界中の人に使ってもらいたいと思います。特
許をとればおそらくボロ儲けでしょうが、そんなせこいことは言い
ません。私のこの大発明を、みんなで人類の財産として使って欲し
いと思います。

あっ、最後の式で後ろの括弧が一個足りないか。まあいいや。

それって数 n に対して、 o(log n) (スモールオーダ) になるんですか?
O(log n) (ラージオーダ) だったら全然必要ないんですけど。

>>35
全然必要ない？驚きました。あなたは
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1
と書く方がいいとおっしゃるのでしょうか？私は、簡潔に
100
と書く方が楽だし、わかりやすいと思います。

そうですねえ。記憶の活用ですが、このような方法は如何でしょうか？
まず、各数字について、
call（0）＝れい
call（1）＝いち
call（2）＝に
call（3）＝さん
call（4）＝よん
call（5）＝ご
call（6）＝ろく
call（7）＝なな
call（8）＝はち
call（9）＝きゅう
と定義しましょう。そして、長さが1でない数図形に対しては、
その図形の長さに対応して同じく文字列を対応させます。
そうですねえ。長さが1の次に短いときは、”じゅう”とでもしましょか。
その次に短いときは”ひゃく”なんていいかも。
で、Ａに対応するこのような文字列をketa（Ａ）としましょう。

また、数図形の定義（２）で、「Ａが0でない数図形で」を「Ａが数図形で」に置き換え
たものを、準数図形と呼ぶことにしましょう。準数図形Ａに対し、
st（Ａ）を以下のように定めます。
st（0）＝φ
st（Ａ）＝Ａ（Ａが0でない数図形の時）
st（Ａ）＝st（Ａ｀）（Ａ＝0Ａ｀の時）


このとき、数図形Ａ＝qＡ｀に対して、(qは0でない数字、Ａ｀は準数図形）

call（Ａ）＝keta（Ａ）call（Ａ｀）（q＝1のとき）
call（Ａ）＝call（q）keta（Ａ）（q≠1で、st（Ａ｀）＝φのとき）、
call（Ａ）＝call（q）keta（Ａ）call（st（Ａ｀））（q≠1で、st（Ａ｀）≠φのとき）、

とさだめます。例えば、
call（124）＝keta（124）call（24）＝ひゃくcall（2）keta（24）call（st（4））
＝ひゃくにじゅうcall（4）＝ひゃくにじゅうよん
call（203）＝call（2）keta（203）call（st（03））＝にひゃくcall（st（3））
＝にひゃくcall（3）＝にひゃくさん
call（50）＝call（5）keta（50）＝ごじゅう
となります。

このような方法で数項を表現する数図形に対し文字列を対応させます。
そして、ここからが提案なんですが、小さい子供の頃から、数項の小さい方から順に
読む習慣をつけてみたらどうでしょうか？たとえば、お風呂に入ったら、
「call（1）からcall（100）まで読まないと、お風呂から出てはいけませんよ。」
と躾てあげるのです。最初は嫌がるでしょうが、これによってしっかりとお風呂で暖まる
ことができ、また、数項に対応した数図形を、対応する文字列を通じて記憶することがで
きるのです。どうでしょうか、このアイデア？

あなたの方法を使わなくても私は数 n を Θ(log n) の長さで書く
方法を既に知ってますので、無理に別の方法を使う必要は感じません。

>>38
数項nですね。間違えないようにしましょう。
で。具体的にそのアルゴリズムを正確に書いてみてくれませんか？

s をsuccessorとし，s(1) を 2 と書く，s(2) を 3 と書く，……，10進数表記を用いる．

ということを面倒に言い直しただけだろ

>>40
実行してみてください。もちろん、……で誤魔化したりしないでね。

あと、数項をああ書いてるんだから、ＰＡだってわかるでしょ？
理論にないsuccessorを使うなら、まずはきちんと定義しましょうね。

>26 は「最後まできちんとできたね。おりこうさん」と言って欲しいだけだろ。

いや、偉そうに言うわりにはこの程度のこともできない厨に対し苦笑してるだけだよw

>>44

ところでそれのどこが「アルゴリズム」なの？
>>1 で例示されてるものとあまりにも乖離してない？

別に>>1の例示にこだわる必要なんか無いだろ？なんつーか、もう少しがんばってくれよ。
せっかく苦労して書いた甲斐がないよw

>>37
嬉しがって準数図形とやらを導入したならちゃんと使ってくれんかね？
stの定義が読みにくくてしょうがない。やりなおせ。

まず自分がやれよwホント口先だけで何もできないヤツだな。

>>37
ketaの定義があいまいで全くなってない。もっと形式的にやってもらわないと
アルゴリズムとは言えない。

call（50）＝call（5）keta（50）＝ごじゅう

とあるが、正直なところcallが数字をわりあてる基底段階がおお過ぎて何がし
たいのかわからない。

俺のみたとことでは、古典的な算術の劣化変形版にしか見えない。
ペアノ算術と比較して、数学的になんの成果が期待できるの？
実際に使うなら、ペアノ算術のほうが規則が少なく、かつ登場人物も少ないの
で、研究のためにはいいわな。
子供のころから「数項」がうんぬんは気違いの冗談にしか思えない。

>>37
call(100)を計算してみたら変なことになったよ。
ちゃんと定義できてないじゃん。

> このとき、数図形Ａ＝qＡ｀に対して、(qは0でない数字、Ａ｀は準数図形）
>
> call（Ａ）＝keta（Ａ）call（Ａ｀）（q＝1のとき）
> call（Ａ）＝call（q）keta（Ａ）（q≠1で、st（Ａ｀）＝φのとき）、
> call（Ａ）＝call（q）keta（Ａ）call（st（Ａ｀））（q≠1で、st（Ａ｀）≠φのとき）、
> とさだめます。

ＡとＡ｀は丁重に使いわけてもらわないと使いものにならない。

call(100)=keta(1)call(00)=keta(1)call(0)keta(00)call(st(0))
=keta(1)れいじゅうcall(φ)
=いちれいじゅうcall(φ) (しかたがないからketa(1)を「いち」と簡約した)
=...
で、call(φ)はどうやって簡約するの？

>>49
やっとまともっぽい突っ込みが来たな。ただ、これがダメなら数学基礎論で使うような
ある種のアルゴリズムはアルゴリズムでないってことにもなる。有限の立場の数学って
勉強したことある？
　それと。これを劣化板と言うからには、君はもちろん普段から
5×4＝20
と書かず
（1＋1＋1＋1＋1）・（1＋1＋1＋1）＝（1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1）
と書いてるってことだよねw僕にはまねできないな。

>>50
定義を見て再現できないなら、あんまり偉そうな口を利かない方がいいと思うぞ。
見ている方が恥ずかしくなる。俺なら、call（300）とかに突っ込みを入れるがw

こういうのは麻疹のようなものだけど、随分と古い病気にかかったね。

# call(100000) と call(110000) は？

そうそう。そういう突っ込みなら大歓迎w
まだそこまで定義できてないから百までで誤魔化してたの。読みの部分は思い付きみたいにその場で書いたんで、かなりツメは甘い。なのにまともな突っ込みがなくて寂しかったよw
しかしどうすればいいかね？4つずつ区切ればいいんだが、それをキチンと定義するのは面倒なんだわ。誰かやってみない？

やらねーよw

すまん。計算間違ってたか。情けない。
やり直して出直してくるわ。

>>36
もしかして「数n」を計算機が蓄えるときに、
本当にn個の記憶素子が使われてると思ってるんですか？
>>35さんは、今の（というか何十年も大昔から）計算機では
数は普通に2進数で格納されてるから必要ないよ、と言ってるのかな、と思うんですが

万が一、10進位取り表記法をあなたが一から再発見したなら確かにすごいけどｗ
その割には説明中で普通に使ってますからねえ。。

そもそも「数項」ってのはキソロンとやらでは使うかもしれないけど
アルゴリズムの理論で使うのかなあ。。

>>38
数項nを表記して何の役に立つんですか？

>>56
いまいちノリが悪いヤツだな。まあいいや。
ところで、

>万が一、10進位取り表記法をあなたが一から再発見したなら確かにすごいけどｗ
>その割には説明中で普通に使ってますからねえ。。

これどこ？相当気をつけたつもりだったんだけど。

> そもそも「数項」ってのはキソロンとやらでは使うかもしれないけど
> アルゴリズムの理論で使うのかなあ。。
基礎論でもnumeral termなんていう単語は使わない。
ShoenfieldもTroelstraも松本和夫も使ってない。
彼の脳内でしか通用しない造語だろう。
しかもあまり日本語も達者ではないようで、数図形だのなんだの言ってるね。

> 自然数に数項ってのがありますよね。
こんなこと言われても困る。

numeralは使いますね
日本人では廣瀬・横田の『ゲーデルの世界』とか
田中一之の『数の体系と超準モデル』はnumeralの訳語に「数項」という単語を当てている
倉田の『入門数学基礎論』でも使ってる（p124など）

まあ数を表す項だから「数項」は訳語として合格じゃないのかな
ただそれならnumeralwiseも数項ごとに、とか任意の数項が、どの数項も、
となるべきと思うが

高橋昌一郎は「数値」という語を当てているけどこれは明らかにまずいような

困るのは同意ね

> >>38
> 数項nを表記して何の役に立つんですか？
ここが気になる。
数項でもなんでもいいけど、文字列変換して何がしたいわけ？

>>58>>59
そうか。サンクス。俺は畑違いでその手の感覚はわからないんで。数項って一般的じゃないんだ。勉強になったよ。
まあ、>>59の言ってるような本で俄か勉強したクチなんで勘弁してくれw
分野が違えば複数の人が書いている用語を一般的と思うのは許容範囲でしかたないだろ？一応定義は書いたから誤解もされないだろうし。
しかし、ネタでもなんでも書いてみるもんだな。思わぬ収穫だったよ。ありがとう、お二人さん。

当然のことですが、Shoenfield の本に numeral は出てきます。
索引にも載っている。

>>58の脳内には別世界のキソロンがあったと言うことでFA？

単に訳語がどの程度使われているかを知らん買った、ってことじゃないかな
numeralって単語は知ってたっぽい

若いうちはこんな勇み足がままあるもの。元気があってよろすぃ。

http://science4.2ch.net/test/read.cgi/math/1072058641/683
ここにもお仲間がいるようだしな。恥ずかしがる必要はない。

>>64
松本和夫はnumeralを数字と訳している。
竹内外史が数項という単語を使っていた記憶はない。
国内の研究集会でnumeralを数項と訳していたことはない。
現在この分野は日本が後手に回っているので、正確を期すときには
英語のまま「ニューメラル」などと言う場合が多い。

以上を踏まえて、数項とか数図形という単語について私見を述べた。

>>58
なら、
>彼の脳内でしか通用しない造語だろう。
なんて勝ち誇ったようなセリフを言わなければ済んだことだろうよ。
もう少し謙虚になろうや、お互いに。

>>58は>>68の間違い。まあ、引用部分は丁度>>58ではあったが。

でもなんか竹内外史って滅多に訳語を使わないで
やたら横文字をそのまま使う人ってイメージがあるんだけど

それから数図形なんてネタに決まってるだろうがw
もう少し頭を柔らかくしろよ。そんなんじゃ良い
研究者になれないぞ

竹内外史-山口人生

>>69
俺も冷静さが足りなかったようだ。申し分けない。

330

アルゴリズムの記述の仕方って論文によってまちまちだけど共通のスタイルファイルとかないの？

age

あっちむいてふたりでまえならえ

age

あるアルゴリズムの研究者(すまそ名前忘れた)が言ってたのを
又聞きしたんだが、

「NP-Completeな問題には実用的な近似解アルゴリズムが比較的
多くある。PSPACE-Completeな問題には実用的な近似解アルゴ
リズムはほとんど見つからない。」

だそうだ。そんなもん?
PSPACE-Completeな問題なんて、その辺にいくらでも転がってる
気がするんだけど、みんな実用的時間じゃ解けないの?

2 人ゲームの先手(後手)必勝判定問題はゲームにループがなければ
PSPACE-Complete(ATIME(poly)-Complete)。
オセロが後手必勝かどうかは 6x6 では分かってるけど、
8x8はまだ未解決だと思う。

age

可積分系とアルゴリズムが関係アルらしいね。　不思議だ。

うん。崖の端から外に向かってブロックをどれだけ積めるのかをアルゴリズムを使って証明。

log

380

>>82
> 2 人ゲームの先手(後手)必勝判定問題はゲームにループがなければ
> PSPACE-Complete(ATIME(poly)-Complete)。

すごいいいきりようだな
俺は2人ゲームで先手必勝判定問題がPに属するようなループのないゲームを
いくらでも設計できるが

age

>>88
そうそう。f(x)=x とか自明な充足可能性問題もあるもんね。
インスタンスと問題の区別がつかないと、計算量理論は理解不能だよね。

913

>>82
将棋はループはないが多項式じゃ無理だぞ。
EXPSPACEあれば十分だけど、EXPやNEXPで解けるのかな。

age

>>92
一応マジレスしとくと将棋は定数時間で解けるね
あとはどう一般化するかしだいでしょ

age

>>94
釣りか？

>>96がどういう意味で釣りか？といっているのが気になる

定数時間で解けるわけねーじゃんという意味なのか
定数時間で解けるのは当り前だけど>>92がいいたいのはそういうことじゃねーだろという意味か

もちろん後半だろ？

500

! 100 !

780

803

良スレage

602