确定性线性有界自动机 (LBA) 是一个 9 元组自动机 G = (Q, Σ, E, δ, ε, q0, GL, GR, F)，其中：Q 是所有状态的集合；Σ 是所有终结符的集合；E 是输入字母表；δ 是转移函数的集合；q0 是初始状态；GL 是磁带的左边界；GR 是磁带的右边界；F 是最终状态的集合。线性有界自动机被称为多轨迹非确定性图灵机，它具有某个有界有限长度的磁带。长度 = 函数（初始输入字符串的长度，常数 c）。线性有界自动机中的计算限于常数有界区域。这里的输入字母表包含两个特殊符号……阅读更多

Post 对应问题 (PCP) 由 Emil Post 于 1946 年提出，是一个不可判定问题。在字母表 Σ 上的 PCP 问题是状态。给定以下两个列表 M 和 N，它们是非空字符串在 Σ 上的列表：−M = (x1, x2, x3, ………, xn) N = (y1, y2, y3, ………, yn) 我们可以说，如果对于某些 i1, i2, ………… ik，其中 1≤ ij ≤ n，条件 xi1 …….xik = yi1 …….yik 满足，则存在 Post 对应解。示例 1 查找列表 M = (abb, aa, aaa) 和 N = (bba, aaa, aa) 是否具有 Post 对应……阅读更多

它是图 G 的顶点子集（最小大小），使得 G 中的每条边至少与 G 中的一个顶点关联。顶点覆盖 (VC) 问题为了证明 VC 是 NP 完全的，我们必须证明以下几点：−VC 是非确定性多项式 (NP) 的。一个 NPC 问题可以简化为 VC。为了证明 VC 是 NP，找到一个验证器，它是一个顶点的子集，它是 VC，并且可以在多项式时间内进行验证。对于一个有 n 个顶点的图，它可以在 O(n2) 时间内得到证明。因此，VC 是 NP。现在考虑“团”问题，它是 NPC，并将其简化为……阅读更多

哈密顿环是在图 G 的 n 条边上沿圆形路径行进，访问每个顶点一次并返回其起始顶点。示例 下面是哈密顿环路径的一个示例：−哈密顿环路径：1, 2, 8, 7, 6, 5, 4, 3, 1 TSP 是 NP 完全的旅行商问题 (TSP) 有一个推销员和一组城市。推销员需要访问每个城市，从某个城市开始，然后返回同一个城市，即返回起始位置。这个问题的挑战在于，旅行推销员想要最小化……阅读更多

非确定性多项式 (NP) 问题有点难以理解。就解决 NP 问题而言，运行时间不是多项式的。它可能是 O(n!) 或更大的值。但是，对于这类问题，给定一个特定的解决方案，检查解决方案的运行时间是多项式的。例如，数独游戏。NP 难问题当一个用于解决 NP 难的问题的算法可以转化为解决任何 NP 问题时，则称该问题为 NP 难问题。然后我们可以说，这个问题至少与任何 NP 问题一样难，但它可能要困难得多或更复杂。NP 完全……阅读更多

非确定性多项式 (NP) 问题有点难以理解。就解决 NP 问题而言，运行时间不可能是多项式的。它可能是 O(n!) 或更大的值。但是，对于这类问题，给定一个特定的解决方案，检查解决方案的运行时间是多项式的。例如，数独游戏。NP 难问题当一个用于解决 NP 难的问题的算法可以转化为解决任何 NP 问题时，则称该问题为 NP 难问题。然后我们可以说，这个问题至少与任何 NP 问题一样难，但它可能要困难得多或更……阅读更多

计算理论 (TOC) 中有两种类型的语言，如下所示：−可判定的不可判定的如果存在该问题的解决方案并且可以构造相应的算法，则该问题称为可判定的。可判定问题的示例查找 1 到 50 范围内所有奇数。对于这个问题，我们可以通过构造一个算法很容易地找到解决方案。就图灵机 (TM) 而言，如果一个问题是可判定的，那么图灵机无论是否接受其输入都会停止。就有限自动机 (FA) 而言，“可判定”是指测试某个……阅读更多

在我们了解计算理论 (TOC) 中的可判定问题和不可判定问题之前，我们必须了解可判定语言和不可判定语言。因此，让我们首先看看可判定语言是什么意思。可判定语言如果存在一个判定器 M 使得 L(M) = L，则语言 L 称为可判定的。给定一个判定器 M，您可以了解字符串 w 是否属于 L(M)。在 w 上运行 M。尽管这可能需要很长时间，但 M 将接受或拒绝 w。集合 R 是所有可判定语言的集合。如果 L 是可判定的，则 L ∈ R。不可判定语言如果……阅读更多

通常，程序由长度有限或无限的循环组成。程序完成的工作量完全取决于给程序的输入。程序可能包含许多不同数量的循环，这些循环可以是线性的或嵌套的。停机问题是根据给定的任意计算机程序及其输入来决定或推断该程序是否会停止执行或对于给定的输入运行无限循环的问题。停机问题说明编写一个在有限时间内执行的计算机程序并不容易，该程序能够……阅读更多

图灵机是一个七元组 (Q, Σ, Γ, δ, q0, qacc, qrej)，其中：Q 是有限状态集；Σ 是输入字母表，不包含空白符号 t；Γ 是磁带字母表，其中 t ∈ Γ 且 Σ ⊆ Γ；δ: (Q × Γ) → (Q × Γ × {L, R}) 是转移函数；q0 ∈ Q 是起始状态；qacc ∈ Q 是接受状态；qrej ∈ Q 是拒绝状态，其中 qrej ≠ qacc。问题构造用于两个一元整数相乘的图灵机 (TM)。解决方案两个一元整数 3*2=6 在图灵机中，3 表示 − 111……阅读更多