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

 

Đây chỉ là một bài cưỡi ngựa xem hoa thôi, vì sự hiểu biết của tôi về tin học chỉ ở mức “lớp 1″. Tuy nhiên, nghe người ta nói “vấn đề P vs NP” là vấn đề lý thuyết “quan trọng nhất của thời đại” nên cũng phải tìm hiểu nó xem sao, coi như là bổ túc văn hóa.

Các nhà toán học tìm ra các cấu trúc và định lý toán, các nhà vật lý tìm ra các định luật của vũ trụ, v.v. Vì sao họ tìm được ? Đứng từ quan điểm tin học, thì là bởi vì các thứ đó có thể tìm được, thuộc loại vấn đề có thể giải quết được, trong một khoảng thời gian không quá lớn !

Thế nào là không quá lớn ?

Một giây, một phút, một giờ, một ngày, một năm, hay chục năm, đều có thể coi là không quá lớn. Hay thậm chí 100 năm, 1000 năm vẫn chưa là quá lớn đối với loài người. Một số vấn đề từ lúc xuất hiện đến lúc có lời giải là mấy trăm năm thật, ví dụ như định lý lớn Fermat. Một vạn năm bắt đầu là “hơi lớn”: lich sử nước Việt Nam, theo các sách “chính thống”, cũng mới chỉ có 4 ngàn năm, trong đó những 2 ngàn năm ứng với “18 đời vua Hùng” — xem ra các vua Hùng là thánh nhân phi thường mỗi ông trị vì trên 100 năm ! Còn đến 10 tỷ năm là quá lớn, bởi bản thân trái đất chưa chắc đã tồn tại được 10 tỷ năm.

Nếu dùng hệ thập phân mà viết, thì 10 tỷ năm thực ra chẳng là bao: nó là 10^10, hay 10000000000, với “chỉ có” 10 chữ số 0. Hay dùng hệ nhị phân, thì nó cũng chỉ là một số với hơn 30 chữ số. Nay hãy tưởng tượng những số có 100 chữ số, hay thậm chí 1000 chữ số. Để viết ra một số như vậy, chỉ cần một vài phút. Nhưng để viết ra toàn bộ các số như vậy, tức là 10^1000 số khác nhau, thì cả vũ trụ này không có đủ chỗ chứa !

Đấy là sự khá nhau căn bản giữa N (một số nào đó, ví dụ 1000), và exp(N) (hay 10^N, hay 2^N): N là một số tương đối nhỏ, thậm chí N^2, N^3 cũng còn “khá nhỏ”, nhưng đến exp(N) thì đã lớn hơn ty tỷ lần số các nguyên tử trong vũ trụ của chúng ta rồi. Đối mặt với những con số như exp(N), thì máy tính có hiện đại đến mấy cũng “không là cái đinh gì”. Dù cho máy tính có chạy nhanh gấp 1 tỷ hiện tại, kể cả các loại “máy tính lượng tử”, kể cả gộp tất cả các máy tính của thế giới vào, thì cũng sẽ không bao giờ có thể tính được exp(N) phép tính trong vũ trụ này (với N = 1000).

Bởi vậy, các bài toán mà lời giải cần đến exp(N) phép tính, dù rằng về mặt lý thuyết toán học thuần túy có thể coi là giải được, nhưng về mặt tin học là không giải được, ít ra là trong thế giới của chúng ta. Từ lâu, các nhà tin học đã biết điều này, và đã tìm cách hình thức hóa các lớp vấn đề có thể giải được với thời gian không quá lớn. Lớp các vấn đề đó được gọi là lớp P.

Lớp vấn đề P

P là viết tắt của chữ “polynomial”, tức là đa thức. Một vấn đề được xếp vào lớp P, nếu như có thuật toán sao cho cứ với mỗi “đầu vào” có chiều dài (tức là số chữ số hay ký hiệu để mô tả đầu vào) là N thì cho ra kết quả (đầu ra) sau cùng lắm là P(N) phép toán đơn giản nhất (kiểu cộng trừ hai số có một chữ số với nhau), trong đó P là một đa thức nào đó.

NHững vấn đề như: cộng hai số tự nhiên, nhân hai số tự nhiên, xếp hạng 1 danh sách các số từ nhỏ đến to, tính chính xác căn bậc hai đến N chữ số, v.v. là những ví dụ về các vấn đề thuộc P.

Vấn đề “mò kim đáy biển” là một ví dụ không thuộc P: A giữ một số bí mật có N chữ số. B phải đoán số đó là bao nhiêu. Mỗi lần hỏi A thì A không cho thông tin nào khác, ngoài thông tin số mà B đoán có đúng là số bí mật mà A giữ không. Vì không có được thông tin nào, nên B không còn cách nào khác là cách “thử thô thiển” (brutal search) tất cả các số có thể (sẽ là 10^N số nếu là hệ thập phân) cho đến khi tìm được kết quả. Tính trung bình thì sẽ phải cần đến (10^N)/2 phép thử. Tôi hơi “ăn gian” ở ví dụ này, vì các vấn đề “định tính” trong định nghĩa của lớp P không có yếu tố “bí mật” (ngẫu nhiên) trong đó, tuy nhiên nó là ví dụ tốt để hình dung là có những vấn đề không thể giải được từ quan điểm tin học tuy về “thuần túy toán học” thì là giải được.

Lớp vấn đề NP

Có những vấn đề mà, việc tìm lời giải có thể mất rất nhiều thời gian, nhưng một khi có ai đó đưa ra lời giải, thì có thể kiểm tra trong một thời gian không quá lớn xem lời giải đó có đúng hay không. Ví dụ như các định lý hay các giả thuyết toán học: tìm ra định lý, chứng minh giả thuyết là công việc có thể vô cùng khó, nhưng một khi đã có chứng minh, thì việc kiểm tra chứng minh có đúng hay không là việc về nguyên tắc sẽ mất ít thời gian hơn nhiều so với việc tìm ra lời giải đúng.

Các nhà tin học gọi các vấn đề như vậy là các vấn đề thuộc lớp NP. Nói một cách chính xác hơn, một vấn đề thuộc lớp NP khi mà có một thuật toán kiểm tra lời giải sao cho mỗi khi có 1 lời giải cho 1 input có độ dài N thì thuật toán kiểm tra lời giải sẽ cho biết là lời giải có đúng hay không sau không quá P(N) phép toán đơn giản, trong đó P là một đa thức (không phụ thuộc vào input).

Một ví dụ bài toán thuộc lớp NP là bài toán SAT (satisfiability problem): một SAT độ dài N là một biểu thức logic gồm có không quá N ký hiệu trong đó, ví dụ như

(a hoặc b hoặc (không c)) và (a hoặc d hoặc c) và (b hoặc (không e) hoặc (không f)) và  …

Lời giải của một SAT như vậy là gắn các giá trị “đúng”, “sai” cho các đơn thức logic thành phần trong đó (ví dụ a = đúng, b = sai, c = sai, v.v.) sao cho biểu thức được thỏa mãn (tức là giá trị của nó = đúng)

Có một biểu thức SAT, việc tìm lời giải có thể rất khó, nhưng việc kiểm tra xem lời giải nào đó có đúng hay không là một việc dễ (lượng công thức đơn giản phải kiểm tra là một đa thức của N) , bởi vậy bài toán SAT thuộc lớp NP.

P khác NP ?!

Tất nhiên, các vấn đề thuộc P thì cũng thuộc NP. Nhưng điều ngược lại có đúng hay không là “bài toán tỷ đô la” mà cho đến nay thế giới chưa có lời giải. Nó là 1 trong số 7 bài toán thiên niên kỷ mà Clay treo giải 1 triệu USD, nhưng ý nghĩa của nó vượt xa cái mức giải 1 triệu được treo ra đó.

Nhiều thuật toán bảo mật tin học ngày nay dựa trên giả thuyết là P khác NP, tức là kiểm tra thì dễ nhưng tìm đáp số thì không thể tìm được trong khoảng thời gian vừa phải. Một ví dụ là thuật toán mã mở (public-key cryptography) RSA (được dùng trong các giao dịch điện tử) dựa trên niềm tin sau: nếu có hai số nguyên tố (mỗi số có vài trăm chữ số) thì việc tính tích của chúng là việc rất dễ dàng, nhưng khi có một tích như vậy, thì việc tìm lại hai số nguyên tố là việc không thể thực hiện được nếu không biết trước các số đó. Nhưng nếu P=NP thì việc tìm lại hai số nguyên tố của một tích cũng trở nên việc dễ dàng, và RSA cũng như nhiều thuật toán mật mã khã đi tong, rất nhiều vấn đề hóc búa đến mức không giải được từ trước đến nay (kể cả giả thuyết Riemann ?) trở nên “dễ”, và thế giới này sẽ thay đổi rất nhiều.

Vấn đề “P có khác NP” được Godel đặt ra trong một bức thư viết cho von Neumann vào năm 1956, nhưng bức thư đó về sau người ta mới để ý đến. Vấn đề bắt đầu được thực sự quan tâm vào quãng năm 1970, sau khi các nhà toán học Cook và Levin chứng minh được rằng có những bài toán là “NP-complete“, tức là khó nhất trong các vấn đề NP: mọi bài toán khác thuộc lớp NP đều đưa được về một bài toán NP-complete cho trước bằng một phép biến đổi sử dụng một lượng thời gian là đa thức. Như vậy, chỉ cần một bài toán NP-complete có lời giải với thời gian đa thức, là đủ để P=NP. Nhưng “tiếc thay”, bao nhiêu cố gắng tìm lời giải thời gian đa thức cho các bài toán NP-complete từ trước đến này đều “công cốc”, tuy rằng người ta đã biết đến hàng trăm bài toán NP-complete khác nhau, ai muốn chọn bài nào để tấn công thì chọn: chu trình Hamilton, SAT, 3SAT, đường đi ngắn nhất của người bán hàng, bài toán Steiner (đường ngắn nhất nối các điểm trên mặt phẳng), bài toán xác định xem một đồ thì có phải là đồ thị con của một đồ thị khác không, v.v. Có thể xem 1 danh sách gần 100 bài toán NP-complete ở đây.

Ngày nay, phần lớn các chuyên gia tin rằng P khác NP, tuy rằng có một số ít người vẫn tin hay “hy vọng” rằng P bằng NP, và một số ít hơn nữa thì coi rằng đây là vấn đề không có lời giải. Nhìn từ khía cạnh logic, có các tình huống sau có thể xảy ra cho vấn đề “P khác NP”:

1) P khác NP, và một lúc nào đó người ta sẽ chứng minh được điều này

2) P bằng NP, và một lúc nào đó người ta sẽ chứng minh được điều này

3) P khác NP, nhưng sẽ không bao giờ có ai tìm được chứng minh. (Hình dung là bản thân vấn đề “P khác NP” là vấn đề khó kiểu NP: nếu có lời giải thì có thể kiểm tra dễ dàng, nhưng đi tìm lời giải sẽ mất 10 mũ 1000 phép thử,  vượt xa khả năng của vũ trụ này)

4) P bằng NP, nhưng sẽ không bao giờ có ai tìm được chứng minh. (Khả năng này khó hình dung hơn là khả năng thứ 3, vì nếu P=NP thì bản thân bài toán “P có khác NP không” là bài toán “dễ” và như vậy sẽ phải có người tìm được lời giải”

5) Vấn đề “P khác NP” độc lập với các hệ tiên đề toán học hiện tại (tương tự như là giả thuyết continuum) và như vậy “không đúng mà cũng không sai”, tức là không tồn tại chứng minh là nó đúng hay nó sai theo logic hiện tại (dù cho chứng minh đó có dài bao nhiêu dòng đi nữa).

 Mỗi tuần một “chứng minh” mới

Trong các vấn đề mở nổi tiếng của toán học (và tin học — vấn đề P vs NP coi là tin cũng được mà toán cũng được), thì vấn đề P vs NP là vấn đề có phát biểu khá dễ hiểu (phát biểu dễ hiểu nhất trước kia là định lý Fermat, thứ nhì có lẽ đến P vs NP), do vậy nó thu hút không chỉ các nhà toán/tin học chuyên nghiệp, mà còn vô thiên lủng các nhà khoa học nghiệp dư cũng đưa ra các lời giải cho nó. Theo hiểu biết hạn hẹp của tôi, thì cho đến nay, tất cả các lời giải đều sai.

Có một “tuyển tập các lời giải bài toán P vs NP” ở trang web này, trong đó “entry” mới nhất là vào tháng 07/2012:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Các lời giải này theo đủ các hướng: bằng, không bằng, và không xác định được. Số lời giải “amateur” cho bài toán P vs NP nhiều đến mức có những chuyên gia tuyên bố sẽ không chịu đọc phản biện lời giải nào cho bài toán này nữa, trừ khi tác giả phải đưa ra được các lý lẽ thật là thuyết phục cho những vấn đề mở đơn giản hơn P vs NP nhiều lần (nhưng là các hệ quả nếu P vs NP dễ dàng được giải quyết) đã. Hình dung là để “trèo lên tháp PvsNP” cần 40 bước, trong đó ngay 3 bước đầu tiên người ta đã chưa biết cách trèo thế nào, mà đã đòi nhảy vọt.

Đi hỏi chuyên gia

Có hy vọng gì là một amateur có thể giải được vấn đề P vs NP trong khi các chuyên gia “bươu đầu sứt trán” cả nửa thế kỷ nghĩ không ra không ? Cũng có thể là có. Nhưng trước hết phải đi hỏi các chuyên gia về các lỗi mà hàng trăm hay hàng nghìn “cảm tử quân” đi trước đã mắc phải, các con đường dẫn đến ngõ cụt, cũng như các tiến bộ đã đạt được tuy nhỏ nho đã. Nếu chưa biết được những điều đó mà đâm đầu vào ra lời giải, thì 99,99999% khả năng sẽ là một lời giải lặp lại các sai lầm như trước.

Thử làm một danh sách nhỏ các chuyên gia, với mục đích “học mót” từ họ xem tại sao vấn đề P vs NP khó như vậy. Trong quá trình học mót này sẽ hiểu thêm được nhiều điều về độ phức tạp trong tính toán !

* Eric Allender, với bài survey khá gần đây: A Status Report on the P versus NP Question

* Scott Aaronson. Ông này ở MIT, có nhiều bài viết về vấn đề này. Thử xem các bài: Has There Been Progress on the P vs. NP Question? (nói về các tiến bộ trong vấn đề P vs NP cho đến những năm gần đây — tuy lời giải còn xa vời nhưng tiến bộ là có thật), Is P Versus NP Formally Independent? (nói về khía cạnh logic của vấn đề P vs NP), Eight signs a claimed proof of P =! NP is wrong (khi nào nghĩ ra chứng minh, thì hãy kiểm tra nó bằng 8 phép thử này trước khi đem trình làng :D )

* Stephen Cook. Đề bài chính thức của Clay về vấn đề P vs NP là do ông Cook viết.

* J. Hastad. Xem bài này: Clique is hard to approximate within n^(1− epsilon). Acta Mathematica, 182:105–142, 1999.

* Oled Goldreich. Một chuyên gia về độ phức tạp. Xem tệp bài giảng này.

* Leonid Levin. Ông này là học trò (?) của Kolmogorov  và là người đưa ra lý thuyết độ phức tạp trung bình. Định lý “SAT là NP-complete” mang tên Cook-Levin, do hai ông này nghĩ ra độc lập. Thử xem bài A tale of one-way functions của Levin viết năm 2000-2003 về các hàm tính xuôi thì dễ nhưng tính ngược lại thì không thể tính nổi. Sự tồn tại của các hàm như vậy vẫn đang chỉ là giả thuyết, và nếu chúng tồn tại thật thì cũng có nghĩa là P khác NP.

* Richard J. Lipton. Ông này là thầy hướng dẫn của ông Avi Wigderson nhắc phía dưới đây. Có một định lý mang tên Karp-Lipton năm 1980 phát biểu  như sau: “if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level”.

* K. Mulmuley. Ông này đưa ra lý thuyết độ phức tạp hình học. Có ai muốn dùng hình học đại số vào giải quyết vấn đề độ phức tạp không ?!

* Micheal Sipser. Thử xem bài này viết năm 1992: The History and Status of the P versus NP question

Avi Wigderson ở IAS Princeton. Ông này có các bài giảng về complexity rất thú vị, có video trên youtube.

Có tệp bài giảng này của Luca Trevisan năm 2004 về “computational complexity“, giải thích về các complexity hierarchies, và chứa nhiều kết quả rất gần đây.

Tạm thời thế đã, sẽ bổ sung sau :D

Print Friendly
 

11 comments to Tại sao vấn đề P vs NP khó vậy ?

  • tqv MonsterID Icon tqv

    Sao những lão như Terrence Tao không thử đâm đầu vào giải nhỉ. Hay là lão vẫn âm thầm làm thử rồi mà chưa ra kết quả??

  • hong van MonsterID Icon hong van

    @Zung: day la bai noi cua chi o vien toan ve van de P vs NP
    https://dl.dropbox.com/u/50296562/complexityhanoi042012.pdf

    Day la bai chi viet o arxiv co lien quan toi van de nay
    http://arxiv.org/abs/1011.2887
    (Example 2.11 va Remark 2.12 chua chinh xac, chi da sua va gui cho editor nhung chua put tren arxiv)

  • admin MonsterID Icon admin

    HÓa ra chị Vân cũng nghiên cứu cái này. Trong bài của chị Vân không thấy nhắc đến Smale nhỉ ?

  • hong van MonsterID Icon hong van

    @Zung: cai nhom cho chi lam theo loi hoc tro cua ong Cook la nhom manh nhat ve complexity day, co 2 cau la invited speakers o ICM va rat dang active.
    Dau tien la bon o day muon xem cai cau Mulmuley lam gi co hay ko nen to chuc xeminars etc…
    Chi chi lam tay trai thoi, trong luc roi rai.

  • admin MonsterID Icon admin

    Cho cua chi Van hoa ra la 1 lo` ghe nhi.

    Lai noi den Smale, o Toulouse co 1 lao (vua bi chet vi ung thu nam nay) lam ve do phuc tap trong real analysis. Lao nay nghi ra mot so khai niem dong thoi voi Smale, va sau do thi cung duoc Smale rat quan tam. Nhung 1 lan khi lao nay xin thang chuc lam prof thi bi 1 phan bien “pure maths” tuong cho 1 cau la “nhung cai anh nay lam cu nhu la cac bai tap cua sinh vien nam thu 3″ !

  • hong van MonsterID Icon hong van

    @Zung: cai cau Smale lam ve complexity khong co lien quan toi cai chi lam nen chi khong trich.

    Chi cung co cau ban lam ve pure math rat trinh thuong voi bon lam ve applied. Cau ke hoc tro cau khong hoc duoc pure math nhay sang applied thi duoc lam GS (dai loai nhu vay chi ko nho chinh xac). Ong Hilbert da tung tuyen bo, vat ly la qua kho cho cac nha vat ly.
    Tuy vay nghe noi Mumford nhay sang applied math khong thanh cong nhu truoc.

  • shakhi MonsterID Icon shakhi

    em là dân technology, bấy lâu nay ngước nhìn các nhà pured math với ánh mắt đầy ngưỡng mộ, hệ quả của sự ngưỡng mộ đó là em biết được trang này. Nhưng dạo này em thấy là các “nhà toán học lý thuyết”, thỉnh thoảng cũng phát biểu những câu thật là tệ, có thể làm “hại đời” những người làm technology như em.

  • hong van MonsterID Icon hong van

    @shakhi: bon toan ly thuyet kieu nhieu khi la vi khong hieu cai gi kho trong toan ung dung.
    Truong hop Hilbert la khac, ong ay nhay vao lam ly thuyet tuong doi rong sau Einstein ma ra ket qua truoc Einstein. Khi ong ay bao cao ve ket qua cua ong o Goettingen ngay 16.11.1915 ong ay cung moi Einstein di nghe nhung Einstein khong di ma nho Walter Baade (luc day la assistant o Goetingen, ve sau la nha thien van hoc co tieng) nghe va viet tom tat gui lai. (Baader da lam ngay bang cach gui postcard co phuong trinh cua Hilbert cho cong su cua Einstein o Berlin la Erwin Freundlich). Sau khi bao cao Hilbert gui bai cho vien HLKH cua Goettingen bai bao “Die Grundlagen der Physik”(Co so cua vat ly) co chua phuong trinh ly thuyet tuong doi mo rong. Nam ngay sau khi Hilbert gui bai di, ngay 25. 11. 1915, Einstein moi gui bai cua minh vao vien HLKH Berlin. Bai cua Einstein duoc ra truoc. Den ngay 20.12 Einstein gui thu xin loi Hilbert vi khong nhac toi cong trinh cua Hilbert trong bai cua minh. Sau do hai nha khoa hoc da hoa giai voi nhau. Vi the cac nha vat ly quen mat Hilbert, mac du phuong trinh cua Hilbert hay hon vi y tuong cua Hilbert dua tren co so thong nhat truong, luc day la qua moi cho cac nha vat ly. (Einstein tu khi di tu phuong trinh tuong doi hep (la cai Poincare cung nghi ra tu truoc) den tuong doi rong phai mat may nam hoc hinh hoc vi phan voi Marcel Grossmann nen khong the nhanh bang Hilbert duoc).

    Nguon: Klaus P. Sommer und Daniela Wuensch, Einsteins Impulsgeber, Sueddeutche Zeitung 21.1.2012, dang lai tai Mitteilung der DMV, 20/2012.

  • zyx MonsterID Icon zyx

    Bạn tqv vẫn có ý nghĩ về universal superman à? :D

  • Thai.dao MonsterID Icon Thai.dao

    Bai hay qua thay oi. Em cung hoc mot so mon ve Scheduling Theory va Mathematical Programming, con nhieu mo ho ve NP va P. Thay oi mo them topics ve dynamical system va cah dung Vennsim, stella duoc khong thay!

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