Tại sao vấn đề P vs NP khó vậy (2)

 

[Cưỡi ngựa xem hoa] [Bổ sung lần cuối: 10/Sep/2012]

Trong bài viết trước (Tại sao vấn đề P vs NP khó vậy) chưa hề nói đến các vũ khí đã dùng “để tấn công thành trì P|NP” . Bài này sẽ thử liệt kê dần các “vũ khí thông dụng” đã dung trong các đợt tấn công này, và lý do vì sao chúng không đánh thắng được thành trì P|NP. Trước hết, có lẽ cần phát biểu lại thật chính xác vấn đề P vs NP.

Các lớp độ phức tạp và vấn đề P vs NP

Để có thể tạo thành các định lý với chứng minh chặt chẽ, thì bản thân phát biểu phải chặt chẽ (nhiều người đưa ra các chứng minh sai, do pĥát biểu vấn đề không chặt chẽ thành ra hiểu lệch vấn đề).

Định nghĩa chặt chẽ của lớp P như sau:

Ký hiệu Sigma* là tập tất cả các các “từ” được viết bởi một dãy hữu hạn các “chữ cái”  trong một “bảng chữ cái” Sigma nào đó gồm hữu hạn các chữ cái (ví dụ như bảng các ký hiệu trong ngôn ngữ thông thường).

Một tập con L thuộc Sigma* sẽ được gọi là một ngôn ngữ. Hình dung nó như tập hợp các “từ” có nghĩa trong một ngôn ngữ. Mỗi phần tử thuộc L là một “từ có nghĩa”,  hay nói cách khác là “đúng và có thể chứng minh được nó là đúng”. Ví dụ như mỗi định lý toán học có thể coi là một “từ” trong ngôn nghữ “các định lý toán học”.

Giả sử có 1 cái Turing machine M chạy trên các băng dùng bảng chữ cái phía trên. (Tất nhiên thay máy Turing bằng mô hình tính toán tương đương nào cũng được). Gọi L(M) là tập tất cả các input mà khi M chạy trên đó thì sẽ dừng lại và chấp nhận input đó (tức là input này khi đưa vào M thì không bị M phủ nhận và cũng không làm cho M chạy mãi không dừng lại được lúc nào). Nếu L = L(M) thì ta gọi L là ngôn ngữ được máy M chấp nhận.

Ngôn ngữ L được gọi là thuộc lớp P, nếu như có một máy M sao cho L= L(M), và một số tự nhiên n sao cho với mọi phần tử x thuộc L ta đều có M khi nhận input là x sẽ dừng lại sau khi chạy không quá |x|^n + n bước, trong đó |x| ký hiệu độ dài của x. (Hàm |x|^n + n là một đa thức của |x|).

Ngoài lớp P, còn có thể định nghĩa rất nhiều lớp độ phức tạp khác của các ngôn ngữ  L, chẳng hạn:

* lớp EXP: thay hàm số |x|^n + n bằng hàm số exp(n|x|) trong định nghĩa trên (thời gian để giải là hàm mũ theo độ dài input)

* Lớp LOGSPACE: không nói đến dùng thời gian bao nhiêu (sau bao nhiêu bước thì máy dừng) mà chỉ nói đến dùng bộ nhớ bao nhiêu: Máy chỉ cần dùng một bộ nhớ (chỗ mà máy có thể ghi lên, rồi xóa đi ghi lại cái khác, bao nhiêu lần cũng được) dài không quá n log (|x| +1). Nếu bộ nhớ có độ dài là K, và bảng chữ cái là Sigma = {0,1}, thì máy khi chạy chỉ có cùng lắm là “2^K nhân với số vị trí của kim” trạng thái khác nhau (mỗi trạng thái ứng với 1 trạng thái của bộ nhớ  + vị trí của kim). Trong trường hợp K có dạng log theo |x|, thì số trạng thái khác nhau có dạng đa thức theo |x|. Vì máy không bị quay vòng thành loop (nếu bị quay vòng sẽ không dừng được) nên số bước máy chạy không vượt quá tổng số trạng thái có thể có. Do đó dễ thấy LOGSPACE là tập con của P.

* Lớp PSPACE: tương tự như trên, nhưng bộ nhớ có chiều dài là đa thức theo |x| thay vì là log. Dễ thấy PSPACE là tập con của EXP, và P là tập con của PSPACE.

* Lớp NP. Có thể định nghĩa NP bằng việc tồn tại “nondeterministic Turing machine”  M sao cho L = L(M) và M chấp nhận các input từ L với thời gian là đa thức. (Máy “nondeterministic” là máy có “vô số phiên bản” mỗi phiến bản đi theo một “hướng” tìm lời giải khác nhau. Chỉ cần 1 phiên bản dừng và chấp nhận input nào đó, là toàn bộ máy dừng và chấp nhận). Chữ N trong NP chính là viết tắt của từ “nondeterministic”. Một định nghĩa tương đương khác của NP, mà chỉ dùng máy Turing thông thường (deterministic), là lời giải có thể kiểm tra trong thời gian là đa thức.

Nói một cách chính xác hơn, L thuộc NP, nếu như có một tập con R của Sigma* X Delta*, trong đó Delta là một bảng chữ cái hữu hạn khác (tập R này gọi là tập các quan hệ kiểm tra), sao cho các điều kiện sau đây thỏa mãn:

i) Ngôn ngữ  {w#y | (w,y) nằm trong R} thuộc lớp P. Ngôn ngữ này có bản chữ cái là hợp của Sigma, Delta, và một ký hiệu đặc biệt là # (không nằm trong Sigma và Delta, và để cho tiện có thể coi Sigma và Delta cũng không giao nhau)

ii) Tồn tại số tự nhiên n sao cho một từ w trong bảng chữ cái Sigma là thuộc L khi và chỉ khi tồn tại một từ y trong bảng chữ cái Delta sao cho (w,y) thuộc R và |y| nhỏ hơn hoặc bằng n|w|^n.

Hình dung như sau: y là chứng minh của w, độ dài của chứng minh là đa thức so với độ dài của input, và việc kiểm tra chứng minh (quan hệ R) cũng chỉ mất thời gian là đa thức.

(Chú ý: khi một “ngôn ngữ” nằm trong lớp NP, thì có nghĩa là với mỗi “từ” của nó đều tồn tại “lời giải” có thể kiểm tra được trong thời gian đa thức, nhưng không có nghĩa là có thể tìm được lời giải trong thời gian đa thức, và cũng không có nghĩa là mọi lời giải đều kiểm tra được trong thời gian đa thức)

Sau khi định nghĩa chặt chẽ như trên, thì vấn đề “P có khác NP hay không” trở thành một giá thuyết toán học chặt chẽ.

Dễ thấy là:

LOGSPACE \subset P \subset NP \subset PSPACE \subset EXP

Phương pháp chéo hóa (diagonalization) và vấn đề tương đối hóa (relativization)

Phương pháp chéo hóa được Cantor nghĩ ra từ giữa thế kỷ thứ 19 để chứng mình rằng đoạn thẳng [0,1] là một tập không đếm được. Phương pháp rất đơn giản: chứng minh bằng phản chứng, giả sự nó đếm được, thì đánh số được các phần tử của nó. Sau đó chỉ cần tạo ra một số mới, sao cho chữ số thứ n sau giấu phẩy của số đó khác với chữ số thứ n của số có thứ tự là n trong việc đánh số trên, thì số đó sẽ khác tất cả các số đã được đánh số nhưng vẫn thuộc đoạn thẳng [0,1], tạo ra mâu thuẫn.

Phương pháp chéo hóa đơn giản nhưng hữu hiệu trong logic. Nó được Godel dùng để chứng minh định lý không đầy đủ, và cũng được dùng để chứng minh việc không có thuật toán nào để có thể xác định sự hay hay không dừng của mọi máy Turing. (Định lý về xác định sự dừng này được gán cho Turing, nhưng hình như bản thân Turing chưa bao giờ chứng minh nó, mà các chứng minh chỉ xuất hiện quãng những năm 10950 ?)

Dùng phương pháp chéo hóa, có thể chứng minh chẳng hạn LOGSPACE không bằng PSPACE. Tuy nhiên, đến khi đụng đầu phải thành trì P|NP thì vũ khí chéo hóa không ăn thua. Vấn đề là, nếu có một lời giải nào đó cho P|NP mà dùng chéo hóa, thì nó cũng đúng với các vấn đề N|NP được tương đối hóa (relativized). Tuy nhiên, khi tương bị đối hóa, thì có lúc “P khác NP” trở nên đúng và có lúc nó trở nên sai. Bởi vậy, mọi phương pháp mà có thể tương đối hóa được thì không dùng để tấn công P|NP được.

Thế nào là tương đối hóa ? Tương đối hóa ở đây hiểu là, thay vì nói đến các phép tính đơn giản nhất (như kiệu cộng trừ hai số có 1 chữ số), ta cho phép mỗi bước tính là một phép tính phức tạp hơn thế nằm trong một họ các phép tính nào đó. Ví dụ, ta cho phép là cứ với mỗi đồ thị, thì việc tìm ra (nếu có) một chu trình Hamilton của đồ thị đó chỉ là một bước tính. Tất nhiên, bước tính đó có thể rất dài, gồm nhiều phép tính đơn giản, nhưng ta vẫn coi nó chỉ là 1 bước.Trong ngôn ngữ tin học, một họ các bước tính như vậy mà ta được phép sử dụng gọi là một oracle (một quả bóng thần: hỏi gì trả lời đấy ngay lập tức, trong phạm vi một họ các câu hỏi nào đó).

Nếu ta có một oracle A, thì ta có thể xây dựng lớp độ phức tạp P^A: đấy là lớp các bài toán giải được theo thời gian là đa thức, nhưng mỗi bước thời gian không phải là làm một phép tính đơn giản, mà là đi hỏi quả bóng thần A một lần (như vậy tiết kiệm được rất nhiều phép tính). Tương tự như vậy, có thể định nghĩa NP^A. Câu hỏi đặt ra là “P^A có khác NP^A”. Câu hỏi đó được gọi là sự tương đối hóa của vấn đề “P có khác NP ?”.

Định lý (Baker-Gill-Soloway 1975). Tồn tại hai oracle A,B sao cho P^A bằng NP^A nhưng P^B khác NP^B.

Chứng minh sự tồn tại của A sao cho P^A = NP^A: có thể kiểm tra dễ dàng là điều này đúng với bất kỳ oracle A nào là PSPACE-complete.  (Một bài toán gọi là PSPACE-complete nếu nó nằm trong lớp PSPACE, và mọi bài toán khác trong lớp PSPACE có thể suy được về bài toán này qua một lượng thời gian là đa thức. Bài toán xác định xem một từ có thỏa mãn một số qui tắc ngữ pháp nào đó không (word problem) là một ví dụ về bài toán PSPACE-complete.) Việc chứng minh khẳng định này khá dễ.

Chứng minh sự tồn tại của B sao cho P^B =! NP^B: vế này tế nhị hơn. Cách xây dựng B cũng tương tự như phương pháp chéo hóa.  Xem chi tiết chẳng hạn trong: Jonathan Katz, Lecture on relativization.

Boolean Circuits

Các mạch Boolean là các mạch dùng các “cửa” OR, AND, NOT, và không có loop.

Ví dụ, để tính 1 hàm n biến, mỗi biến nhận 1 trong 2 giá trị 0 và 1, thì có thể làm  1mạch Boolean với n đầu vào và 1đầu ra. Shannon từ năm 1949 đã chứng minh được rằng với hầu hết các hàm n biến f: {0,1}^n -> {0,1} như vậy, mạch Boolean để tính nó cần ít nhất 2^n/n cửa, tức là số cửa (số phép tính) là hàm mũ của độ dài của đầu vào. Tuy nhiên, phương pháp của Shannon không cho biết đối với các bài toán thuộc NP thì sao.

Dễ thấy điều sau: nếu L là một ngôn ngữ dùng bảng chữ cái {0,1} thuộc lớp P, thì tồn tại một đa thức P, sao cho vớ mỗi số tự nhiên n tồn tại một mạch Boolen B_n có số cửa không vượt quá P(n) để tính được các phần tử thuộc L có độ dài n (tức là nếu thuộc L thì cho kết quả 1, không thuộc L thì cho kết quả 0). Tuy nhiên điều ngược lại không đúng: với mỗi n tồn tại B_n như vậy, thì cũng chưa chứng tỏ L thuộc lớp P. (Khi thuộc P thì họ mạch B_n phải có “cùng thiết kế” với mọi n, chứ không phải mỗi B_n thiết kế một kiểu khác nhau). Nếu chỉ ra được rằng với 1 bài toán NP-complete nào đó tồn tại Boolean circuit B_n (có số cửa là đa thức) như vậy với mọi n, thì cũng chưa có nghĩa là P bằng NP, nhưng nếu chỉ ra được là không tồn tại các mạch B_n như vậy thì có nghĩa là P khác NP.

Từ năm 1985, Alexander Razborov và các tác giả khác đã chỉ ra được rằng là đối với các bài toán NP-complete, thì cần dùng mạch có số cửa là hàm mũ, nếu như đó là mạch đơn điệu, tức là mạch không có cửa NOT. Thế nhưng phương pháp của Razborov không còn hữu hiệu nếu như mạch được phép có cửa NOT. Lý do là việc không có cửa NOT làm cho mạch phải phình lên nhiều để thay thế sự thiếu hụt đó, và như vậy cách tiếp cận của Razborov không tấn công được bài toán P|NP

Xem chẳng hạn bài báo của Alisa Knitzel về chứng minh định lý Razborov khá đơn giản dựa trên một số công thức tổ hợp:

http://www14.in.tum.de/konferenzen/Jass09/courses/1/Knizel_paper.pdf

Có một lớp độ phức tạp gọi là LINEAR-SIZE được định nghĩa như sau: tồn tại các mạch B_n giải ngôn ngữ L, sao cho đọ dài của B_n là tuyến tính theo n: |B_n| = O(n).

Định lý. Nếu P là tập con của LINEAR-SIZE, thì P khác NP.

Định lý này là hệ quả của hai điều sau:

1) Định lý Kannan (1982): tồn tại những bài toán trong polynomial hierarchy không thuộc LINEAR-SIZE

2) Nếu P = NP thì toàn bộ polynomial hierarchy bằng P

(Hệ quả: nếu P=NP thì có những bài toán trong P mà không thuộc LINEAR-SIZE)

Cho đến nay, người ta chưa biết P có nằm trong LINEAR-SIZE hay không. (Điều ngược lại dễ thấy hơn: LINEAR-SIZE không phải là tập con của P ?)

Thuật toán ngẫu nhiên

Có những thuật toán cho phép tìm lời giải nhanh bằng cách sử dụng một số phương pháp ngẫu nhiên, đưa vào các random bits, v.v. Tuy nhiên, các thuật toán này cũng không tấn công được P|NP ?

Bổ sung tài liệu

Complexity zoo: http://qwiki.stanford.edu/index.php/Complexity_Zoo

Bài viết của Fortnow về tình hình bài toán P vs NP, 2009: Xem http://blog.computationalcomplexity.org/2009/08/status-of-p-versus-np-problem.html

(to be continued)

—————-

Phụ lục: Định nghĩa máy Turing

Máy Turing là một mô hình toán học của việc tính toán, tương đương với các mô hình máy tính “cổ điển” khác.

Một máy Turing M gồm một bộ (\Sigma, \Gamma, Q,\delta) trong đó $\Sigma, \Gamma, Q$ là những tập hữu hạn, trong đó  $latex  \Sigma$ gọi là bảng chữ cái chứa một chữ cái đặc biệt gọi là b (blank — trống không viết gì), và \Gamma là một tập con của bảng chữ cái không chứa “blank”: . Tập Q gọi là tập các trạng thái (số trạng thái cũng hữu hạn), trong đó có 3 trạng thái đặc biệt gọi là “ban đầu” (0), “nhận” (accept), “bỏ”  (reject). \delta là một ánh xạ chuyển đổi (máy M chạy theo sự chuyển đổi này):

\delta: (Q \setminus \{``accept'', ``reject''\}) \times \Gamma \to Q \times \Gamma \times {-1,1}

Hiểu phép biến đổi \delta như thế này: máy đang ở một trạng thái nào đó (mà không thuộc một trong hai trạng thái dừng “accept”, “reject”) và mũi kim đa ở vị trí  nào đó trên dải băng ghi các chữ cái (bộ nhớ). Khi đó kim đọc xem là chữ cái gì ở đó. Ứng với mỗi trạng thái và mỗi chữ cái như vậy, thì máy quyết định chuyển về một trạng thái nào đó (thay vì trạng thái cũ), ghi một chữ cái nào đó vào ô mà kim đang chỉ (thay vì chữ cái cũ), và dịch chuyển kim hoặc là tiến lên phía trước hoặc là lùi về phía sau 1 bước trên dải băng.

Máy bắt đầu ở trạng thái “ban đầu”, với mũi kim nằm ở đầu dải băng, và nhận input ghi trên dải băng (ghi bắt đầu từ ô đầu tiên). Máy sẽ chạy theo nguyên tắc \delta, và dừng lại khi rơi vào một trong hai trạng thái “nhận” hoặc “bỏ”, còn nếu không thì nó sẽ cứ chạy mãi.

 

Print Friendly
 

9 comments to Tại sao vấn đề P vs NP khó vậy (2)

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Spam Protection by WP-SpamFree