Qua các bài viết trong blog, chúng ta đã thấy rất nhiều các bài toán được giải quyết một cách hiệu quả. Ví dụ như bài toán sắp xếp, bài toán tìm kiếm xâu, bài toán tìm đường đi ngắn nhất, tìm cây khung nhỏ nhất, bài toán luồng cực đại, bài toán lát cắt cực tiểu, v.v và v.v. Tất cả các bài toán này đều được giải trong thời gian $O(n^c)$ với một hằng số $c$ nào đó và $n$ là chiều dài của đầu vào bài toán. Ngược lại, hầu hết các bài toán chúng ta gặp trong thực tế là những bài toán mà hiện tại chúng ta không biết làm sao để giải chúng một cách hiệu quả. Mình nhấn mạnh hai từ "hiện tại" và "không biết" ý nói có thể những bài toán đó có lời giải hiệu quả, chỉ là chúng ta chưa tìm ra được lời giải. Tuy nhiên, rất nhiều các nhà nghiên cứu tin rằng những bài toán đó chúng ta không thể giải được hiệu quả và vấn đề chỉ là chúng ta chưa tìm ra cách để chứng minh rằng ta không thể giải chúng hiệu quả. Post này và các post tiếp theo sẽ cung cấp một công cụ để xác định những bài toán khó đó.

Độ phức tạp của một bài toán tính toán

Chúng ta thường mô tả độ phức tạp của một bài toán dựa vào các tài nguyên (resource) cần thiết để giải bài toán đó. Hai loại tài nguyên cơ bản là thời gian (time) và bộ nhớ (space). Trong các bài viết ở đây, chúng ta quan tâm nhiều đến thời gian hơn là bộ nhớ. Trong phân tích của các bài viết trước trên blog, chúng ta thường phát biểu thuật toán có độ phức tạp (thời gian) $O(n)$, $O(n^2)$, $\ldots$, $O(2^n)$, hay một cách tổng quát hơn là $O(f(n))$ với $f(n)$ là một hàm (tăng) của $n$. Vậy ở đây $n$ và $f(n)$ có ý nghĩa thế nào? Ta sẽ lần lượt làm rõ ý nghĩa của hai đại lượng này.

• Biến $n$ ở đây chính là chiều dài của đầu vào (input) của bài toán (problem). Việc sử dụng $n$ để phân tích độ phức tạp của bài toán dựa trên ý tưởng: bài toán càng lớn (dài) thì càng khó giải quyết. Chiều dài của đầu vào được định nghĩa là số bít dùng để biểu diễn đầu vào, và số bít này thì lại phụ thuộc vào cách mã hóa (encode) đầu vào. Ví dụ, trong hệ unary, số $n$ cần $n$ bít để biểu diễn còn trong hệ nhị phân (binary), số $n$ chỉ cần $\lfloor\log(n)\rfloor + 1$ bít để biểu diễn. Ở đây, ta sẽ sử dụng hệ nhị phân để biểu diễn đầu vào. Nói một cách đầy đủ, biến $n$ ở đây là chiều dài của input trong hệ biểu diễn nhị phân.
• Hàm $f(n)$ ở đây biểu diễn số thao tác cơ bản mà một thuật toán sử dụng để giải quyết bài toán có input chiều dài $n$. Tập thao tác cơ bản lại phụ thuộc vào mô hình tính toán (models of computation) mà ta sử dụng. Có rất nhiều loại mô hình tính toán khác nhau đã được đề xuất mà ta không thể nghiên cứu hết được. Ở đây, ta mặc định sử dụng mô hình máy Turing tất định (deterministic Turing machine) mà một ví dụ cụ thể là máy tính cá nhân của chúng ta (Desktop hay Laptop). Do máy tính của chúng ta sử dụng các bít để biểu diễn thông tin và các thao tác logic AND, OR và NOT để xử lí các bít, tập các thao tác cơ bản mà chúng ta sử dụng ở đây là tập các thao tác bít AND, OR và NOT.

Trong phân tích thuật toán, chúng ta thường sử dụng tiệm cận hơn là đếm chính xác số lượng các thao tác cơ bản. Một phần vì đếm chính xác số lượng thao tác thường là một việc không tầm thường. Một phần khác là vì sử dụng phương pháp tiệm cận sẽ cho chúng ta một cách ước lượng tương đối về thuật toán một cách nhanh chóng để chúng ta tập trung vào thiết kế ở mức cao (high level). Phân tích tiệm cận cho phép chúng ta có thể mở rộng tập thao tác cơ bản để bao gồm các phép toán phức tạp hơn như cộng, trừ, nhân và chia (CTNC), trong đó, các hạng (nhân) tử tham gia vào các phép CTNC đều có chiều dài hằng số. Chú ý, nếu các hạng (nhân) tử tham gia vào các phép CTNC không còn là hằng số nữa thì ta không thể coi đó là các thao tác cơ bản. Bạn đoc có thể xem ví dụ cụ thể khi các phép CTNC không còn được coi là hằng số trong phân tích tìm số Fibonacci.

Bài toán P và NP

Một bài toán bao giờ cũng có ít nhất hai phần là đầu vào (input) và đầu ra (output). Độ dài của input được coi như là biến để đo độ phức tạp của thuật toán giải bài toán. Có những bài toán mà ta phải phân tích độ phức tạp dựa trên cả hai biến input và output, ví dụ như bài toán nén dữ liệu (data compression). Ở đây, ta chỉ xét những bài toán mà đầu ra chỉ là 1 bít ( Yes hoặc No). Các bài toán như vậy được gọi là các bài toán quyết định (decision problem).

Các bài toán quyết định thoạt đầu nghe có vẻ không có tính tổng quát cao vì đầu ra chỉ có 1 bít. Tuy nhiên, ta có thể quy rất nhiều bài toán không quyết định về bài toán quyết định, mà thời gian để chuyển qua lại giữa hai bài toán vẫn là đa thức. Ví dụ bài toán tìm kích thước của tập độc lập (independent set) lớn nhất trong đồ thị.

 
Ta có thể quy bài toán IndependentSetOpt về bài toán quyết định như sau:

 
Dễ thấy, bài toán IndependentSet là bài toán quyết định (có tồn tại hay không). Nếu ta có thể giải được bài toán IndependentSet, ta có thể giải được bài toán IndependentSetOpt bằng cách tìm kiếm nhị phân giá trị $K$ trong đoạn $[1,V]$.

Figure 1: (a) Tập màu đỏ là một tập độc lập trong đồ thị. (b) Tập màu xanh không phải là một tập độc lập trong đồ thị.

Một thuật toán được gọi là giải bài toán quyết định nếu như với mỗi input của bài toán, thuật toán xác định được chính xác đầu ra là Yes hay No. Trong số các bài toán quyết định, lớp bài toán mà chúng ta quan tâm nhất là lớp các bài toán mà ta có thể giải được hiệu quả bằng máy tính. Lớp bài toán đó được gọi là lớp P (viết tắt của polynomial time-thời gian đa thức).

 
Trong định nghĩa trên, giá trị của bậc $c$ trong biểu thức $O(n^c)$ không quan trọng, miễn là nó không phụ thuộc vào $n$. Do đó, ta sẽ dùng kí hiệu $poly(n)$ để thay cho $O(n^c)$.

Tuy nhiên, nhiều bài toán hiện tại chúng ta chưa biết có thể giải được hiệu quả hay không (thuộc P hay không). Trong số các bài toán đó, có một lớp các bài toán thú vị mà người ta gọi nó là lớp NP. Ý tưởng đằng sau lớp bài toán này là: nếu ai đó cho chúng ta lời giải của một bài toán khó, việc kiểm tra xem đó có phải là lời giải đúng hay không sẽ dễ hơn việc trực tiếp giải bài toán đó. Dễ hơn ở đây hiểu theo nghĩa có thể kiểm tra được lời giải trong thời gian $poly(n)$. Ví dụ với bài toán IndependentSet. Nếu ai đó đưa ta một tập đỉnh $X$ của đồ thị và nói rằng tập đỉnh đó là tập độc lập của đồ thị có kích thước ít nhất $K$, ta có thể kiểm tra (trong thời gian $poly(n)$) xem $X$ có phải là tập độc lập hay không trong thời gian $O(n^2)$ (tại sao?) và kiểm tra xem $|X| \geq K$ hay không. Nếu cả hai điều kiện được thỏa mãn thì đầu vào của bài toán có lời giải Yes, và ngược lại.

Tập $X$ đó gọi là một bằng chứng (certificate) cho thấy input của bài toán có output Yes. Hai tính chất quan trọng của tập $X$ mà ta có thể rút ra từ ví dụ trên:

1. Ngắn gọn: Ta có thể mô tả $X$ sử dụng tối đa $poly(n)$ bít vì $|X| \leq n$
2. Dễ kiểm tra: Ta có thể kiểm tra xem $X$ có thỏa mãn điều kiện là một tập độc lập có kích thước $K$ hay không trong thời gian $poly(n)$.

Ta gọi $X$ là một bằng chứng ngắn gọn dễ kiểm tra của bài toán IndependentSet.

Theo định nghĩa trên, để chứng minh một bài toán thuộc NP ta phải: (i) chỉ ra một bằng chứng ngắn gọn cho đầu vào Yes và (ii) chỉ ra một thuật toán để kiểm tra bằng chứng đó trong thời gian $poly(n)$. Ta sẽ minh họa thêm một số bài toán NP trong phần sau.

Remarks: Từ NP ở đây là viết tắt của Nondeterministic Polynomial time, một thuật ngữ liên quan đến máy Turing không tất định. Nhiều người nhầm lẫn NP là viết tắt của Non-Polynomial time.

Về mặt trực quan, một bài toán dễ giải thì cũng dễ kiểm tra lời giải. Do đó, P $\subseteq $ NP. Hay nói cách khác, bất kì một bài toán P nào cũng thuộc NP. Việc chứng minh P $\subseteq $ NP theo định nghĩa bằng chứng ngắn gọn dễ kiểm tra ta sẽ coi như bài tập cho bạn đọc (hints: bằng chứng ngắn gọn dễ kiểm tra của một bài toán P là $\emptyset$).

Một câu hỏi làm đau đầu các nhà nghiên cứu lý thuyết đó là liệu P $\subsetneq $ NP hay không? Hay nói cách khác, liệu có tồn tại một bài toán nào trong lớp NP mà không thể giải được hiệu quả? Bài toán này được gọi là bài toán P vs NP, một trong 7 bài toán mà người đưa ra lời giải sẽ được thưởng 1 triệu đô la từ viện Clay.

Hầu hết các nhà khoa học máy tính tin rằng P $\not=$ NP. Tuy nhiên, có những nhà khoa học máy tính nối tiếng, ví dụ như Donald Knuth [3], tin rằng P $=$ NP. Trên trang web cá nhân của mình, Gerhard J Woeginger có liệt kê một danh sách các "chứng minh", và gần như một nửa đưa ra "chứng minh" P $=$ NP còn nửa kia đưa ra "chứng minh" P $\not=$ NP. Điều đó cho thấy bài toán này, có lẽ, còn rất lâu nữa mới có thể được giải quyết một cách đầy đủ. Tạm thời, chúng ta có biểu đồ Venn thể hiện quan hệ giữa P và NP như sau:

Figure 2: P vs NP

Một số bài toán NP

Bài toán quan trọng nhất trong lớp NP đó là bài toán Sat. Lí do tại sao Sat là bài toán quan trọng nhất thì ta sẽ xem ở bài viết tiếp theo.

 
Ví dụ:

$\varphi(3,3) = (x \vee y \vee z)\wedge (\bar{x} \vee y \vee \bar{z})\wedge (x \vee \bar{y} \vee z)$

$\varphi(2,4) = (\bar{x} \vee y)\wedge (x \vee \bar{y} )\wedge (x \vee y)\wedge (\bar{x} \vee \bar{y})$

Trong ví dụ trên, biểu thức $\varphi(3,3)$ có phép gán $(x,y,z) = $(True,False,True) có giá trị True. Biểu thức $\varphi(2,4)$ không có phép gán nào có giá trị True.

 
Chứng minh: Bằng chứng mà chúng ta đưa ra ở đây là một phép gán cho các biến của $\varphi(n,m)$. Bằng chứng này là ngắn gọn vì một phép gán có thể được mô tả bằng $O(n)$ bít với mỗi bít biểu diễn giá trị gián của một biến. Để kiểm tra xem một phép gán này có giá trị True hay không, ta sẽ thay giá trị của từng biến vào biểu thức $\varphi(n,m)$. Nếu tất cả các mệnh đề đều có giá trị True thì biểu thức có giái tị True, và ngược lại. Việc tính giá trị của biểu thức có thể được thực hiện trong thời gian $poy(n,m)$. Do đó, một phép gán là một bằng chứng dễ kiểm tra.

 
Ví dụ bài toán xác định biểu thức $\varphi(3,3)$ ở trên có phép gán giá trị True hay không thuộc 3SAT.

Chứng minh tương tự Lemma 1, ta có:

 
Ví dụ $A = \{1,3,11,6,7,8\}$ và $T = 10$, tập $S = \{1,3,6\}$ có tổng bằng $T$.

 
Chứng minh: Ta chứng minh định lý cho bài toán Subsetsum. Bằng chứng ta đưa ra ở đây là một tập các số nguyên $S \subseteq A$. Bằng chứng $S$ ngắn gọn vì ta có thể dùng tối đa $S\log(X)$ bít để biểu diễn $S$, trong đó $X = \max_i \log(|a_i|)$. Để kiểm tra bằng chứng này, ta chỉ việc cộng tất cả các số trong $S$ và kiểm tra xem tổng của chúng có bằng $T$ hay không. Phép cộng này có thể thực hiện được trong thời gian đa thức.

 

Figure 3: Các cạnh tô đậm màu đỏ là các cạnh của một chu trình Hamilton trong đồ thị.

 
Chú ý, trong định nghĩa của đường đi đóng, ta cho phép một đỉnh xuất hiện nhiều lần trên đường đi.

 
Chứng minh Lemma 4 coi như bài tập cho bạn đọc. Trong post tiếp theo, chúng ta sẽ tìm hiểu về NP-complete; tập các bài toán khó nhất trong lớp NP.

Tham khảo

[1] Cook, Stephen. The P versus NP problem. The Millennium Prize Problems (2006): 87-106.
[2] Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
[3] Reddit Thread, https://www.reddit.com/r/compsci/comments/262tw7/knuth_on_why_he_believes_pnp_question_17/. Accessed 19/12/2016.