Archive for the ‘Khoa hoc’ Category

Nhân vật của tuần: anh Vinay (NP vs P)

Tháng Tám 9, 2010

Nhân vật nóng của tuần này phải là anh Vinay.

Anh Vinay là cán bộ nghiên cứu của công ty trách nhiệm hữu hạn HP. Anh (nói đúng hơn là bạn anh) vừa pót lên mạng một bài báo dài, thông báo vùa giải quyết vấn đề NP \neq P. Đây là một trong sáu vấn đề triệu đô còn lại của viện Clay. Nói vậy, để chứng tỏ là nó khó, và nhiều người quan tâm.

NP \neq P là vấn đề trọng tâm của lý thuyết máy tính hiện đại. Định nghĩa thì lằng nhằng, nhưng bạn có thể hiếu đơn giản là nếu NP \neq P, thì có những bài toán mà ta có thể kiểm tra sự chính xác của đáp số (tưởng tượng là có một vị thần, hay cá vàng, cho ta đáp số) môt cách nhưng chóng bằng máy tính, nhưng không thể dùng máy tính để tự tìm ra đáp số này. Ý nghĩa vấn đề này rất hay, ấy là: Máy tính không phải cái gì cũng làm được !! (suy ra, các nhà toán học cần được đãi ngộ đúng mức, nhỉ (:=).)

Ví dụ đơn giản là bài toán tô màu. Có một đồ thị n điểm. Cá vàng nói với ta rằng đồ thị này tô được bằng ba màu. Muồn tìm ra cách tô màu, bạn có thể
thử tất cả các cách tô mầu có thể. Mỗi đỉnh có thể tô một trong ba mầu, vậy tổng cộng có 3^n cách tô mà máy tính phải xét, tức nó phải làm 3^n thuật toán. Nêu n lớn (n =1000), máy tính sẽ không bao giờ đủ thời gian để làm ngần ấy phép toán, dù nó có chạy nhanh như ánh sáng. Có những cách nhanh hơn một it, nhưng số bước chạy vẫn tiến đến vô cùng rất nhanh so với n. Nhưng nếu cá vàng rỉ tai cho ta cách tô màu, thì máy tính có thể kiểm tra xem cá vàng có nói đúng hay không rất nhanh, nó chỉ cần xét tất cả các đỉnh ở cùng một cạnh của đồ thị (tôi đa là {n \choose 2} cạnh) xem mầu của chúng có khác nhau không. Nếu số phép toán máy tính cần làm là hàm da thức trong n (như n^2, n^3 etc) thì (về mặt lý thuyết) thuật toán được coi là khả thi (nhanh).

Anh Vinay có làm đúng không thì chưa ai dám nói. Bac Cook bảo là chứng minh của anh ấy trong có vẻ “nghiêm túc” (serious). Mà một trăm trang mới chỉ là tóm tắt, còn rất nhiều chi tiết sẽ được viết sau. Làng còn phải chờ.

Dưới đây là địa chỉ mạng của anh Vinay và email thông báo của chàng (nhận qua một mạng khác):

http://www.hpl.hp.com/personal/Vinay_Deolalikar/

——————
Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highly welcomed.

The paper is about 100 pages, and looks serious (but being a decade away from last thinking about complexity, I am unable to give any more useful evaluation than that). I’ll refrain from posting the paper itself.

Deciding P ≠ NP is a Millennium Prize Problem and I don’t think I’d get much argument to say it is the biggest open problem in computing science.

Update: I see someone else has uploaded the paper. I should point out that in the email thread I got, Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.”

Posted in Khoa hoc | 11 phản hồi »

Sao laị tròn ? (nhân ngày Mother’s day)

Tháng Năm 9, 2010

Hàng ngày, ta gặp rất nhiều vật thể có dạng tròn. Phần lớn các hình tròn đếu rất dễ thương, hấp dẫn, chẳng hạn

(1) Hạt sương ban mai.

(2) Hạt ngọc trai.

(3) Bóng.

Chúng dễ thương vì chúng đối xứng, tròn trĩnh, mang lại cảm giác đáng tin cậy, xinh xắn và vui nhộn.

Nhưng, sao lại tròn ? Sao không là hình tứ phương hay hình chóp. Cái này có thể giải thích theo nhiều phong cách

(phong cách) Dân gian: Trời sinh ra thế.

(phong cách) Triết gia/nhà thơ: Hình tròn biểu hiện sự hoàn thiện, toàn thiện toàn mỹ.

(phong cách) Kinh Dịch/Kim Dung: Trong tròn có vuông, trong vuông có tròn.

(phong cách) Anh Tạ Biên Cương: Bóng không tròn đá thế nào được ? Thử đánh đầu quả bóng hình chóp xem, biết nhau ngay…

Còn các nhà khoa học nói gì ?

Phong cách của các nhà khoa học, nói chung, là gần với văn học dân gian, tức là “Trời sinh ra thế”, nhưng với
ngôn ngữ hiện đại hơn: “Đó là qui luật của tự nhiên !”

Về phương diện toán học, nhiều qui luật tự nhiên được giải thích với ngôn ngữ tối ưu hóa. Nói một cách rất nôm na,
vật chất ở một trạng thái nhất định là vì ở trạng thái đó một đại lượng nào đó đạt giá trị tối ưu. (Bạn có thể xem một ví dụ rất hay trong bài Cơ học lượng tử của anh Đàm Thanh Sơn. )

Vậy hình tròn, hay hình cầu nói chung, tối ưu cái gì ? Điều này chắc nhiều bạn đã biết:

Định lý (Isoperimetric theorem; IT): Trong các hình có cùng thể tích (trong không gian R^d), hình cầu có diện tích mặt nhỏ nhất.

Chẳng hạn hình tròn là hình có chu vi nhỏ nhất trong các hình phẳng có cùng diện tích. Diện tích mặt nhỏ nhất sẽ tối giản áp suất lên vật thể (chẳng hạn trong trường hợp hạt sương).

IT có nhiều cách chứng minh. Tôi sẽ giới thiệu cách chứng minh dùng định lý Brunn-Minkowski. Định lý B-M là một trong nhưng định lý cơ bản nhất trong hình học giải tích, và bản thân nó cũng có nhiều cách chứng minh tuyệt vời.

Để trình bày định lý BM, ta cần một định nghĩa. Định nghĩa này là tổng Mincowsky, được dùng rất nhiều trong hình học giảt tỉch, và gần đây, trong số học tổ hợp. Tổng này cho phép ta cộng hai tập hợp:

A+B := \{ a+b| a \in A, b \in B \} .

Ví dụ:

\{1,3, 6\} + \{0,1\}= \{1,2, 3,4, 6,7 \}; [0,1]+ [0,1]= [0,2]; [0,1]^2 +[0,2]^2 =[0,3]^2 .

Định lý Brunn-Minkowski:

vol (A+B)^{1/d} \ge vol (A)^{1/d} + vol (B) ^{1/d} .

vol A ký hiệu thể tích của A. Trong bài này, ta giả sử các tập hợp là compact (nếu bạn không biết định nghĩa thì cũng không cần quan tâm nhiều, nó là giả sử mang tính kỹ thuật). Định lý BM được chứng minh bởi Brunn (1887) cho một trường hợp đặc biệt năm 1887, và Mincowsky tổng quát năm 1896. Các nghiên cứu liên quan đến định lý này được phát triển liên tục trong vòng hơn 100 năm qua, cho thấy sự quan trọng của nó. Bạn có thể tham khảo một bài báo rất hay của R. Gardner: THE BRUNN-MINKOWSKI INEQUALITY, viết năm 2001.

Để hiểu và chứng minh IT, trước hết ta cần thấy mối liên quan giữa diện tích mặt và thể tích của một vật thể. Cho đơn giản, bạn
tưởng tượng củ khoai. Hồi bé, mẹ dạy gọt khoai, thường bảo tôi phải cạo vỏ hơn là gọt. Củ khoai bé tí, nếu gọt sâu vào, thì chẳng còn gì. (Đây là chuyện của những năm 70-80 rồi;nếu bạn còn trẻ, có thể không biết đâu.)

Gọi củ khoai sau khi gọt vỏ là A. Nếu độ dày vỏ khoai là r, thì lượng vỏ khoai gọt ra xấp xỉ r \times area (\partial A), trong đó area (\partial A) là diện tích bề mặt của khoai. Củ khoai trước khi gọt vỏ có thể biểu diễn bằng A + S(r), trong do S(r) là hình cầu bán kính r. Dùng đẳng thức đáng nhớ: Khoai vào nồi = Khoai lúc đầu- Vỏ khoai và cho r tiến đến 0, ta có công thức quan trọng sau:

area (\partial A) = \lim _{r \rightarrow 0} \frac{vol (A+ S(r)) - vol (A) }{r}.

Ta thử áp dụng công thức này cho chính hình cầu xem sao. Như mọi người đều biết, thể tích hình cầu tỷ lệ thuận với bán kính mũ d, S(r) = C(d) r^d, trong do C(d) là hằng số phụ thuộc vào d (bạn có thể tính hằng số này một cách cụ thể, chẳng hạn C(2)= \pi, nhưng giá trị thật của nó không có vai trò quan trọng ở đây). Theo công thức trên, ta có:

area (\partial S(r_0))= \lim _{r \rightarrow 0} C_d \frac{ (r_0+r )^d - r_0^d}{r}= C_d d r_0^{d-1}.

Nếu S(r_0) có thể tích C_d r_0^d= 1, thì diện tích mặt của nó là: C_d d r_0^{d-1}= \frac{d}{r_0} .

Bây giờ ta có thể chứng minh IT. Lấy một tập A thể tích vol (A)=1, ta cần chứng minh area (\partial A) \ge \frac{d}{r_0}.

Theo định lý BM và khai triển mũ (x+y)^d= x^d + d x^{d-1} y +..., ta có

area( \partial A) = \lim _{r \rightarrow 0} \frac{vol (A+ S(r) ) - vol (A) }{r}

\ge \lim_{r\rightarrow 0} \frac{d vol (A)^{1-1/d} vol S(r)^{1/d} }{r}.

Vì vol A=1 và \frac{ vol (S(r)) ^{1/d} }{r} không phụ thuộc vào r,
\frac{d vol (A)^{1-1/d} vol S(r)^{1/d} }{r} là một hằng số. Nếu ta lấy r=r_0 nó trở thành \frac{d}{r_0} . QED.

Trong phần còn lại của blog, tôi đưa ra một chứng minh rất gọn của đjinh lý (theo Hadwiger and Ohmann), gần như chỉ dùng kiến thức toán cấp ba.

(1) Bước thứ nhất là một ý tưởng rất cơ bản trong giải tích. Nếu ta muốn chứng minh a \ge b, ta có thể tìm hai dãy a_n, b_n sao cho a_n \ge b_n và a_n \rightarrow a, b_n \rightarrow b_n.
Lợi thế ở đây là các số a_n, b_n do ta tự chọn, nên ta có thể có thêm những tính chất đẹp mà a và b không có.

Trong trường hợp A là một tập bẩt kỳ, ta có thể xấp xí nó bắng union của một dãy các hình hộp (có cạnh song song với các trục tọa độ) không giao nhau (như tổng Rieman khi tính tích phân), A_1 \cup A_2 \cup...\cup A_n \cup.... Nếu a là thể tích của A, thì a_n là thể tich của A_1 \cup ...\cup A_n. Đây cũng là một ý tưởng rất cơ bản khác trong giải tích.

Bây giờ ta sẽ chỉ cần chứnh minh định lý BM trong trường hợp cả A và B là (dísjoint) union của một số hữu hạn các hình hộp. Gọi tổng số các hình hộp trong cả A và b là m. Ta qui nạp theo m.

(2) Trường hợp đầu tiên là m=2 (A là một hình hộp và B là một hình hộp). Gọi x_i, i=1,...,d là độ dài các cạnh của A và y_i, i=1,...,d là độ dài các cạnh của B; A+B sẽ là hình hộp có cạnh dài x_i +y_i. Định lý BM, trong trường hợp này, tương đương với bất đẳng thức

1 \ge (\frac{x_1}{x_1+y_1} \dots \frac{x_d}{x_d+y_d} )^{1/d} + (\frac{y_1}{x_1+y_1} \dots \frac{y_d}{x_d+y_d} )^{1/d} , và là một hệ quả của bất đẳng thức tổng-tích (AG inequality).

(3) Giả sủ ta đã giải quyết tất cả m \le k. Trong trường hợp k+1 \ge 3, ta có thể giả sứ A có \ge 2
hình hộp. Để ý rằng nội dung bài toán không thay đổi nếu ta tịnh tiến A và B. Ta sẽ tịnh tiến A sao cho có một mặt phẳng tọa độ H (chẳng hạn z_d=0) chứa ít nhất một hình hộp (của A) ở phía trên và it nhất một hình hộp phía dưới nó. Gọi hai phần này là A_{+} và A_{-}. Để ý rằng số hình hộp trong mỗi tập này lớn hơn 0 nhưng Ít hơn trong A. Đây là cơ sở để ta áp dụng phép qui nạp.

(4) Gọi B_{+} và B_{-} là phần của B ở trên và dưới H. Ta có

vol (A+B) \ge vol (A_{+} + B_{+}) + vol (A_{-} + B_{-} ).

Theo giả thiết qui nạp,

vol (A_{+} + B_{+}) \ge (vol (A_{+})^{1/d} + vol (B_{+})^{1/d})^d , do đó

vol (A+B) \ge (vol (A_{+})^{1/d} + vol (B_{+})^{1/d})^d + (vol (A_{-})^{1/d} + vol (B_{-})^{1/d})^d . (*)

(5) Vế bên phải xem ra khó nhai. Nhưng ta còn một vũ khí chưa dùng tới, đó là ta có thể tịnh tiến B để thay đổi tỷ lệ vol (B_{-})/ vol (B_{+}) . Ta sẽ chọn một phép tịnh tiến sao cho

vol (B_{-})/ vol (B_{+}) = vol (A_{-}) / vol (A_{+} ) := \alpha .

Khi đó vế phải của (*) trở thành

(vol (A_{+})^{1/d} + vol (B_{+})^{1/d})^d (1+ \alpha) = ( vol (A)^{1/d} + vol (B)^{1/d}) ^d. \,\,\, QED.

Bài tập: Khi nào đẳng thức xảy ra trong định lý BM ?

Posted in Khoa hoc | 17 phản hồi »

SỐ ĐỎ

Tháng Ba 17, 2010

SỐ ĐỎ

Dân ta thích đỏ đen. Không biết có tự bao giờ, nhưng số đề đang là trò “đỏ đen” được nhiều người ưu ái nhất, chơi nhiều nhất. Đêm nằm mơ số đề đẹp, sáng ra chợ nghe bàn, trưa đi đặt số, chiều đợi radio nghe xổ số… đề.

Luật chơi đề đại loại như sau: Sáng bạn đặt một số tiền, nói đơn giản là 1$ cho chủ đề, vào một số từ 00 đến 99. Mục đích của người chơi đề là làm sao số này trùng vào 2 chữ số cuối cùng của giải sổ xồ do nhà nước phát hành trong ngày đó. Khi xổ số quay, hai chữ số này được xác định (gọi là “đề về”), chủ đề xo số và thanh toán tiền nong. Nếu sổ của bạn trùng, bạn sẽ được 70$ (tức 70 lần số tiền đầu tư). Nếu không trúng, bạn sẽ mất 1$ đặt cược lúc đầu.

“Ai ơi yêu lấy số đề
Khi đi một chỉ, khi về bảy cây !”

Đánh đề thông dụng có lẻ bởi nó đơn giản dễ hiểu, và khả năng trúng xố, trong mắt người chơi là tương đối cao (1/100). Khả năng này cao hơn nhiều so với các giải xổ số chính thức của nhà nước, và có tác dụng tâm lý rất mạnh. Những người chơi đề lâu ngày, thường ai cũng thắng, hoặc quen biết những người đã thắng một vài lần. Tâm lý chơi đề để có một cơ hội “đổi đời” rất phổ biến, nhất là đối với những người nghèo. Chuyện về “nuôi đề”, nằm mơ thấy “đề về”, đi thăm mộ thấy số đề, vv là những chuyện nghe thấy hàng ngày.

Vậy thực chất ĐÁnh Đề có phải là một trò chơi đem lại nhiều hy vọng ?

Nhìn về khía cạnh toán học mà nói, thì luật chơi đề rất thiệt cho ngươi chơi, vì kỳ vọng của nó là một số âm to đùng.

Giả sử ông A chơi đề ngày một lần, mỗi lần đều đặn 1 triệu đồng. Như vậy sau 6 năm,
tính là 2000 ngày cho chẳn, ông A bỏ ra 2 tỷ. Mổi lần chơi, xác xuất trúng là 1%.
Như thế, trung bình ông A sẽ trúng 20 lần. Mỗi lần được 70 triệu, 20 lần là 1,4 tỷ, như vậy, trung bình ông A lỗ 600 triệu.

Tất nhiên, ông A sẽ nói “ờ thì trung bình là vậy, nhưng nhỡ tôi may thi sao ?”.

Xác suất may của ông A hoàn toàn có thể tính được. Nó được biểu diễn qua một định lý rất nổi tiếng và cơ bán:

Định lý giới hạn trung tâm:

x_1, \dots, x_n là các biến độc lập ngẫu nhiên, có cùng
kỳ vọng là E và phương sai là V=\sigma^2. Khi đó nếu n tiến đến vô cùng

Pr (\frac{\sum_{i=1}^n x_i - nE} { \sqrt n \sigma } \ge x )\rightarrow \Phi(x) .

Ở đây \Phi(x) là hàm phân bố Gauss

\Phi(x)= \frac{1}{\sqrt 2 \pi} \int_x^{\infty} e^{-t^2/2} dt.

Điều quan trọng ở đây là hàm e^{-t^2/2} tiến đến 0 rất nhanh với t, do đó \Phi(x) cũng tiến đến 0 rất nhanh với x. Chẳng hạn
\Phi(1) \le .16, \Phi(2) \le .03, \Phi (3) \le .003. Định lý trên có thể viết lại dưới dạng

Pr (\sum_{i=1}^n x_i \ge nE + x \sqrt n \sigma) \approx \Phi (x) .

Quay trở lại với ông A. Muốn ứng dụng định lý trên, ta cho x_i là số tiền ông A thu hoạch trong lần chơi thứ i. x_i có phân bố như sau: Pr (x_i =-1) = .99 (thua) và Pr (x_i =69) =.01 (thắng). Kỳ vọng của x_i là -.3 (triệu đồng) va phương sai xấp xi 49=7^2. Nếu ông A không lỗ sau 2000 lần chơi, thì \sum_{i=1}^n x_i \ge 0, tức ta phải lấy

x \ge \frac{n|E|} { \sqrt n \sigma } \approx \frac{ 600} {\sqrt {2000} 7} \approx 1.9.

Vậy xác suất để ông A “may” (không lổ vốn) là độ \Phi (1.9) . Xác suât này cỡ ba phần trăm. Nói một cách nôm na, nếu có 100 người chơi như ông, trung bình chỉ có 3 người không lỗ.
(Tất nhiên bạn được nghe ba ông này tuyên truyền về “tài năng” của mình bao nhiêu lần lại là chuyện khác. Đây là khía cạnh tâm lý của trò chơi.)

Định lý giới hạn trung tâm phản ánh một hiện tượng quan trọng và có tính ứng dụng cao:

Hiện tượng (Large deviation): Một biến ngẩu nhiên được
xác định bởi nhiều biến ngẩu nhiên độc lập thường lấy một giá trị gần với kỳ vọng của nó.

Trong trường hợp vừa rồi, biến này là S:= x_1 + ...+ x_n, tổng số thu hoạch của ông A.
Bạn có thể dùng định lý giới hạn trung tâm để so sánh sồ đề với rullet, một trò chơi thông dụng ở
casino. Ở cả hai trò, kỳ vọng của người chơi đều âm, nhưng kỳ vọng của rullet là một số âm nhỏ.

The Central limit theorem was first established by de Moivre, năm 1733, and has been extended and strengthened by a series of famous mathematicians, including  Laplace, Lyapunov,  Lindeberg, Kolmogorov etc (see this and this). The phrase “Central limit theorem” was  first used by Polya around 1920. Almost 300 hundred years after its discovery, the CLT still has been used daily in various fields of mathematics, and research motivated by CLT and the Large Deviation Phenomenon plays a key role in probability, statistics, high dimensional geometry, mathematical physics, combinatorics and theoretical computer science. 

Vĩ thanh: Bạn Luciano (bên Thích Học Toán) băn khoăn là dân chơi đề thực sự thường không đánh như ông A.
Đúng vậy, ví dụ của ông A là một ví dụ đơn giản nhất (to sell the point). Một dân đề thực thụ sẽ chơi phức tạp hơn, chẳng hạn:

Ông B (more advanced player) sẽ chơi như sau:

(1) Số 23 trong 5 ngày liền, nếu không thắng, chuyển sang con 35.
(2) Nếu 35 trong năm ngày không về, nhịn tắm một tuần, chuyển sang con 12 và chơi lại con 23.
(3) Nếu một tuần sau đề vẫn không đậu, tắm và đi lễ chùa, nghỉ hai ngày.
(4) Chơi tiếp con 12 và 89, tránh gặp phụ nữ buổi sáng, vv

Hiện tượng Large deviation ke tren sẽ chỉ ra cho chúng ta là, bất kể ông B thay đối thế nào, với xác suất gần bằng một, sau một thơi gian dài, ông ta sẽ thu hoạch y hệt như ông A, tức là lỗ khoảng 30% vốn.

This is one of the key points of martingale theory.

Posted in Khoa hoc | 27 phản hồi »

Hello world!

Tháng Hai 27, 2010

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!

Posted in Khoa hoc | 2 phản hồi »

Follow

Get every new post delivered to your Inbox.

Join 52 other followers