What is an instance (precisely) in computational complexity?

Question

I am trying to understand the notion of reduction of a problem to another problem. As it is known this has huge impact on classifying the complexity of a problem.

The definition of reduction involves the notion of instances. From wiki we read that a computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

I do not really understand though what this actually means. If I consider the reduction problem of multiplication $$ a \times b = \frac{(a + b)^2 - a^2 - b^2}{2} $$ what would an instance be in this case? I am particularly interested in understanding what is an instance for a problem that cn be reduced to a SAT-3 problem.

One definition I ve found is that the instance of a problem is an exact specification of the data: for example, “The graph contains nodes 1, 2, 3, 4, 5, and 6, and edges (1, 2) with cost 10, (1, 3) with cost 14, …” if we have a problem containing a graph $G$. I still find this not quite a good definition.

Disclaimer: not a computer scientist here, just a string theorist.

Answer 1

When considering a problem in a Computational Complexity context, an instance for the problem is just an input to the problem encoded in a manner that works with the underlying model of computation. For a Turing Machine, you would want your input to be encoded in the input alphabet $\Sigma$, which could be as simple as $\Sigma = \lbrace 0, 1\rbrace$ if your input has a binary encoding. Then, a (decision) problem is just a set of all instances that are decided by the problem (meaning they return an output of 1). If we use $\langle \cdot \rangle$ to denote an encoding for some input, then we might define a problem as the language

$$\text{POSITIVE-MULT} = \lbrace \langle a,b \rangle | a, b \in \mathbb{R} \text{ and } (a \times b) \geq 0 \rbrace$$

So the problem this language represents, then, is for some scalar inputs $(a,b)$, does their multiplication produce a non-negative number? Now we might have another language (problem) of the form

$$\text{POSITIVE-ADD} = \lbrace \langle a,b \rangle | a, b \in \mathbb{R} \text{ and } (a + b) \geq 0 \rbrace$$

So a question might be, can we use an algorithm that decides $\text{POSITIVE-ADD}$ to solve $\text{POSITIVE-MULT}$? Well sure, we just use the reduction you stated in your post. Namely, we will define a polynomial reduction of the form

$$f(a,b) = \left(\frac{(a+b)^2}{2}, -\frac{(a^2+b^2)}{2}\right)$$

Now it is pretty clear for this case that $x \in \text{POSITIVE-MULT}$ $\iff$ $f(x) \in \text{POSITIVE-ADD}$. This implies that we have a reduction from $\text{POSITIVE-MULT}$ to $\text{POSITIVE-ADD}$. You can do the same sort of things when considering $\text{3SAT}$ and other challenging problems but some of the reductions can take quite a bit of cleverness.

For a decent introductory reference to this material, check out Introduction to the Theory of Computation by Michael Sipser.

Answer 2

Pragmatically, an instance just means an input/output pair of an algorithm.

I think a better example of a reduction would be transforming multiplication into repeated addition. For example, the single multiplication "instance", $4*7$, can be transformed into $7+(7+(7+7))$, three "instances" of the addition algorithm. Reduction is all about finding ways to compose hard/unknown algorithms (like multiplication) from simpler/known algorithms (like addition), by transforming hard instances into simple ones. Often there's a cost/growth associated with such a reduction (in the big-$\mathcal O$ sense), like how we had to use four additions to accomplish a single multiplication.

For another example, consider sorting a list of numbers. This is a hard algorithm, but I spot a reduction! I happen to know the linear search algorithm to find the smallest number from a list (just iterate over it and keep track of the biggest-seen-so-far). Given a list of N numbers, I'll use linear search to find the smallest one, place it into a new output list, remove it from input, then repeat the process on the remaining numbers until the input is empty. This algorithm (selection sort) reduces the hard problem of sorting to a simpler problem of (multiple) linear search. Unfortunately, a single instance of sorting a list of length N requires N instances of linear search, so my overall complexity does increase to $\mathcal O(N^2)$.

Given that you mention 3-SAT, you have likely encountered the concept of reduction in the context of "NP-completeness". That starts to veer towards theoretical computer science, I'd suggest that any follow-up questions about 3-SAT be directed towards a different stackexchange site (https://cstheory.stackexchange.com/)