自然语言复杂度的非数学化描述

Question

NL-Complexity似乎与NP复杂性有关，我想要一个非数学的解释(因为我对那篇文章中使用的数学水平只是略知一二)。有人能描述一下它与编程和NP复杂性的关系吗？

Answer 1

具有NL复杂度的算法可以在仅随问题大小对数增长(非常慢)的内存空间中运行。换句话说，这些问题会很好地扩展到所需的内存使用量--问题大小增加了一倍，你几乎不需要更多的内存来运行算法直到完成。我不知道NL和NP复杂性集之间是否存在理论上的关系。NP复杂度与完成程序所需的时间有关，而NL复杂度则表征了完成程序所需的存储空间。

我确实注意到你在那篇维基文章中提到，它不知道是否为NL=P。这似乎不太可能，因为这意味着所有可以在多项式时间(w.r.t大小)内完成的算法也可以在逻辑扩展w.r.t的内存空间中完成。问题大小。如果这是真的就好了！现在我们只知道NL包含在P中。

-Paul

Answer 2

这三个概念之间只有边际关系。

简而言之，NP问题是那些可以用不确定的图灵机解决的问题，因为计算机是确定性的，(量子计算机是不同的类别，但不是非确定性的)，并且它的求解时间最多是输入长度的多项式函数。

问题可以被证明是NP完全的。这些都是NP中的，NP中的所有其他问题都可以转换为输入中的时间多项式中的一个。例子有3-可满足性和旅行商问题。

这些结果仍然完全是理论上的，除非许多问题已经被证明是NP-完全的，并且对于这些问题中的任何一个，都没有找到在输入长度的时间多项式中运行的确定性(即，在真实计算机上)解决方案。这使得人们相信，如果一个问题可以被证明是NP-完全的，那么所有的解决方案都可能是指数增长的。这两种方法都没有得到证实。在计算方面，这类问题的解决方案涉及递归搜索，而不是固定深度的for循环嵌套，后者将是多项式的。

NL-complete问题与内存使用有关，而不是解决问题所花费的时间。同样，这些解决方案是在假想的非确定性机器上“运行”的。它们可以被认为是猜测正确答案的机器，然后使用与输入长度成对数函数增长的内存量进行检查。我们并不关心这需要多少时间。一个等价的确定性解决方案将迭代所有可能的猜测，因此将使用更多的内存来存储当前正在检查的猜测。

NL-完全问题的一个例子是2-可满足性。给定子句的输入，猜测变量的真值，并在输入时检查它们。变量的数量随着输入的log2而增长，或者更确切地说，子句字符串的长度将随着变量数量的增加而增长。

我们知道NL问题在P中，也就是说，它们可以通过使用固定深度的嵌套for循环的解决方案来解决。但这并不意味着这些解决方案可以保持较低的内存使用率。内存不足的解决方案可能需要更长时间才能运行。在计算方面，这相当于用空间换取时间。

Answer 3

您可以将差异表示为:NP机器可以双向访问猜测的不确定比特，而NL机器只能读取它们一次。