Max Clique - NP Problem

Question

The question is to show that the recognition version of Clique is in NP.

I have started with a graph G=(V,E) and integer k such that G does have a clique C of cardinality k. How to proceed further from here?

Thanks in advance for any help.

Because of the capital letters, it took me some time to understand that this is not about the recognition by the mathematical community of a guy called Max Clique who claimed to have solved the P=NP problem... — Nikolaj-K, Mar 25 '13 at 09:00

score 2 · Answer 1 · answered Mar 25 '13 at 08:54

2

The idea is that given a set $C$ of vertices, you can check in polynomial time whether $C$ is a clique of cardinality $k$.

answered Mar 25 '13 at 08:54

Robert Israel

Isn't this only half of the problem though? How would I give an evidence of the nonexistence of a $k$-clique that can be checked in polynomial time? – hardmath Dec 30 '16 at 02:13
1

@hardmath NP means that a "yes" answer can be checked in polynomial time. If a "no" answer can be checked in polynomial time, the problem is in co-NP. – Robert Israel Dec 30 '16 at 02:29

score 0 · Answer 2 · answered Mar 25 '13 at 09:02

0

answered Mar 25 '13 at 09:02

gukoff

2 Answers2