算法，语言和问题有什么区别？

Question

看来，在这个网站上，人们经常会纠正其他人混淆“算法”和“问题”。这些区别有什么区别？我怎么知道何时应该考虑算法并考虑问题？这些与形式语言理论中语言的概念有何关系？

Answer 1

为简单起见，我将首先考虑“决策”问题，这些问题具有是/否答案。功能问题的工作方式大致相同，除非是/否，否则有一个与每个输入单词关联的特定输出单词。

语: ：一种语言只是一组字符串。如果您有一个字母，例如$ sigma $，则$ sigma^*$是所有单词的集合，仅包含$ sigma $中的符号。例如，$ {0,1 }^*$是所有长度的所有二进制序列的集合。但是，字母不需要二进制。它可以是一致的，三元的等。

字母$ sigma $上的语言是$ sigma^*$的任何子集。

问题: ：一个问题是我们想回答的一些输入的问题。具体来说，决策问题是一个问题，问：“我们给定的输入是否满足属性$ x $？

语言是问题的正式实现。当我们想从理论上推论决策问题时，我们经常检查相应的语言。对于问题$ x $，相应的语言是：

$ l = {w mid w $是对问题$ x $的输入$ y $的编码，而对于问题$ x $的输入$ y $的答案是“是” $ } $

确定决策问题输入的答案是否是“是”等同于确定该字母对该输入的编码是否在相应的语言中。

算法: ：算法是解决问题的逐步方法。请注意，可以通过多种方式和多种语言表达算法，并且有许多不同的算法解决任何给定的问题。

图灵机: ：图灵机是算法的形式类似物。在给定字母上，对于每个单词，将在接受状态下停止或不会停止。因此，对于每台Turing Machine $ m $，都有一个相应的语言：

$ l（m）= {w mid m $ halts在输入$ w } $上处于接受状态。

（在所有输入上停止的图灵机之间存在一个细微的区别，并停止了是输入，这定义了复杂性类之间的区别$ m m m} $ rathsf {r} $和$ m athsf {re} $。）。

语言与图灵机之间的关系如下

1. 每台图灵机都完全接受一种语言

2. 可能有多台图灵机可以接受给定的语言

3. 可能没有接受给定语言的图灵机。

关于算法和问题，我们可以说大致相同：每种算法都解决了一个问题，但是可能有0或许多算法解决给定的问题。

时间复杂性: ：算法和问题之间最常见的混淆来源之一是关于复杂性类别。正确的分配可以总结如下：

• 算法 有 时间复杂
• 一个问题 属于 到一个复杂的课程

算法可以具有一定的时间复杂性。我们说，如果算法最多停止$ f（n）$ step，则算法具有最差的上限复杂性$ f（n）$。

问题没有跑步时间，因为问题与实际运行的特定算法没有绑定。相反，我们说问题属于复杂性类别，如果存在 一些 通过给定时间复杂性解决该问题的算法。

$ mathsf {p}， mathsf {np}， mathsf {pspace}， mathsf {exptime} $等都是复杂性类。这意味着它们包含问题，而不是算法。算法永远不可能以$ mathsf {p} $为单位，但是如果有一个多项式算法解决给定的问题$ x $，则$ x $ in $ mathsf {p} $。也可能会有一堆需要接受$ x $的指数时间算法，但是由于存在一个单个多项式算法接受$ x $，因此它在$ mthsf {p} $中。