1
$\begingroup$

Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$

  1. Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
  2. If $NP=P$, does $MAX-CLIQUE\in P$?

I cannot think of a polynomial verifier for $MAX-CLIQUE$'s complement. There might not be a max clique of size k due to two reasons:

  1. There's a bigger clique than k (and then the verifier will get such clique and verify it).
  2. There's no clique of size k in the graph (and this is cannot be verified in polynomial time).

Regarding the second question: it's known that $MAX-CLIQUE$ is just $NP-HARD$ and not $NP-COMPLETE$. I understand from that that probably $MAX-CLIQUE \notin NP$, therefore even if $P=NP$, so $MAX-CLIQUE \notin NP=P$.

So does it mean that the answer to all the question is simply "no"?

$\endgroup$
5
  • $\begingroup$ I. What do you mean by complement? A subgraph that doesn't contain max clique? II. No, $\mathsf{P = NP \Leftrightarrow P = PH}$. Since $MAX-CLIQUE \in \mathsf{PH}$ it will be in $\mathsf{P}$ also. $\endgroup$
    – rus9384
    Jul 3, 2017 at 17:55
  • $\begingroup$ By $MAX-CLIQUE$'s complement I mean $\overline{MAX-CLIQUE}$ $\endgroup$
    – iTayb
    Jul 3, 2017 at 18:05
  • $\begingroup$ So, you mean decision variant $MAX-CLIQUE$? Otherwise I have a difficulty in understanding this. There is an $INDEPENDENT-SET$ problem which may seem to be a complement to $MAX-CLIQUE$ but it is not. $\endgroup$
    – rus9384
    Jul 3, 2017 at 18:07
  • $\begingroup$ What is MAX-CLIQUE for you? Can you formally state it? $\endgroup$ Jul 3, 2017 at 18:08
  • $\begingroup$ Of course, sorry. I thought the definition of MAX-CLIQUE is the same everywhere. I've edited the question accordingly. $\endgroup$
    – iTayb
    Jul 3, 2017 at 18:12

1 Answer 1

2
$\begingroup$
  1. $MAX-CLIQUE \in \mathsf{coNP \Leftrightarrow NP = coNP}$.
  2. The answer is yes: your variant of $MAX-CLIQUE$ is in $\mathsf{P^{NP}}$, since knowing the size of max clique you can solve your problem.

There is no polynomial verifier (if $\mathsf{NP \neq P^{NP}}$) for this problem, because it is not in $\mathsf{NP}$.

Classic $MAX-CLIQUE$ which only asks if there is a clique of size at least $k$ is $\mathsf{NP}$-complete. But if $\mathsf{P = NP}$ you can ask a machine if there is a clique of size $|V|, |V| - 1, |V|-2...$ until the answer is "YES" to find max clique. Of course, you can use binary search instead of linear.

So, $\mathsf{P = NP}\Leftrightarrow MAX-CLIQUE\in \mathsf{P}$.

$\endgroup$
4
  • $\begingroup$ There is no polynomial verifier - why is that. $\endgroup$
    – Eugene
    Jul 3, 2017 at 21:07
  • $\begingroup$ @Eugene, this problem is clearly $\mathsf{NP\cup coNP}$-hard: you can solve both $MAX-CLIQUE$ and $\overline{MAX-CLIQUE}$ with it. Also, it can be that $\mathsf{NP = coNP}$. Then polynomial verifier exists. $\endgroup$
    – rus9384
    Jul 3, 2017 at 21:47
  • $\begingroup$ I think there is dubious term usage $MAX-CLIQUE$. OPs definition might have a verifier if $\mathcal{NP} = \mathcal{coNP}$. Anyway, everything is clear to me now. $\endgroup$
    – Eugene
    Jul 3, 2017 at 22:03
  • $\begingroup$ That's what I wrote. Maybe you haven't seen it, as I edited comment. But same is written in the answer: see "if $\mathsf{NP\neq P^{NP}}"$. $\endgroup$
    – rus9384
    Jul 3, 2017 at 22:04

Your Answer

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

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