Đến nội dung

Hình ảnh

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

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết
Đâ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.
Hình đã gửi
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 10.000.000.000, 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.


Hình đã gửi
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 $\frac{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.n...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 $P$ vs $NP$” 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 Hình đã gửi)
* 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.


Theo http://zung.zetamu.net


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#2
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết
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 Máy Turing $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à:
http://s.wordpress.c...f&fg=000000&s=0



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 \to \{ 0,1 \}$ như vậy, mạch Boolean để tính nó cần ít nhất $\frac{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....nizel_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.stanfor.../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.computat...np-problem.html

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 Máy Turing $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à:
http://s.wordpress.c...f&fg=000000&s=0



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 \to \{ 0,1 \}$ như vậy, mạch Boolean để tính nó cần ít nhất $\frac{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....nizel_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.stanfor.../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.computat...np-problem.html

1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh