アカウント名:
パスワード:
2.9の証明の始め、Corollary 2.5を使うところで説明が飛んでないか?|coPp|=|Pq| や n∈O(m) はどっから来た。n∈O(m)は、n∈O(m^k)(kはrの次数)とかの間違い?
ご指摘のとおり、ここはちょっと間違っていて|coPp|≦|Pq|n∈O(m^k)ですね。この関係はcoPp->Pqの多項式時間単射還元から来ています。この単射が存在するのならば、coPpに対応するPqは高々多項式規模の長さしか違わないので、n∈O(m^k)で|coPp|≦|Pq|となるものが存在します。
v4のTheorem 2.9の証明がおかしい|Pb|≦O((L+c)^k)はTheorem 2.8から導いたんだろうけど、PbがTheorem 2.8を満たすとは限らない。
PaとPbを選ぶと、それに応じて単射rが存在し、またrに応じて、n∈O(L^k)を定めることができ、そのnに応じて、あるP∈ANTI_nが存在し、Theorem 2.8を満たす。つまり、最初のPbの選び方によって、Pが変動しうるため、PbがPになるように、最初にうまくPbを選べる保証がない
なるほど、確かに確定できないですね……Theorem 2.6. を構成するときに気付かずに明示していない条件が入っているようですね。問題の複雑性も落ちているかも。
ちょっと考えてみます。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
開いた括弧は必ず閉じる -- あるプログラマー
Theorem 2.9 (スコア:0)
2.9の証明の始め、Corollary 2.5を使うところで説明が飛んでないか?
|coPp|=|Pq| や n∈O(m) はどっから来た。
n∈O(m)は、n∈O(m^k)(kはrの次数)とかの間違い?
Re:Theorem 2.9 (スコア:1)
ご指摘のとおり、ここはちょっと間違っていて
|coPp|≦|Pq|
n∈O(m^k)
ですね。
この関係は
coPp->Pq
の多項式時間単射還元から来ています。
この単射が存在するのならば、coPpに対応するPqは高々多項式規模の長さしか違わないので、
n∈O(m^k)
で
|coPp|≦|Pq|
となるものが存在します。
Re: (スコア:0)
v4のTheorem 2.9の証明がおかしい
|Pb|≦O((L+c)^k)はTheorem 2.8から導いたんだろうけど、
PbがTheorem 2.8を満たすとは限らない。
PaとPbを選ぶと、それに応じて単射rが存在し、
またrに応じて、n∈O(L^k)を定めることができ、
そのnに応じて、あるP∈ANTI_nが存在し、Theorem 2.8を満たす。
つまり、最初のPbの選び方によって、Pが変動しうるため、
PbがPになるように、最初にうまくPbを選べる保証がない
Re:Theorem 2.9 (スコア:1)
なるほど、確かに確定できないですね……
Theorem 2.6. を構成するときに気付かずに明示していない条件が入っているようですね。
問題の複雑性も落ちているかも。
ちょっと考えてみます。