0
$\begingroup$

Suppose we have given a 0.12 approximation algorithm for MAX-CLIQUE is an efficient algorithm that on an input graph G with optimal solution of size 𝑘, returns a clique of size at least 0.12⋅𝑘.

My question is: is the following conjecture true?

if there exists a language L that is not in EXP and is not NP-hard, then there is no 0.12 approximation algorithm for MAX-CLIQUE.

$\endgroup$
1
  • $\begingroup$ If $P \ne NP$, then there are languages that are not even decidable, and yet not NP-hard; see this answer. If $P=NP$, then every language $L$ is NP-hard unless $L$ or its complement is empty. So your question is whether the approximation algorithm would imply that $P=NP$. $\endgroup$ Commented May 12 at 20:30

1 Answer 1

Reset to default
2
$\begingroup$

It's known (see proof here, although I couldn't find original paper or textbook) that approximating max clique with constant factor is NP-hard.

Consider two possibilities.

  1. $\text{P} = \text{NP}$. Then, any non-trivial language $L$ is NP-hard, and so there is no language not in EXP that is not NP-hard, so your conjecture is vacuously true.
  2. $\text{P} \neq \text{NP}$. Then there is no $0.12$ approximation algorithm for MAX-CLIQUE, and so your conjecture is again true.
$\endgroup$
6
  • $\begingroup$ See doi.org/10.1145/273865.273901 for an early citation, although more recent papers have even stronger results. $\endgroup$ Commented May 12 at 21:13
  • $\begingroup$ Thanks. One little confusion, would you tell me am I correct or not? If I take contrapositive of my conjecture(if there is 0.12 approximation algorithm for MAX-CLIQUE then there exists a language L that is in EXP or is NP-hard) , then implies P=NP, L is NP hard. Am I correct? $\endgroup$ Commented May 12 at 21:35
  • $\begingroup$ approximation algorithm for MAX-CLIQUE is NP-hard. So my question how it would imply that P=NP? Are you considering polynomial time algorithm? $\endgroup$ Commented May 12 at 23:10
  • 1
    $\begingroup$ Contrapositive would be "if there is an algorithm, then any language is in EXP or is NP-hard" - you need to switch quantifier. Yes, I am considering polynomial-time algorithms, it's pretty obvious that there are exponential approximation algorithms for MAX-CLIQUE. $\endgroup$ Commented May 12 at 23:29
  • $\begingroup$ My final confusion "language L is NP-hard, and so there is no language not in EXP that is not NP-hard"-- would you explain this line? How can you say "there is no language not in EXP that is not NP-hard" from "L is NP-hard" ? What does mean "not NP-hard "? Is it more easy NP hard? $\endgroup$ Commented May 13 at 0:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.