确定性线性有界自动机 (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)我们可以说存在一个 Post 对应解，如果对于某些 i1, i2, ………… ik，其中 1≤ ij ≤ n，条件 xi1 …….xik = yi1 …….yik 成立。示例 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…… 阅读更多