0

所以我给出了一个带有 2n 个变量的布尔公式 Q。用 Q(x1...xn,y1...yn) 表示，并且提到存在 a1....an 属于 {0,1} 使得对于属于 {0,1} 的每个 b1...bn Q(a1...an,b1,....bn} 现在的问题是证明这是在 PSPACE 和 U DTIME(2^ kn) 复杂度类。

现在我相信这就像两个玩家，其中玩家 A 有一个获胜的策略。如果我可以编写一个需要指数时间和多项式空间的程序，我会解决它。

现在，如果玩家 A 存在选择，则程序应该返回 true，即在他从 0 和 1 中选择 ai 的值之后，无论双玩家 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 回答