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
