Cheap and Secure Web Hosting Provider : See Now

# [Solved]: How to prove membership of NP

, ,
Problem Detail:

My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're suppose to do at this step   I understand that you're suppose to verify the correctness of a solution but how do I do that?

#### Answered By : Yuval Filmus

Here are several examples:

1. MAX-CLIQUE: The witness is a set of vertices of given size. The verifier checks that edges connect all pairs of vertices in the set.

2. SAT: The witness is a satisfying assignment. The verifier checks that it satisfies all clauses in the formula.

3. 3COL: The witness is a 3-coloring of the graph. The verifier checks that all edges connect vertices of different color.

4. SUBSET-SUM: The witness is a subset of the set. The verifier checks that the subset sums to the target number.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48416

3.2K people like this