NL-复杂性的非数学描述

Question

NL-Complexity似乎与NP-复杂性有关，并且我想要一个非数学解释（因为我只是熟悉了那篇文章中使用的数学水平）。有人可以提供它与编程和NP复杂性相关的描述吗？

Answer 1

具有NL复杂性的算法可以运行在一个内存空间中，该内存空间的增长率只能以对数（非常缓慢）的问题大小增长。换句话说，这些问题会根据所需的内存使用情况很好地扩展 - 问题的两倍大小，并且您几乎不需要任何内存就可以完成算法。我不知道在NL和NP复杂集之间是否存在理论关系。 NP复杂性与完成程序所需的时间有关 - 而NL复杂性则表征完成程序所需的存储空间。

我在那篇wiki文章中注意到，如果NL = P，那么您提到它是未知的。这看起来不太可能，因为这意味着所有可以在多项式时间内完成的算法（w.r.t大小）也可以在按照对数进行w.r.t.缩放的存储空间中完成。问题大小。如果那只是真的！现在，我们只知道NL包含在P.

- 保罗

Answer 2

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

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

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

这些结果将保持完全理论，除了许多问题已被证明是NP完全的，并且没有一个确定性的（即在真实计算机上）解决方案被发现在时间多项式运行输入的长度。这使人们相信，如果一个问题可以被证明是NP完全的，那么所有的解决方案都可能呈指数级增长。这一切都没有被证明任何方式。在计算方面，这些问题的解决方案涉及递归搜索，而不是for循环的固定深度嵌套，这将是多项式。

NL-完整问题关心的是内存使用情况，而不是花在解决问题上的时间。再次，这些解决方案可以在假想的非确定性机器上“运行”。它们可以被认为是猜测正确答案的机器，然后检查使用一定数量的内存，这些内存随着输入长度的对数函数而增长。我们不在乎需要多少时间。一个等价的确定性解决方案只是遍历所有可能的猜测，所以会使用更多的内存来存储当前正在检查的猜测。

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

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

Answer 3

您可以表达如下差异：当一台NP机器双向访问 猜测的非确定位时，一台NL机器只允许读取一次。