$\Sigma_k^\text{P}$−SAT definition is not clear to me

363 Views Asked by At

I don't understand if by saying there are $k$ alternating quantifiers on the variables $x_1$,$x_2$...$x_k$, It means we quantify ALL variables (there are only $k$ variables in the SAT formula) or just $k$ of them (so there can be more than $k$ variables) For example, for $\Sigma_1^\text{P}$-SAT, the clause has to be with only one variable who is quantified? It seems like there have to be some free variables left (not under quantifiers) but I'm not sure. (I know TQBF demands no free variables.) Thanks.

1

There are 1 best solutions below

0
On

There are no unquantified variables in SAT. If no quantifiers are explicitly given, the variables default to being existentially quantified.

When $k$ alternations is spoken of in reference to quantified boolean formulas, it refers to the number of groups of variables quantified by $\exists$ or $\forall$, not the number of variables themselves. So for $\Sigma_1^\text{P}$-SAT there is one group of quantified variables, not one variable.