问题标签 [computability]

我正在寻找一种简单的方法来估计固定大小的位序列的复杂性（可能最大长度为 10）。例如，我想 0000000 和 111111 根本不是很复杂，但 101010 和 101101 位于频谱的其他位置。

我知道 Kolmogorov 复杂性是无法计算的，但是是否可以简单地为具有二进制字母的固定（和小）长度序列进行编程？或者是否有另一种可能仅近似该度量但更容易计算的度量？

重要的是该措施相当简单，以便我可以向其他人（尽管受过良好教育）解释它。

谢谢。

我正在研究可计算性和复杂性，但我有一个疑问。将问题简化为另一个问题的功能是图灵可计算的。我想知道它是否甚至是一对一的函数（对应），因为例如查看 Vertex-Cover -> Independent Set reduction 我看不到一个问题的实例与另一个实例不对应的位置另一个。

谢谢

是否有可能创建一种算法来解决 Vim-golf 问题？对于那些不熟悉那是什么的人，您会得到两个不同的文本块，并且必须使用尽可能少的击键次数将第一个块转换为第二个块（在规范示例中使用 Vim，或者您选择的任何文本编辑程序）利用）。我最初的怀疑是答案是否定的。我们知道所需文本更改数量的上限 - 手动删除差异并输入正确的文本。然而，降到最低数量更复杂 - 文本编辑器可以编写强大的宏来执行任务，并且您可以组合多个宏 - 我猜可能有一些方法可以显示与停止问题的对应关系，但我我不太确定细节。

是否有一个程序 (may-halt?p) 可以判断是否存在输入以使 (p input) 停止？

我尝试了简单的对角化，但它只告诉我 (may-halt?di​​ag-may-halt) 必须为真。它无助于证明程序是否存在。

有这样的程序吗？

从 ATM 到 ATM-complement 有减少吗？

我一直在想太多，找不到答案。

我知道从 ATM-complement 减少到 ATM 是不可能的，因为如果是这样，ATM 就不会在 RE 中。但是我怎样才能反其道而行之呢？

非常感谢 ：）

请注意以下粒子物理动画：

它虽然简单，但涉及远距离作用：即，在每个滴答声中，原子与其他任意远的原子相互作用。这对于只有本地规则的元胞自动机是不可能的。因此，我想知道：最简单的自动机编码是什么，可以显示类似的粒子物理行为？

我正在学习的可计算性课程解释了 RE - REC 中的几种语言（递归可枚举但非递归，即可通过非停止图灵机求解）。它首先显示其中一个（L_d，不接受自己编码的图灵机语言）不在 RE 中，并证明其补码在 RE-REC 中。然后证明它可以简化为通用语言（L_u，图灵机的所有二进制编码与它接受的字符串连接的集合）。然后它继续展示 L_u 如何是 RE-Hard，然后将其简化为 L_PCP（Post 的对应问题），然后将其简化为上下文无关语法歧义。RE 中是否存在任何问题，但 RE-Hard 中没有问题？因为到目前为止，对于我们的教授在 RE - REC 中解释的每一个问题，他都证明了它们可以相互还原。

如果我告诉你一盘棋的走法并宣布谁赢了，如果赢家真的赢了，为什么不能在多项式时间内检查呢？根据我的理解，这将使它成为一个 NP 问题。

定义 SAT2016 = {\phi | \phi 是一个 CNF 公式，最多有 2016 个子句}。假设 P \neq NP，SAT2016 NP-complete 吗？

由于每个子句中的文字数量没有限制，因此尚不清楚是否存在多项式时间算法来检查具有恒定子句数量限制的公式的可满足性。

欢迎您的想法。

我有一个子集和问题的变体，其中子集的大小是k并且所有整数都是正数（不是零）。

从网上可以看出，这个问题可以用伪多项式时间内的动态规划来很好地解决。

我需要决定这个问题是NPC，还是在P（假设时P!=NP）。

我试图从子集和问题中减少，但遇到了所有整数必须大于零的约束问题。因为否则我只会用k零整数填充输入。

问题的正式定义：

L={<S1,S2,...,Sn,T,k>|There exists a subset I of S1,...,Sn of size m which sums up to T}