Ý tưởng rằng một số vấn đề tính toán trong toán học và khoa học máy tính có thể khó xảy ra không phải là điều ngạc nhiên. Trên thực tế, có cả một lớp vấn đề mà nó được coi là không thể giải được bằng toán học. Bên dưới danh mục này có một số vấn đề “dễ hơn” chưa được hiểu rõ – và chúng cũng có thể là bất khả thi.

David Jamarnik, Giáo sư Nghiên cứu Hoạt động tại Trường Quản lý MIT Sloan và Viện Dữ liệu, Hệ thống và Xã hội, tập trung sự chú ý của mình vào loại sau là các vấn đề ít được nghiên cứu hơn, phù hợp hơn với thế giới hàng ngày vì chúng liên quan đến Ngẫu nhiên—Một tính năng không thể thiếu của các hệ thống tự nhiên. Ông và các đồng nghiệp của mình đã phát triển một công cụ mạnh mẽ để phân tích những vấn đề này được gọi là thuộc tính khoảng cách chồng chéo (hay OGP). Gamarnik đã mô tả phương pháp luận mới trong một bài báo nghiên cứu gần đây trong Kỷ yếu của Viện Hàn lâm Khoa học Quốc gia.

P NP

50 năm trước, bài toán nổi tiếng nhất trong khoa học máy tính lý thuyết đã được hình thành. P ≠ NP hỏi, nếu có vấn đề liên quan đến tập dữ liệu khổng lồ mà câu trả lời có thể được xác minh tương đối nhanh chóng, nhưng điều này – ngay cả khi làm việc trên máy tính nhanh nhất hiện có – sẽ mất nhiều thời gian vô lý để giải quyết.

Phỏng đoán P ≠ NP vẫn chưa được chứng minh, nhưng hầu hết các nhà khoa học máy tính tin rằng nhiều vấn đề quen thuộc – bao gồm, ví dụ, bài toán người bán hàng lưu động – thuộc loại khó tưởng tượng này. Thử thách trong ví dụ về người bán là tìm ra con đường ngắn nhất, về khoảng cách hoặc thời gian, qua N thành phố khác nhau. Nhiệm vụ được quản lý dễ dàng khi N = 4, vì chỉ có sáu con đường khả thi để xem xét. Nhưng trong 30 thành phố, có hơn 10³⁰ những cách có thể và các con số tăng lên theo cấp số nhân từ đó. Khó khăn lớn nhất nằm ở việc thiết kế một tập tin thuật toán Nó giải quyết vấn đề một cách nhanh chóng trong mọi trường hợp, với mọi giá trị nguyên của N., các nhà khoa học máy tính tin tưởng, dựa trên lý thuyết độ phức tạp tính toán, rằng không có thuật toán nào như vậy, xác nhận rằng P ≠ NP.

Có rất nhiều ví dụ khác về những vấn đề khó chữa như vậy. Ví dụ, giả sử bạn có một bảng số khổng lồ với hàng nghìn hàng và hàng nghìn cột. Bạn có thể tìm thấy, trong số tất cả các kết hợp có thể, sự sắp xếp chính xác của mười hàng và 10 cột sao cho hàng trăm mục nhập của chúng có tổng số có thể đạt được cao nhất không? Jamarnik nói: “Chúng tôi gọi đó là các nhiệm vụ tối ưu hóa, bởi vì bạn luôn cố gắng tìm ra điểm lớn nhất hoặc tốt nhất – tổng các con số lớn nhất, tuyến đường tốt nhất qua các thành phố, v.v.”.

Từ lâu, các nhà khoa học máy tính đã nhận ra rằng bạn không thể tạo ra một thuật toán nhanh mà trong mọi trường hợp, có thể giải quyết vấn đề một cách hiệu quả như câu chuyện của người bán hàng lưu động. Jamarnik lưu ý: “Rất có thể một điều như vậy sẽ không thể xảy ra vì những lý do đã hiểu rõ. “Nhưng trong cuộc sống thực, bản chất không tạo ra vấn đề từ góc độ thù địch. Nó không cố gắng làm bạn thất vọng với một vấn đề được lựa chọn tỉ mỉ, khó khăn nhất mà bạn có thể tưởng tượng được.” Trên thực tế, mọi người thường gặp phải các vấn đề trong những hoàn cảnh ngẫu nhiên hơn và ít được quản lý hơn, và đây là những vấn đề mà Đối tác Chính phủ Mở hướng tới giải quyết.

Đỉnh núi và thung lũng

Để hiểu tất cả về Đối tác Chính phủ Mở, có thể hữu ích trước tiên là xem ý tưởng bắt nguồn như thế nào. Từ những năm 1970, các nhà vật lý đã nghiên cứu thủy tinh spin – vật liệu có đặc tính của cả chất lỏng và chất rắn có các hành vi từ tính bất thường. Nghiên cứu về kính spin đã tạo ra một lý thuyết chung về các hệ thống phức tạp liên quan đến các vấn đề trong vật lý, toán học, khoa học máy tính, khoa học vật liệu và các lĩnh vực khác. (Công trình này đã giành cho Giorgio Baresi giải Nobel Vật lý năm 2021.)

Một vấn đề khó hiểu mà các nhà vật lý phải đối mặt là cố gắng dự đoán trạng thái năng lượng, đặc biệt là các cấu hình năng lượng thấp nhất, của các cấu trúc thủy tinh quay khác nhau. Tình huống đôi khi được mô tả trong một “cảnh quan” của vô số đỉnh núi bị ngăn cách bởi các thung lũng, nơi mục tiêu là xác định vị trí đỉnh cao nhất. Trong trường hợp này, đỉnh cao nhất thực sự đại diện cho trạng thái năng lượng thấp nhất (mặc dù thay vào đó người ta có thể lật hình ảnh và tìm lỗ sâu nhất). Jamarnik giải thích: “Bạn có một dãy núi khổng lồ này, và có vẻ như cách duy nhất để tìm được vị trí cao hơn là leo lên từng ngọn một” —một công việc lố bịch giống như vậy mò kim đáy bể.

Các nhà vật lý đã chỉ ra rằng bạn có thể đơn giản hóa bức tranh này và thực hiện một bước hướng tới giải pháp, bằng cách cắt các ngọn núi đến một độ cao xác định trước và bỏ qua mọi thứ dưới mức giới hạn đó. Sau đó, bạn sẽ để lại một nhóm các đỉnh nổi bật trên một lớp mây đồng nhất, với mỗi điểm trong các đỉnh đó đại diện cho một giải pháp tiềm năng cho vấn đề ban đầu.

Trong một bài báo nghiên cứu năm 2014, Jamarnik và các đồng nghiệp lưu ý một số điều trước đây đã bị bỏ qua. Trong một số trường hợp, họ nhận ra rằng đường kính của mỗi đỉnh sẽ nhỏ hơn nhiều so với khoảng cách giữa các đỉnh khác nhau. Do đó, nếu người ta chọn hai điểm bất kỳ trên cảnh quan trải dài này – tức là hai “giải pháp” khả thi – thì chúng sẽ rất gần (nếu chúng đến từ cùng một đỉnh) hoặc rất xa nhau (nếu được vẽ từ các đỉnh khác nhau) . Nói cách khác, sẽ có một “khoảng cách” kể chuyện trong những khoảng cách này – nhỏ hay lớn, nhưng không có gì ở giữa. Jamarnik và các đồng nghiệp cho rằng hệ thống trong trường hợp này được đặc trưng bởi OGP.

Jamarnik khẳng định: “Chúng tôi nhận thấy rằng tất cả các vấn đề đã biết có tính chất ngẫu nhiên khó tính toán đều có một phiên bản của tính chất này” – đó là đường kính của ngọn núi trong mô hình giản đồ nhỏ hơn nhiều so với khoảng cách giữa các ngọn núi. “Điều này cung cấp một thước đo chính xác hơn về tính mạnh mẽ của thuật toán.”

Mở khóa bí mật về độ phức tạp của thuật toán

Sự ra đời của OGP có thể giúp các nhà nghiên cứu đánh giá độ khó của việc tạo ra các thuật toán nhanh để giải quyết các vấn đề cụ thể. Nó đã cho phép họ “toán học [and] Ông Jamarnik nói: Đặc biệt, chúng tôi đã học được rằng các thuật toán ổn định – những thuật toán có đầu ra sẽ không thay đổi nhiều nếu đầu vào chỉ thay đổi một chút – sẽ không giải quyết được loại vấn đề tối ưu hóa này. “Kết quả phủ định này không chỉ áp dụng cho máy tính cổ điển mà còn cho máy tính lượng tử và đặc biệt, cho cái gọi là“ thuật toán tối ưu hóa xấp xỉ lượng tử ”(QAOA), mà một số nhà nghiên cứu đã hy vọng sẽ giải quyết được các vấn đề tối ưu hóa tương tự. Hiện đã đưa ra kết quả của Jamarnik và phát hiện của các đồng tác giả, những hy vọng này được nung nấu bởi nhận thức rằng nhiều lớp hoạt động sẽ được yêu cầu để các thuật toán loại QAOA thành công, điều này có thể thách thức về mặt kỹ thuật.

Ông nói: “Đây là tin tốt hay xấu tùy thuộc vào quan điểm của bạn. “Tôi nghĩ rằng đó là một tin tốt theo nghĩa nó giúp chúng ta mở ra những bí mật về độ phức tạp của thuật toán và nâng cao kiến ​​thức của chúng ta về những gì thuộc lĩnh vực xác suất và những gì không. Đó là tin xấu theo nghĩa nó cho chúng ta biết những vấn đề này khó, ngay cả khi thiên nhiên tạo ra chúng, và ngay cả khi chúng được tạo ra một cách ngẫu nhiên ”. Anh ấy nói thêm rằng tin tức này không thực sự đáng ngạc nhiên. “Nhiều người trong chúng tôi đã mong đợi điều này từ lâu, nhưng giờ đây chúng tôi có cơ sở vững chắc hơn nhiều để đưa ra tuyên bố đó.”

Điều này vẫn khiến các nhà nghiên cứu mất nhiều năm ánh sáng để có thể chứng minh rằng không có thuật toán nhanh nào có thể giải quyết các vấn đề tối ưu hóa này trong các cài đặt ngẫu nhiên. Có bằng chứng như vậy sẽ cung cấp một câu trả lời chắc chắn cho vấn đề P NP. Anh ấy nói, “Nếu chúng tôi có thể chứng minh rằng chúng tôi không thể có một thuật toán hoạt động hầu hết thời gian, điều đó cho chúng tôi biết rằng chúng tôi chắc chắn không thể có một thuật toán hoạt động mọi lúc.”

Dự đoán sẽ mất bao lâu trước khi bài toán P NP được giải quyết có vẻ là một bài toán khó. Có khả năng sẽ có nhiều đỉnh núi để leo lên và các thung lũng để đi qua, trước khi các nhà nghiên cứu có được cái nhìn rõ ràng hơn về tình hình.