E.g. the algorithmic problem of sorting:
input: sequence of some objects;
output: reordering of sequences such that some relation works for each next element of a sequence.

Right? So what's the instance of a problem?

So instance could be:
input type: integers; relation in the output: $\geq$.

or instance is some specific input:
like $\{1, 2, 3\}$; plus some relation, e.g. $\geq$.

It looks like there is a problem, then like instance, and then kind of sub-instance.

Also, for example, sorting such that relation is $\ge$ vs $\le$ is it two different algorithmic problems? Or two different instances of the same algorithmic problem?

Also if input data is numbers vs input data is strings, is it two different algorithmic problems or two instance of the same algorithmic problem?


1 Answer 1


Yes, there is a clear distinction. A problem is a general computational task; an instance is an input to that task.

The confusion in your examples is because you need to make a decision about what the task is and, correspondingly, what the input is. For any fixed domain $D$ and fixed comparison relation $\sqsubseteq$ on that domain, sorting elements of $D$ according to $\sqsubseteq$ is a problem. The instances of this problem are sequences of elements of $D$. For example, the problem of sorting natural numbers according to $\leq$ is a problem, whose instances are sequences of natural numbers. The problem of sorting natural numbers according to $\geq$ is a different problem, though its instances are also sequences of natural numbers.

Alternatively, one could make the comparison operator a part of the input. Now, the problem is to sort elements of some fixed domain $D$ using the given comparison operator, and an instance consists of a sequence of elements of $D$ and a comparison operator. However, it's not clear how you'd specify the comparison operator, which is a binary relation on $D$, which could be an infinite amount of data. One option might be to have a list of allowed choices so, e.g., choice 1 means sort according to $\leq$, choice 2 means sort according to $\geq$, etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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