What is an instance of NP complete problem?

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.

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

-
problem: "given two numbers $k,n$ with $1

-
the instances of the problem (or informally the input of the problem) are all the valid pairs $(k,n)$ such that $1

• 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 ... :)

StackExchange Computer Science Q#7005, answer score: 9