Skip to content

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

From → Khoa hoc

11 phản hồi
  1. Nkd permalink

    Em thấy nhà toán học có hơn gì máy tính đâu. Đa số vấn đề các ông ấy dễ dàng kiếm tra đúng hay sai, khi có người khác giải rồi. Nhưng nếu để tự các ông ấy làm thì chả biết đến bao giờ mới xong, hoặc có thể không bao giờ xong.

    Nếu giải xong cũng chỉ là may mắn ngẫu nhiên, trong khi anh không bắt máy tính quét hết các trường hợp mà chỉ duyệt một số trường hợp nào đó thì cũng có thể may mắn ra được đáp số.

    Có thể coi tất cả các nhà toán học trên trái đất thuộc về 1 hệ thống, tương tự như 1 cái super computer thôi. Ta không thể biết chắc khi nào thì họ giải được cái gì.

    Thế nên đãi ngộ họ giống như những cái mini computer thôi. Cho vào 1 cái phòng có điều hòa!!!

    • Các nhà toán học đúng là làm được cái gì là gập may thật. Có điều có những bác gập may suốt ngày….

      • nclam permalink

        Em đọc blog của anh Van lâu rồi mà chưa dám bình “loạn” gì, hôm nay vào lại đọc được câu trả lời này của anh thấy hay quá. Cái chữ “may” của anh lợi hại thật, em hiểu thì nó chính xác là cái mà một con robot đang muốn có phải không anh, để nhiều khi chơi cờ còn biết được cái sự sung sướng của “gặp may” chứ không thì cứ hì hục vét cạn hết các trường hợp trong mỗi nước đi thì vất quá🙂

  2. Mèo permalink

    Nkd đúng là có lối tư duy rất giống cái máy tính :)).

  3. Nkd permalink

    Đấy là em đùa thôi.😀

    Nhưng các bài toán cũng có độ khó/độ phức tạp. Các bài toán có độ phức tạp thấp, trung bình, hoặc tương đối cao thì máy tính bình thường cũng giải được nhanh. Trong khi những bài có độ phức tạp rất cao thì không đảm bảo giải được mà nếu cứ cố bắt máy chạy thì việc giải được cũng chỉ là ngẫu nhiên.

    Em nghĩ là toán học hiện nay cũng có nhiều bài có độ phức tạp hơi cao, một số bác giải bay bay, trong khi đa số các bác khác không giải được. Có thể coi các bác này là các Super-power computer, đa số các bác còn lại là High, Medium & Low-power computer. Nhưng với độ phức tạp cao hẳn lên thì em nghĩ ngay các bác Super-power này giải được hay không cũng là ngẫu nhiêu.

    Thế nên ta không thể biết chắc bác nào sẽ giải quyết được cái great problem nào, và vào khi nào.

  4. TVP permalink

    Bao giờ bác Cook kiểm chứng xong nó thì anh pót một bài thông báo nhé. Em cũng rất hứng thú với vấn đề này. Khoa học máy tính quả thật rất hay và thú vị nhưng nước mình rất kém về cái món này.

  5. Đây không phải là lần đầu tiên người ta “tuyên bố” giải được bài toán P vs NP.
    Anh Vinay kết hợp vật lý thống kê, toán và khoa học máy tính trong bài báo của mình, và được một người như bác Cook đọc qua và nhận xét là ” nghiêm trong” thì cũng nghiêm trọng thật đấy.

    BTW, 2 trong số hơn chục học trò của bác Cook là người Việt, hy vọng trong tương lai gần chúng ta sẽ thấy Vina ( Việt Nam) giải bài toán này chứ không phải là Vinay😛

  6. Anh ấy đúng là nhân vật trong tuần, vì sau 1 tuần, đến nay, thế giới biết là chứng minh của anh ấy sai trầm trọng.

  7. KHG permalink

    Terry Tao posted very clear and definitive opinions on the proof:

    “Ultimately, it seems that what Deolalikar has really proven is not that P != NP, but rather that pp != ppp (for which we have a simple half-page proof)…”

    and then this wonderful summary:

    “To give a (somewhat artificial) analogy: as I see it now, the paper is like a lengthy blueprint for a revolutionary new car, that somehow combines a high-tech engine with an advanced fuel injection system to get 200 miles to the gallon.

    The FO(LFP) objections are like a discovery of serious wiring faults in the engine, but the inventor then claims that one can easily fix this by replacing the engine with another, slightly less sophisticated engine.

    The XORSAT and solution space objections are like a discovery that, according to the blueprints, the car would run just as well if the gasoline fuel was replaced with ordinary tap water. As far as I can tell, the response to this seems to be equivalent to “That objection is invalid – everyone knows that cars can’t run on water.”

    The pp/ppp objection is like a discovery that the fuel is in fact being sent to a completely different component of the car than the engine.”

  8. Chắc anh Vinay ra đi thật rồi, dù sao anh cũng dũng cảm.

    “Anh nằm xuống
    Sau một lần
    Đã đến đây…”

    Blog pót của bac Lipton có nhiều comment rât vui về vụ này.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: