アカウント名:
パスワード:
おっしゃりたいことはNTD を導入すると P ⊂ NTD ⊆ PH となる，だから P != PH ってことですか？
でもそれは NTD を導入したからであってNTD以外のアルゴリズム，つまり理想的な アルゴリズム X が見つかればP = X = PHとなりませんか？
証明すべきはそのような X が存在しないことでは無いでしょうか？多くの人はそのようなXは存在しないと信じてますが，存在しないことを証明するのが P != NP のキモだと思います．
コメントありがとうございます。
> NTD を導入すると P ⊂ NTD ⊆ PH となる，だから P != PH ってことですか？
いいえ。問題のクラスで表すとPH ∋ NTD ∉ P--> P != PHですね。
定義１(とSipserの証明)よりP ⊂ 入力長の多項式規模のNNF回路族で計算できる問題のクラス
定理１３よりNTD ∉ 入力長の多項式規模のNNF回路族で計算できる問題のクラス
定理１０よりNTD ∈ PH
から、定理１４にて・定義１、定理１３より NTD ∉ P・定理１０より NTD ∈ PHよってPH ∋ NTD ∉ P--> P != PHを導いています。
たとえばNTD ∉ Pをx(NTD) ∈ Pと変換する x() が存在するとどうなるでしょうか？
個人的には，そんなx()は存在しないと思いますが，その存在を議論することが自体が P!=NP の問だと思います
そのようなxは存在しますが、多項式時間還元にはなりません。
多項式時間還元でx(NTD) ∈ Pとなるxが存在する-->（x(NTD) ∈ Pより）入力長の多項式規模のNNF回路族でx(NTD)が計算できる。-->（xが多項式時間還元となることより）入力長の多項式規模のNNF回路族でNTDが計算できる。となり、定理１３と矛盾します。
「定理１３と矛盾する」とおっしゃっていますがそれは「NTDを計算するNNF回路族の素子数は多項式規模に収まらない。」と決め込んでいるからではありませんか？これは正しくは「今の所，多項式規模還元する方法が見つかっていないだけ」だと思います．
この部分が本証明の肝となります。
定理３より、NNF回路族には（隣の入力のペアの）差分部分のどちらか片方を含む時のみに1になるAND素子が存在。−＞隣の入力のペア毎に1つ以上のAND素子が必要。（さもなければ間の入力を区別できない）
定理１２（及び定理５、８、９、１１）より、NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。
よって、NTDを計算するNNF回路族の素子数は多項式規模に収まりません。
肝というか，DTMをエミュレートしているので自明だと思うのですが…
肝というのは、「隣の入力のペア毎に1つ以上のAND素子が必要」「NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない」−＞「NTDを計算するNNF回路族の(AND)素子数は多項式規模に収まらない」の部分です。
上記は、DTMをエミュレートしているからと言って自明ではありません。
ああいうと、実はこれで。こういうと、これはあれで。
＞「隣の入力のペア毎に1つ以上のAND素子が必要」「毎に」というのはなぜ？その素子は他の入力では反応しないことが証明されるの？
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私はプログラマです。1040 formに私の職業としてそう書いています -- Ken Thompson
確認ですが (スコア:1)
おっしゃりたいことは
NTD を導入すると P ⊂ NTD ⊆ PH となる，だから P != PH ってことですか？
でもそれは NTD を導入したからであって
NTD以外のアルゴリズム，つまり理想的な アルゴリズム X が見つかれば
P = X = PH
となりませんか？
証明すべきはそのような X が存在しないことでは無いでしょうか？
多くの人はそのようなXは存在しないと信じてますが，
存在しないことを証明するのが P != NP のキモだと思います．
Re: (スコア:1)
コメントありがとうございます。
> NTD を導入すると P ⊂ NTD ⊆ PH となる，だから P != PH ってことですか？
いいえ。問題のクラスで表すと
PH ∋ NTD ∉ P
--> P != PH
ですね。
定義１(とSipserの証明)より
P ⊂ 入力長の多項式規模のNNF回路族で計算できる問題のクラス
定理１３より
NTD ∉ 入力長の多項式規模のNNF回路族で計算できる問題のクラス
定理１０より
NTD ∈ PH
から、定理１４にて
・定義１、定理１３より
NTD ∉ P
・定理１０より
NTD ∈ PH
よって
PH ∋ NTD ∉ P
--> P != PH
を導いています。
Re: (スコア:1)
たとえば
NTD ∉ P
を
x(NTD) ∈ P
と変換する x() が存在するとどうなるでしょうか？
個人的には，そんなx()は存在しないと思いますが，
その存在を議論することが自体が P!=NP の問だと思います
Re: (スコア:1)
そのようなxは存在しますが、多項式時間還元にはなりません。
多項式時間還元でx(NTD) ∈ Pとなるxが存在する
-->（x(NTD) ∈ Pより）入力長の多項式規模のNNF回路族でx(NTD)が計算できる。
-->（xが多項式時間還元となることより）入力長の多項式規模のNNF回路族でNTDが計算できる。
となり、定理１３と矛盾します。
Re: (スコア:0)
「定理１３と矛盾する」とおっしゃっていますが
それは「NTDを計算するNNF回路族の素子数は多項式規模に収まらない。」と決め込んでいるからではありませんか？
これは正しくは「今の所，多項式規模還元する方法が見つかっていないだけ」だと思います．
Re:確認ですが (スコア:1)
この部分が本証明の肝となります。
定理３より、
NNF回路族には（隣の入力のペアの）差分部分のどちらか片方を含む時のみに1になるAND素子が存在。
−＞隣の入力のペア毎に1つ以上のAND素子が必要。（さもなければ間の入力を区別できない）
定理１２（及び定理５、８、９、１１）より、
NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。
よって、NTDを計算するNNF回路族の素子数は多項式規模に収まりません。
Re: (スコア:0)
肝というか，DTMをエミュレートしているので自明だと思うのですが…
Re:確認ですが (スコア:1)
肝というのは、
「隣の入力のペア毎に1つ以上のAND素子が必要」
「NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない」
−＞「NTDを計算するNNF回路族の(AND)素子数は多項式規模に収まらない」
の部分です。
上記は、DTMをエミュレートしているからと言って自明ではありません。
いつまでたっても後出し、後出し。 (スコア:0)
ああいうと、実はこれで。
こういうと、これはあれで。
Re: (スコア:0)
＞「隣の入力のペア毎に1つ以上のAND素子が必要」
「毎に」というのはなぜ？
その素子は他の入力では反応しないことが証明されるの？