问题标签 [computation-theory]

是否有任何论文描述了从编译程序中推断子程序的任何算法/技术？换句话说：是否有一种算法可以找到在程序中出现多次的代码块？这些块可以重新排序指令（当然没有程序行为改变），以便更有可能找到匹配项。

这个过程可以看作与编译器为避免调用而完成的子例程内联相反，但会增加二进制大小。

在我看来，这是一个非常困难的理论问题。

所以，到了期末考试的时间，我在一次旧考试中遇到了这个问题：

给出一个表示diff(x)where 的正则表达式：

例如

我一直在努力解决这个问题，但无法提出任何建议。任何指针将不胜感激。

问题是：给定所有只接收偶数长度单词的 DFA 的语言，证明它是否在 P 中。

我考虑过制造一台图灵机，它可以像 BFS/Dijkstra 的算法那样遍历给定的 DFA，以便找到从起始状态到接受状态的所有路径，但不知道如何处理循环？

谢谢！

我猜 X^n 效率更高。谁能解释一下？

谢谢。

我们知道C++ 模板元编程是图灵完备的，但预处理器元编程不是。

C++11 为我们提供了一种新的元编程形式：constexpr 函数的计算。这种计算形式是图灵完备的吗？我在想，由于在 constexpr 函数中允许递归和条件运算符 (?:) ，它会是这样，但我希望有更多专业知识的人来确认。

减少很多个，是不对称的。我试图证明这一点，但效果并不好。

给定两种语言 A 和 B ，其中 A 定义为

和B=A_TM，其中 A_TM 不可判定但图灵可识别！

鉴于以下减少：

（请原谅我没有使用 Latex ，我没有使用它的经验）

正如我所看到的，从 A <= B（从 A 到 A_TM）的减少是可能的，并且效果很好。但是，我不明白为什么 B <= A 是不可能的。

你能澄清和解释一下吗？

谢谢罗恩

我研究过复杂性理论，并且拥有扎实的编程背景，而且在人类固有的时间里运行这么多东西似乎总是很奇怪。我想知道是否有人对这是为什么有任何想法？

我一般说的时间在 1 秒到 1 小时的范围内。如果您考虑到时间跨度与计算机每秒可以处理的数十亿次操作成正比，那么如此大量的事情属于该类别似乎很奇怪。

几个例子：

编码视频：20分钟

检查更新：5 秒

启动计算机：45 秒

你明白了……

您不认为大多数事情应该属于以下两类之一：瞬时/数百万年吗？

所以有anxn游戏板，板上的每个位置都有一个整数。玩家一从第 1 行中选择一个数字，玩家 2 从第 2 行中选择一个数字，他们交替进行直到没有更多行。然后他们将所有数字相加，如果总和等于预定的总和 S，则玩家 1 获胜，否则玩家 2 获胜。对于特定棋盘和总和（B，S），玩家 1 的获胜策略是无论玩家 2 做什么，玩家 1 都能获胜。我想证明这个问题是 PSpace-complete

所以首先我必须证明它在 PSpace 中，我认为这很容易，因为移动的总数受棋盘大小的限制，即 n^2。

我一直坚持证明它很难 PSpace，但我知道我必须从 QSAT 中减少，但我不知道如何。有人可以帮忙吗？

编辑：其实我不知道我必须从 QSAT 中减少，但是在搜索之后似乎 QSAT 是最有可能的候选人。许多其他两人游戏，地理是最突出的例子，从 QSAT 减少，所以我认为这也是必须的。但是，如果我对此有误，请随时纠正我。

我如何证明这种语言是否正常？

L = {a ⁿ b ⁿ : n≥1} 并集 {a ⁿ b ⁿ⁺² : n≥1}

我如何为这个问题绘制 NFA（自动机）？

首先它应该接受：

• 字母 = x,y,z

• L= { w | w 使得出现次数 x,y,z 之一是三的倍数。}

例如：{xxx, yyy, zzz, xyxyzzz, xyxyx, zyzyz...}