务实地说，实例仅表示算法的输入/输出对。

我认为减少的一个更好的例子是将乘法转换为重复加法。例如，单乘法“实例”，$4*7$, 可以转化为$7+(7+(7+7))$，加法算法的三个“实例”。减少就是通过将硬实例转换为简单实例，从更简单/已知算法（如加法）中找到组合硬/未知算法（如乘法）的方法。通常有与这种减少相关的成本/增长（在大-$\mathcal O$感觉），就像我们必须使用四个加法来完成一次乘法一样。

再举一个例子，考虑对数字列表进行排序。这是一个困难的算法，但我发现了一个减少！我碰巧知道线性搜索算法可以从列表中找到最小的数字（只需遍历它并跟踪迄今为止最大的数字）。给定一个包含 N 个数字的列表，我将使用线性搜索找到最小的一个，将其放入新的输出列表中，将其从输入中删除，然后对剩余的数字重复该过程，直到输入为空。该算法（选择排序）将排序的难题简化为更简单的（多重）线性搜索问题。不幸的是，对长度为 N 的列表进行排序的单个实例需要 N 个线性搜索实例，因此我的整体复杂性确实增加到$\mathcal O(N^2)$.

鉴于您提到了 3-SAT，您可能已经在“NP 完全性”的背景下遇到了减少的概念。这开始转向理论计算机科学，我建议任何关于 3-SAT 的后续问题都指向不同的 stackexchange 站点（https://cstheory.stackexchange.com/）

在计算复杂性上下文中考虑问题时，问题的实例只是问题的输入，以与底层计算模型一起使用的方式编码。对于图灵机，您希望您的输入以输入字母表编码$\Sigma$, 这可能很简单$\Sigma = \lbrace 0, 1\rbrace$如果您的输入具有二进制编码。然后，（决策）问题只是由问题决定的所有实例的集合（意味着它们返回的输出为 1）。如果我们使用$\langle \cdot \rangle$来表示某些输入的编码，那么我们可以将问题定义为语言

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

因此，这种语言所代表的问题是针对一些标量输入$(a,b)$，它们的乘法是否产生非负数？现在我们可能有另一种语言（问题）的形式

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

所以一个问题可能是，我们可以使用一种算法来决定$\text{POSITIVE-ADD}$解决$\text{POSITIVE-MULT}$? 好吧，我们只是使用您在帖子中所说的减少。即，我们将定义形式的多项式归约

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

现在很清楚这个案例$x \in \text{POSITIVE-MULT}$ $\iff$ $f(x) \in \text{POSITIVE-ADD}$. 这意味着我们有一个减少$\text{POSITIVE-MULT}$到$\text{POSITIVE-ADD}$. 在考虑时你可以做同样的事情$\text{3SAT}$和其他具有挑战性的问题，但其中一些减少可能需要相当多的聪明才智。

有关此材料的不错的介绍性参考，请查看Michael Sipser的计算理论导论。