解決策と非決定論的検索の問題

充足不可能なCNF式$ F = C_1 wedge C_2 wedge … wedge C_m $
overの変数$ X $に対する各解决反駁$ Pi $は、多項式時間($ Pi
$)を次の検索問題を解決する確定的な分岐プログラム$ P $に変換します。

1)$ P $には、各節$ C_i $に対して1つのソースノードと1つのシンクノードがあります。

2)各アサインメント$ alpha:X rightarrow {0,1 } $には$ P
$の一貫したパスがあります。 ソースノードを$ alpha
$によって改ざんされた節に関連付けられたシンクノードに接続します。

Question: Is there a proof system strictly
stronger than resolution where each proof $Pi$ can be translated
in polynomial time (in the size of $Pi$) into a not
necessarily deterministic
branching program $P$ solving the
search problem above?

ベストアンサー

私が質問を正しく理解していれば、いわゆる Buss-Pudlak
ゲームは、証明システムからそのような決定木への簡単な変換を提供します(Buss-Pudlak ’94 http://math.cas.cz/%7Epudlak/howtolie.ps
)。クエリは数式(変数だけでなく)です。ツリーも完全に確定的です。

リニアディシジョンツリーは、Res(lin)の反駁に対応する(例えば、 http://www.csc.kth.se/~sokolovd/files/papers/splitting.pdf
および http://cs.rhul.ac.uk/home/tzameret/Res-Lin-Two.pdf
)。しかし、他にも多くの例があります(例えば、Tonian PitassiのCP様の証明システムの研究参照)。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です