Chào khách,
Câu "Tất cả đều dựa trên giả thuyết P khác NP" là trỏ đến các bài đã liên kết chứ không phải trỏ đến toàn bộ khoa học máy tính. Ý tôi nói là muốn chứng minh độ khó của cái gì đó thì thường ta dùng giả thiết P khác NP, ví dụ như chứng minh độ khó bẻ khóa của một hệ thống bảo mật, độ khó học của một bài học máy, độ khó xấp xỉ của một bài toán tối ưu. P có bằng NP hay không thì khoa học và công nghệ máy tính vẫn phát triển như vũ bão.
Ngoài ra, có một điểm hơi đặc biệt của lý thuyết máy tính là: cho dù giả thiết P khác NP là sai, thì các chứng minh độ khó dựa trên giả thiết (sai) này vẫn hữu dụng. Lý do là các chứng minh đều là các phép chuyển giản, nghĩa là các thuật toán chạy trong thời gian đa thức. Các thuật toán này vẫn hữu dụng dù P=NP. |