0

したがって、2n 個の変数を持つブール式 Q を指定しました。Q(x1...xn,y1...yn) で表され、{0,1} に属する a1....an が存在することが言及されています。 {0,1} に属するすべての b1...bn に対して Q(a1...an,b1,....bn} が true と評価されると、問題は、これが PSPACE および U DTIME(2^ kn) 複雑度クラス。

これは、プレイヤー A が勝利戦略を持っている 2 プレイヤーのようなものだと思います。指数時間と多項式空間を取るプログラムを書くことができれば、それを解決します。

プレーヤー A に選択肢が存在する場合、つまり、ai の値を 0 と 1 から選択した後、バイ プレーヤー B がどのような値を選択しても、0,1 の値を与えても、式は常に true と評価されます。

だから私はの条件で考えています

for ai=a1 to an
{
flag =true;
for j=0 to 1
{
set ai =j;

//check all possible combination of bi's and check the formula
//if formula evaluates to false ,set flag =false and break,
//try the next j for ai;

}

//if flag =false then ai is not a good selection ,select another ai
//if flag =true yes we have a good selection of ai ,
//player 1 will always win in this case
return true and break;

}

このアプローチは正しいですか、同じアプローチを使用してbiのすべての組み合わせをチェックできますか

for bi=b1 to bn
{
for j=0 to 1
{
//evaluate formula here
//but the problem is i do not have all the values of ai's
// i have only one value of ai ,what will i substitute for the rest
}

}

この種の問題に取り組むための提案や新しいアプローチを歓迎します

4

1 に答える 1

0

DTIME(2**2n) です。ブルート フォース アルゴリズム:

//requires n bits space, 2**n iterations of check() or 2**2n time total
loop over all possibilities to choose (a1,...,an):
    if (check(Q, (a1,..., an))):
        return (a1,...,an);

return null

check(Q, (a1,...,an)):
    //requires n bits space, 2**n iterations
    loop over all possibilities to choose (b1,...,bn):
        if (! Q(a1, ..., an, b1, ..., bn)):
             return false
    return true
于 2013-03-10T19:01:01.450 に答える