Giới thiệu về P và NP --- P vs NP

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 nf(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ị.

IndependentSetOpt. Cho một đồ thị vô hướng G(V,E). Một tập đỉnh X\subseteq V được gọi là một tập độc lập nếu không có cạnh nào của đồ thị nối hai đỉnh cùng thuộc X (xem Figure 1). Tìm kích thước của tập độc lập lớn nhất của đồ thị.

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

IndependentSet. Cho một đồ thị vô hướng G(V,E) và một số nguyên K. Xác định xem đồ thị đó có một tập độc lập kích thước ít nhất K hay không?

 
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].
independentset
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).

Definition 1 (P problem): Một bài toán quyết định được gọi là thuộc lớp P nếu tồn tại một thuật toán giải bài toán trong thời gian O(n^c) với một hằng số c không phụ thuộc vào kích thước đầu vào n.

 
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.

Definition 2 (NP problem): Một bài toán quyết định được gọi là thuộc lớp NP nếu tồn tại một bằng chứng ngắn gọn dễ kiểm tra cho bài toán đó.

 

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\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.

P vs NP: Liệu PNP có phải là hai lớp bài toán hoàn toàn khác nhau hay không?

 

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 PNP như sau:

pvsnp
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.

SAT (Satisfiability). Cho một biểu thức logic \varphi(n,m) gồm n biến x_1,x_2,\ldots, x_n có dạng là hội (conjuction) của m mệnh đề (clause) C_1,C_2,\ldots, C_m, trong đó mỗi mệnh đề C_i lại là tuyển (disjunction) của các literal. Mỗi literal là một biến x_j hoặc phủ định của nó \bar{x}_j. Một phép gán (assigment) của \varphi(n,m) là một cách gán cho mỗi biến x_i một giá trị True hoặc False. Giá trị của một phép gán là giá trị của biểu thức (True hoặc False) khi ta thay giá trị tương ứng của biến vào biểu thức. Xác định xem có tồn tại hay không một phép gán của biểu thức \varphi(n,m) có giá trị True.

 
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.

Lemma 1: SAT \in NP.

 
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.


3SAT. Cho một biểu thức logic \varphi(n,m) trong đó mỗi mệnh đề chỉ gồm không quá 3 literals, xác định xem có tồn tại hay không một phép gán của biểu thức \varphi(n,m) có giá trị True.

 
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ó:

Lemma 2: 3SAT \in NP.

 

SubsetSum. Cho một tập gồm n số nguyên A =\{a_1,a_2,\ldots, a_n\} và một số nguyên dương T, tìm tập S\subseteq A sao cho:

\sum_{a\in S}  a = T

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

Knapsack. Cho n đồ vật, trong đó đồ vật thứ i có trọng lượng w_i và giá trị v_i và một cái ba lô có khả năng mang được trọng lượng tối đa W. Liệu ta có thể đựng được đồ vật trong ba lô (mà không quá giới hạn trọng lượng của ba lô) có tổng giá trị ít nhất V hay không?

 

Lemma 3: Subsetsum Knapsack là các bài toán thuộc lớp NP.

 
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.


HamiltonianCycle. Cho một đồ thị vô hướng G(V,E). Một chu trình C trong đồ thị được gọi là chu trình Hamilton nếu chu trình này đi qua mỗi đỉnh đúng một lần. Xác định xem có tồn tại một chu trình Hamilton trong G(V,E) hay không?

 
hamiltonian-cycle
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ị.

Tsp. Cho một đồ thị vô hướng G(V,E), trong đó mỗi cạnh e\in E có một trọng số không âm w(e), và một số nguyên K. Một đường đi đóng (closed walk) là dãy đỉnh v_1,v_2,\ldots, v_\ell-1, v_\ell = v_1 trong đó tồn tại một cạnh của đồ thị nối hai đỉnh liên tiếp v_i,v_{i+1} với mọi  1\leq i \leq i-1. Có tồn tại hay không một đường đi đóng (closed walk) trong G đi qua tất cả các đỉnh mà có tổng trọng số các cạnh trên đường đi không quá K?

 
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.

Lemma 4: HamiltonianCycle Tsp là các bài toán thuộc lớp NP.

 
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.

Facebook Comments

Tags: , , , , , ,

Reply

Your email address will not be published. Required fields are marked *