问题标签 [computation-theory]

我研究了很多关于减少的问题，但我有一个很糟糕的问题：我从 CLRS 得到这个：

“ ...通过将解决问题 A 的问题“简化”为解决问题 B，我们用 B 的“容易性”来证明 A 的“容易性”。”

我从“Christos H. Papadimitriou 的计算复杂性”中得到这个：

“……如果 B 简化为 A，问题 A 至少和问题 B 一样难。”

我对这两个概念感到困惑：当我们使用 easyiness 时，我们说问题 X 减少为问题 Y，如果我们有 Y 的多项式时间算法并且减少过程是在多项式时间内完成的，那么问题 X 可以在多项式时间内解决，而 X 是比 Y 容易，或者至少不比 Y 难。

但是当我们使用 hard 时，我们说问题 X 简化为问题 Y，并且 Y 比 X 更容易，或者至少不比 X 更难。

我真的很困惑，请帮助我。特别感谢。

我需要对非确定性算法的简单描述。我们可以将非确定性算法与具有并行处理器的计算机进行比较吗？请有人准确地向我解释一下非确定性算法

我现在正在学习计算理论课程。我可以很好地理解这些概念。我能够解决问题。而且，当我向我的导师询问现实世界的应用程序时，他告诉我这些概念在编译器设计中肯定是有用且必不可少的。但是，至少要进行有意义的研究，我需要一些关于如何在我的编码中使用这些概念的解释。

例如，如果我想设计自己的 grep。我将在 C 中使用字符串函数。我不知道如何在编码中使用正则表达式。

同样的情况也适用于图灵机。

如果我想添加两个数字，为​​什么我必须使用那些一元概念。硬件是否实现了这些概念？

我正在寻找可以让我对正则表达式列表或一些文档和研究进行排序的东西，

根据他们的特殊性/严格性

但是怎么样

哪一个比另一个不那么具体？

先感谢您

我正在学习上下文无关语法，我很好奇 f 和 g 部分中带星号的箭头和不带星号的箭头是什么意思：

• f 是假的。
• g 是真的。

你能帮我找到一种语言的补充，它以abab - (a|b)*abab (over an alphabet {a,b})

我想，补码必须包含所有不以 abab 结尾的字符串。在构建一个 DFA 以(a|b)*abab补充

好的，单词不允许以 . 结尾abab。末尾有's 和's的四个字母有 2 ^{4种方式。}好的，必须删除所以有 15 种组合。这是否意味着，补语是.（所有's 和's 的组合的联合，没有 's ）？但还是一开始就保持不变吗？ababab(a|b)*ababab(a|b)

请帮助我理解这一点。

在理论计算机科学中众所周知，“Hello world tester”程序是一个无法确定的问题。（这是我所说的hello world tester
的链接 我的问题是因为给定一个程序作为输入，我们不能说该程序会做什么做，我们能解决相反的问题吗：
给定一组输入和输出，是否有一种算法可以编写程序来实现给定输入和输出之间的一对一映射。
我知道元编程，但我的问题是更多的理论兴趣。可以适用于一般案例的东西。

我想我接近这个答案，但仍然要确认我们是否可以创建一个可以进行实数计算并给出准确结果的图灵机（至少在原则上）？**例如找到整数的平方根。（其输出将是一个实数）我认为我们不能开发这种机器的逻辑是，实数是不可数无限的，对于不可数无限的语言，我们无法创建图灵机。

DFA 中接受具有“1”作为右起第 5 个符号的字符串所需的最少状态数是多少？字符串在字母表 {0,1} 上定义。

根据标题，是否可以在 HTML中创建（非平凡的）quine ？

我对 HTML quine 的定义：

一个非平凡的 HTML quine 是一个不为 null 并使用至少一个 HTML 标记的 HTML quine，假设 HTML 文件中的某些字符串由浏览器呈现为纯文本。HTML quine 被定义q.html 为使得标准浏览器呈现的输出是其自身的内容q.html。

（我愿意对此定义发表任何评论，我现在有点破解它）

HTML 不是图灵完备的，因此不能应用不动点定理来证明它确实是可能的。

但是，这并不一定意味着 HTML quine 是不可能的。或者实际上是否可以证明 HTML quine 是不可能的？