6
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for the detailed response. Although, Q is an abstract problem and is a subset, I was actually thinking "I" and "S" is a set inside Q. $\endgroup$ – user1675999 Nov 30 '12 at 2:13
6
$\begingroup$

An abstract decision problem, such as clique, is an assignment of a truth value (b>true or false) for each instance of the problem. In the case of clique, each instance is a pair $(G,k)$, where $G$ is a graph and $k$ is a natural number, and the problem assigns true to a pair $(G,k)$ if $G$ contains a clique of size $k$; otherwise it assigns false to the pair.

An algorithm for an abstract decision problem is an algorithm which takes an instance and returns its correct truth value. So an algorithm $A$ for clique takes as input a graph $G$ and an integer $k$, and returns whether $G$ contains a clique of size $k$. An algorithm should work for all instances at once, and we are interested in the resources it consumes (time and memory) in terms of the length of the input.

For example, let us consider the following algorithm for clique: given $(G,k)$, go over all sets of vertices of $G$ of size $k$, and for each one, check whether it constitutes a clique. One can check that the running time of this algorithm isn't polynomial in the length of the input.

We are interested in algorithms that work for all instances. For any given instance $(G,k)$, we can construct an algorithm that works correctly on it (one of the following algorithms will do: the algorithm that always outputs true, and the one that always outputs false). So it's not meaningful to look at single instances. If we have a particular algorithm in mind, then this algorithm might work better on some instances, and in that sense we can say that an instance is easy for a particular algorithm.

NP-completeness theory deals with worst-case time complexity - we're interested only in algorithms that work for all instances. The area of average-case complexity deals with algorithms that only have to work on almost all instances (in some precise sense), the idea being that such an algorithm is very likely to work on every instance encountered in practice.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

A problem instance is the actual case you're trying to solve.

For example, the problem "can this set of numbers be divided into two sets which have the same sum" is an NP-hard problem. An instance of this problem would be an actual set of numbers, for example 87, 58, 62, 104, 29, 78.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ so does that mean not all instances of a problem X say suppose are solvable if one instance of X can be reducible to a NP problem Y with polynomial time function? Assume Y can solved in polynomial time. $\endgroup$ – user1675999 Nov 29 '12 at 2:34
  • 1
    $\begingroup$ What do you mean when you say X is "solvable"? If Y is an NP problem, why do we assume it can be solved in polynomial time? Could we just say it's a P problem? $\endgroup$ – SamM Nov 29 '12 at 2:59
  • 1
    $\begingroup$ I mean to say X can be polynomially reduced to known NP problem Y. And that Y can be solved in polynomial time. So I am asking when we say instances, so say suppose for only certain instance of a problem X can be solved that does not imply all instances of X can be solved or reduced in polynomial time to Y $\endgroup$ – user1675999 Nov 29 '12 at 3:37
  • 1
    $\begingroup$ Since Y is polynomial, and X can be polynomial reduced to it, X is also polynomial. $\endgroup$ – SamM Nov 29 '12 at 3:41
3
$\begingroup$

In short: an instance of a problem is the input for an algorithm solving the problem. Correspondingly, solutions are the outputs of such an algorithm.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.