0
$\begingroup$

I want to prove that the language $\text{Max-Unique-Clique} = \{<G> | \text{The maximal clique of $G$ is unique}\}$ is in $\Sigma_2^p$ by using the following $\Sigma_2^p$ machine:

  1. The machine guesses $k$ and verifies that there is a subset of size $k$ that is a clique. If not, it rejects.
  2. It verifies that all other subsets of vertices of size $k$ and all subsets of size $k+1$ are not a clique. If both conditions are true, it accepts; otherwise, it rejects.

The correctness of the machine is trivial, but I'm not sure if it qualifies as a legal $\Sigma_2^p$ machine because I want to verify whether: $$\exists k,y_1,\ldots ,y_k\forall z_1,\ldots ,z_k,w_1,\ldots,w_{k+1}M(x,y,zw)=1$$

However, the length of the variables depends on $k$, which may be problematic.

$\endgroup$

1 Answer 1

0
$\begingroup$

I'm not sure what you mean by "$\Sigma_2^p$ machine". If you consider a polytime NTM with a $\mathsf{coNP}$ oracle (i.e. using $\Sigma_2^p = \mathsf{NP}^{\mathsf{coNP}}$), then we only have restrictions on running time (that is, the length of "guessed" witnesses is merely bounded rather than fixed); essentially the same is true for alternating TMs (i.e. using $\Sigma_2^p = \Sigma_2 \mathsf{Time}(\mathrm{poly}(n))$).

From a very technical point of view, you are correct when using the certificate/verifier definition: The class is usually defined such that the length of the witnesses is purely defined in terms of the input length. However, you can easily fix this problem by padding your witnesses. Simply use $n$ bits to encode a subset of the vertices of your graph by setting the $i$-th bit to $1$ iff you wish to specify that the $i$-th vertex (say, in the order they appear in the encoding of the input graph) lies in the set under consideration.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.