What is an instance of NP complete problem?

Problem Detail: 

I don't understand this definition of an "instance" of a problem. Quoting from the CLRS book on page 1054 on abstract problems (Chapter 34.1):

We define an abstract problem $Q$ to be a binary relation on a set $I$ of problem instances and set $S$ of problem solutions.

Asked By : user1675999

Answered By : Vor

Other answers are good, I'll give only another trivial example:

• problem: "given two numbers $k,n$ with $1 < k < n$, does a number $m$ smaller or equal than $k$ exist such that $n$ is divisible by $m$ ?"

• the instances of the problem (or informally the input of the problem) are all the valid pairs $(k,n)$ such that $1 < k < n$; so $I = \{ (2,3),(2,4),...,(3,4),(3,5),...\}$

• the set of solutions is the set $S = \{ YES, NO \}$, indeed the problem is a decision problem (the answer to the question "does exist ...?" is simply YES or NO)
• the abstract problem $Q$ is a subset of $I \times S$ and is the relation that associates an instance of the problem to the correct answer

So:

Q = { ( (2,3), NO  ),       ( (2,4), YES ),        ( (2,5), NO  ),        ....       ( (6,13), NO ),           ( (6,14), YES ),        ...       ( (7,13), NO ),           ( (7,14), YES ),        ...     } 

P.S. the problem $Q$ is known as INTEGER FACTORIZATION and probably you'll meet it again ... :)

Best Answer from StackOverflow

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