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機器只允許讀取一次。