Đúng là tin động trời, không hiểu bác Nờ-Pê-Khó sẽ đánh giá vụ này thế nào nhỉ?
[Only registered and activated users can see links. ]
Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper titled simply "P ≠ NP".
This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute's seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.
The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P.
If the answer to a task can be checked quickly then it is in class NP.
So if P = NP, every problem that can be checked quickly can also be completed quickly. That outcome would have huge repercussions for internet security, where the difficulty of factorising very large numbers is the primary means by which our data is kept safe from hackers.
Ingenious argument
But Deolalikar says that's not the way it is. His argument revolves around a particular task, the Boolean satisfiability problem, which asks whether a collection of logical statements can all be simultaneously true or whether they contradict each other. This is known to be an NP problem.
Deolalikar claims to have shown that there is no program which can complete it quickly from scratch, and that it is therefore not a P problem. His argument involves the ingenious use of statistical physics, as he uses a mathematical structure that follows many of the same rules as a random physical system.
If the result stands, it would prove that the two classes P and NP are not identical, and impose severe limits on what computers can accomplish – implying that many tasks may be fundamentally, irreducibly complex.
For some problems – including factorisation – the result does not clearly say whether they can be solved quickly. But a huge sub-class of problems called "NP-complete" would be doomed. A famous example is the travelling salesman problem – finding the shortest route between a set of cities. Such problems can be checked quickly, but if P ≠ NP then there is no computer program that can complete them quickly from scratch.
Complexity theorists have given a favourable reception to Deolalikar's draft paper, but when the final version is released in a week's time the process of checking it will intensify.
__________________ Stay hungry, never foolish - Hãy cứ khát khao, nhưng chớ dại khờ
Ðề: P ≠ NP? It's bad news for the power of computing
[Only registered and activated users can see links. ]
Một số thread của PhDvn về P và NP
Trích:
Vấn đề P khác NP (P # NP)
Với quyển từ điển trong tay, liệu bạn thấy tra nghĩa của từ "thằn lắn" dễ hơn, hay tìm một từ phổ thông để diễn tả “loài bò sát có bốn chân, da có vảy ánh kim, thường ở bờ bụi” dễ hơn? Câu trả lời hầu như chắc chắn là tra nghĩa thì dễ hơn tìm từ.
Những các nhà toán học lại không chắc chắn như thế. Nhà toán học Canada Stephen Cook là người đầu tiên, vào năm 1971, đặt ra câu hỏi này một cách “toán học”. Sử dụng ngôn ngữ lôgic của tin học, ông đã định nghĩa một cách chính xác tập hợp những vấn đề mà người ta thẩm tra kết quả dễ hơn (gọi là tập hợp P), và tập hợp những vấn đề mà người ta dễ tìm ra hơn (gọi là tập hợp NP). Liệu hai tập hợp này có trùng nhau không? Các nhà lôgic học khẳng định P # NP. Như mọi người, họ tin rằng có những vấn đề rất khó tìm ra lời giải, nhưng lại dễ thẩm tra kết quả. Nó giống như việc tìm ra số chia của 13717421 là việc rất phức tạp, nhưng rất dễ kiểm tra rằng 3607 x 3808 = 13717421. Đó chính là nền tảng của phần lớn các loại mật mã: rất khó giải mã, nhưng lại dễ kiểm tra mã có đúng không. Tuy nhiên, cũng lại chưa có ai chứng minh được điều đó.
"Nếu P=NP, mọi giả thuyết của chúng ta đến nay là sai" – Stephen Cook báo trước. "Một mặt, điều này sẽ giải quyết được rất nhiều vấn đề tin học ứng dụng trong công nghiệp; nhưng mặt khác lại sẽ phá hủy sự bảo mật của toàn bộ các giao dịch tài chính thực hiện qua Internet". Mọi ngân hàng đều hoảng sợ trước vấn đề lôgic nhỏ bé và cơ bản này!
N = NP ?
Hi vọng những ai cùng chuyên môn có thể cho mọi người một số insight về bài toán này và impact của công trình kia.
Ðề: P ≠ NP? It's bad news for the power of computing
Theo như bác Nờ Pê Khó nói ở [Only registered and activated users can see links. ] thì chứng minh ấy là sai:
Trích:
...chứng minh của Deolalikar 99 phần trăm là sai. Bạn xem các phát triển về chủ đề này ở [Only registered and activated users can see links. ].
Trích:
An update on the P not equal to NP proof
Timothy Gowers, Gil Kalai, Ken Regan, Terence Tao, and Suresh Venkatasubramanian are some of the top people who are trying to unravel what is up with the claimed proof that P NP. I will call them the Group today—I hope that is okay. It’s a pretty powerful collection of top theorists, all who want to help us understand what Vinay Deolalikar has done.
Today I will talk about the Group’s effort to help all of us understand the claimed proof of Vinay Deolalikar. Of course many others are working towards the same goal, but the Group is one that I have been interacting with the most.
This came about when some of the Group suggested that we start to be more organized and use wiki technology to handle the serious public discussion needed to understand the proof. I completely agree. One hold-up is we are currently unsure what Vinay wishes to happen. We are in direct communication with him, but he has not yet made it clear what he wishes.
The Group has decided for now to let things go along in the current ad hoc fashion. If and when Vinay wants help, we are prepared to help in any way that we can. For now we will follow Clint Eastwood who once said:
“Don’t just do something, stand there.”
__________________ Stay hungry, never foolish - Hãy cứ khát khao, nhưng chớ dại khờ
Ðề: P ≠ NP? It's bad news for the power of computing
Nhìn vào mấy suggestions các bác "to đầu" thì đúng là chứng minh của Deolalikar rất khó trụ vững:
Trích:
I suggest this to Vinay as a possible way to give us some insight into his ideas, and perhaps allow him to simplify some technical issues. If this is too much of a detour, I understand. But it could be a useful “warm-up” exercise. We see this type of idea all the time in new proofs. If you can show that a new proof can solve weaker questions, even questions that are known, that can be very confidence building.
__________________ Stay hungry, never foolish - Hãy cứ khát khao, nhưng chớ dại khờ
Ðề: P ≠ NP? It's bad news for the power of computing
Có vẻ như mọi chuyện đã [Only registered and activated users can see links. ]:
Trích:
I think there are several levels to the basic question “Is the proof correct?”:
Does Deolalikar’s proof, after only minor changes, give a proof that P [Only registered and activated users can see links. ] NP?
Does Deolalikar’s proof, after major changes, give a proof that P [Only registered and activated users can see links. ] NP?
Does the general proof strategy of Deolalikar (exploiting independence properties in random [Only registered and activated users can see links. ]-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?
After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the [Only registered and activated users can see links. ]), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added.” But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days.)
__________________ Stay hungry, never foolish - Hãy cứ khát khao, nhưng chớ dại khờ
Ðề: P ≠ NP? It's bad news for the power of computing
Không biết quantum computing có thể giải dc các bài tóan NP không nhỉ, theo bài này thì có thể không: [Only registered and activated users can see links. ]
. Nếu như có 1 bác PhD Việt Nam nào sáng tạo ra một mô hình tính tóan mới khác Turing machine thì may ra mới có đột phá
Ðề: P ≠ NP? It's bad news for the power of computing
Thực ra bản thân tớ thấy chứng minh P # NP chẳng mang lại lợi ích gì nhiều, ngoài số tiền thưởng cùng với uy tín, danh dự giành cho người đưa ra lời chứng minh.
Hiện tại, có lẽ hầu hết dân làm về theory CS đều tin và "cảm" thấy rằng P # NP. Thế giới của tính toán và nhất là trong bảo mật đều dựa trên assumption là P # NP, vì thế có đưa ra lời chứng minh cho nó cũng chả có tác dụng gì nhiều, có chăng chỉ như là một lời giải thích làm vấn đề rõ ràng hơn thôi.
Nguợc lại, nếu có ai đưa được chứng minh P = NP thì đây chắc chắn là một trong những phát minh vĩ đại nhất trong lịch sử ngành KHMT, vì trong lời chứng minh đó sẽ có cách chuyển đổi từ NP sang P và cách biến đổi này sẽ vô cùng hữu ích trong thực tế.
Mọi người tham khảo thêm ý kiến từ [Only registered and activated users can see links. ].
Ðề: P ≠ NP? It's bad news for the power of computing
Các bài toán millenium prize problems và Fields medal problems nó mang hai ý nghĩa:
+ Trực tiếp: Độ khó -> tempting, glory, fame...v.v
+ Gián tiếp: hầu như không thể dùng các công cụ có sẵn để giải. Một khi giải được các bài toán này đều nảy sinh ra những công cụ rất mạnh để giải quyết các bài toán khác, hoặc thống nhất được nhiều lĩnh vực tưởng chừng không có quan hệ với nhau, hoặc mở ra một ngành, hướng hoàn toàn mới (Fermat last's theorem, Fundamental lemma, Poincare's conjecture).
Vì thế bài toán này khả năng vẫn có ý nghĩa, về cái đóng góp 'gián tiếp'.
Ví dụ cái fundamental lemma đó, bao năm người ta biết là nó đúng (trực giác người làm toán), và đã làm bao bài toán dựa trên giả định đó. Cái ý nghĩa chứng minh được nó không chỉ là làm cho người khác yên tâm mà nó còn liên hệ được nhiều lĩnh vực lại với nhau và tạo một mô hình cái cầu mới (techniques) để người sau có thể bắc qua nhiều lĩnh vực khác nữa.
Ðề: P ≠ NP? It's bad news for the power of computing
Mỗi một ngành khoa học, hay thậm chí các nhóm ngành hẹp trong cũng một ngành, thường có các mindset rất khác nhau. Như ngành CS người ta thường coi trọng các ứng dụng thực tế của các nghiên cứu, phát minh. Hẹp hơn nữa thì như những người làm về database chẳng hạn thì họ lại càng coi trọng tính thực tế của các công trình. Ví dụ như khi bạn trình bày về công trình của mình mà có những thuật toán rất đẹp đẽ về mặt toán học nhưng không có ứng dụng cụ thể cả thì sẽ chẳng có ai quan tâm cả. Giới academic còn như thế, những người ở industry còn thực dụng hơn nữa.
Theoretical CS gần với toán, sử dụng nhiều toàn hơn nhưng dù sao thì nó vẫn là ngành ứng dụng, người ta vẫn luôn quan tâm đến tính áp dụng của công trình, dù là mức độ cụ thể có thể nới lỏng hơn. Bạn nào học theoretical CS vào confirm hộ tớ cái.
Quay lại bài toán P vs NP. Tôi đã nói nếu ai chứng minh được P=NP thì sẽ là một phát minh vĩ đại, vì hiển nhiên trong cách chứng minh đó cần chỉ ra cách convert từ NP về P, và thuật toán để convert này sẽ làm thay đổi rất nhiều thứ trong ngành CS.
Còn ngược lại chứng minh P#NP thì hầu như chỉ giống như đưa ra một lời giải thích làm cho người khác yên tâm hơn vê một thứ mà mọi người vẫn luôn tin tưởng là đúng. Không có nó, cả thế giới của CS vẫn chuyển động như bình thường.
Cách bạn Menam đưa fundamental lemma ra so sánh tôi thấy hơi chung chung và xa vời so với trường hợp này.
P ≠ NP? It's bad news for the power of computing 
