-1

all.

I have some question about proving NP-complete

The conditions of proving problem is NP-complete is following.

1) Problem is in NP

2) Problem is reducible other from NP-Complete Problem (Ex. SAT)

To do condition #1, we use certificate.

My question is this.

When we do certificate, I need to give C(Instance, string of suitable answer). For example, when I certificate Vertex Cover, I need to Instance of V.C (graph, and integer number k which is number of needed cover vertex), and string(the answer)

In this condition, can I give any Instance & k & string? The most simplest example can be done? and its result is "yes". what does it mean "yes"?

Tony_SSU
  • 21

1 Answers1

1

To prove that a problem is in NP, you do not need to provide an actual solution. You just need to prove that the certificate can be verified in polynomial time.

In your example, a "certificate" would be a set of k vertices, $S=\{v_1, v_2,...,v_k\}$. You do not need to actually specify what these k vertices are.

A simple graph (i.e. no repeated edges) with n vertices has at most $n^2$ edges $(v_i, v_j)$ for $i, j=1..n$ and $i \neq j$.

To verify the certificate, you just need to check that for each edge $(v_i, v_j)$ that at least one of $v_i$ or $v_j$ is in $S$. Since S has k elements, you should be able to do this in $kn^2$ comparisons or $O(n^3)$ which is polynomial time.

user137481
  • 2,605