BoostMatch
BoostMatch

Reputation: 15

What would P=NP tell us for a proof?


An exercise I've been working on is "Prove that there is no efficient 5/4-approximation toChromaticNumber unless P=NP.
My question is what would P=NP tell us? Let's say we "Suppose P=NP" in our proof. Does that mean that there is a 1-approximation algorithm? Or that the polynomial-time verifier is the same as the algorithm itself? A little confused here, any responses are appreciated!

Upvotes: 0

Views: 125

Answers (0)

Related Questions