アカウント名:
パスワード:
たとえば> NTDの濃度は多項式規模に収まらない。よって、NTDを計算するNNF回路族の素子数は多項式規模に収まらない。ここの「よって、」は P≠NPを仮定してませんか？
ご指摘ありがとうございます。ここはちょっと修正＆補足が必要そうです。
まず「NTDの濃度は多項式規模に収まらない」の部分ですが、正確には「NTDにある隣の入力のペアの濃度は多項式規模に収まらない」ですね。定理１２もそれに合わせて定理１２NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。に修正した方が良さそうですね……
また、「よって」の部分ですが、定理３：NNF回路には、入力が少なくとも（対応する）差分部分のどちらか片方を含む時のみに1になるAND素子が存在する。−＞NTDのそれぞれの隣の入力毎に、（受理すべき隣の入力の差分部分全体と 拒否すべき間の入力を判別するために）入力がその差分部分全体を含むかどうかを 判定する独自のAND素子を持つ必要がある。
を前提とする「よって」になります。定理３自体はP≠NPを仮定していませんので、この「よって」もP≠NPを仮定していません。
後で説明の補強を考えることにします。＃単純に「定理３より」のような説明を追加する感じですかね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」
暗にP≠NPを前提としてませんか？ (スコア:0)
たとえば
> NTDの濃度は多項式規模に収まらない。よって、NTDを計算するNNF回路族の素子数は多項式規模に収まらない。
ここの「よって、」は P≠NPを仮定してませんか？
Re:暗にP≠NPを前提としてませんか？ (スコア:1)
ご指摘ありがとうございます。
ここはちょっと修正＆補足が必要そうです。
まず「NTDの濃度は多項式規模に収まらない」の部分ですが、正確には
「NTDにある隣の入力のペアの濃度は多項式規模に収まらない」
ですね。定理１２もそれに合わせて
定理１２
NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。
に修正した方が良さそうですね……
また、「よって」の部分ですが、
定理３：
NNF回路には、入力が少なくとも（対応する）差分部分のどちらか片方を
含む時のみに1になるAND素子が存在する。
−＞NTDのそれぞれの隣の入力毎に、（受理すべき隣の入力の差分部分全体と
拒否すべき間の入力を判別するために）入力がその差分部分全体を含むかどうかを
判定する独自のAND素子を持つ必要がある。
を前提とする「よって」になります。
定理３自体はP≠NPを仮定していませんので、この「よって」もP≠NPを
仮定していません。
後で説明の補強を考えることにします。
＃単純に「定理３より」のような説明を追加する感じですかね。