P ≠ NP? It's bad news for the power of computing - Page 2

socnau · #11 (**permalink**) 08-21-2010

	Trích:	kitte
	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.

Theo mình hiểu nếu chỉ xét theo tiêu chí của viện Clay thì với bài toán này chỉ cần trả lời liệu P có bằng NP hay không. Vì vậy nếu kết quả là P=NP thì trong lời giải không nhất thiết phải xây dựng được một thuật toán cụ thể mà chỉ cần chứng minh tồn tại một thuật toán polynomial time giải được một NP-complete. Trong toán học chứng minh tồn tại không nhất thiết phải chỉ rõ nó hình dạng cụ thể ra sao. Tất nhiên nếu xây dựng được thì tốt hơn, còn không được thì ngoài những thu hoạch như bác Nấm nói thì kết quả thôi cũng là một bước tiến lớn nếu so sánh với tình hình hiện nay

. Không tiến được bước lớn thì tiến bước nhỏ cũng đỡ mà, có thể từ lời giải về sự tồn tại hay cho dù là P khác NP ta tìm ra những phương pháp phân loại kĩ hơn các lớp bài toán chẳng hạn.

~~BerkBear~~ · #12 (**permalink**) 08-21-2010

Tôi lại đánh giá khác.

	Trích:
	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.

Đây là một kết quả rất quan trọng để đánh dấu thời điểm từ này không còn ai phải mất thời gian để đi tìm cách chứng minh/xây dựng thuật toán để quy NP về P, tiết kiệm vô cùng nhiều xương máu cho các nhà toán học, không biết bao nhiêu đề tài NSF. Vậy đáng tiền chứ, đúng không?