串流模型下的2-SAT演算法及其應用

Abstract

串流模型下的演算法在近數十年內被廣泛地研究，主要的研究動機來自於巨量資料的產生使得傳統的計算模型不再適用。由於單一機器的儲存空間有限，無法將所有需要的資料都存取在同一台機器中再進行處理，因此需要在有限的可用空間中處理。在這篇論文中我們提出了第一個在僅考慮插入串流的模型中，可以在 $O(k)$ 次串流以及 $O(\frac{n^2\log{n}}{k})$ 空間中解出2-SAT問題的演算法。我們採取了將2-SAT轉換成有向圖再進行強連通元件分解的作法，因此對應的也提出了第一個在僅考慮插入串流的模型中，可以在 $O(k)$ 次串流以及 $O(\frac{n^2\log{n}}{k})$ 空間中計算出強連通元件分解的演算法。儘管關於2-SAT和強連通元件分解在串流模型下的複雜度仍未完整解出，因此我們不能完全保證這篇論文提出的演算法是最佳的，但我們提出了數個證據，包括不可能性結果、既有演算法不能有效的轉換到串流模型、簡化到其他問題，說明2-SAT和強連通元件分解在串流模型中不太可能有簡單的演算法。此外，我們提出的演算法具有容易描述和可以調整參數的性質，使得在不同應用情境下可以藉由改變參數以符合需求。強連通元件分解是處理許多有向圖上的問題的基礎，我們的強連通元件演算法可以作為在串流模型中研究有向圖問題的一個重要工具。

Algorithms in the streaming model have been extensively studied in recent decades, driven by the escalating demand to handle massive amounts of data efficiently. In this thesis, we introduce the first algorithm for 2-SAT in the insert-only model using $O(k)$ pass and $O(\frac{n^2\log{n}}{k})$ space. To serve our purpose, we also introduce the first algorithm for SCC-decomposition in the insert-only streaming model using $O(k)$ pass and $O(\frac{n^2\log{n}}{k})$ space, employing a novel approach that can be adapted and reutilized in other models. While a complete proof of the optimality of our algorithm is yet to be established, we offer convincing evidence such as impossibility results, the inefficiency of implementing existing approaches from other models, and reductions to other problems. Our algorithm exhibits desirable properties such as simplicity and flexibility, precisely, a smooth tradeoff between pass and space usage that might be useful in future applications. SCC-decomposition is the basis for studying many problems related to directed graphs, our algorithm for SCC-decomposition can be utilized as a crucial building block for tackling these problems, laying the foundation for exploring and addressing a wide range of problems in this evolving research direction.