← Về danh sách
Điện toán & Nhúng
#NP-완전#P-NP문제#계산복잡도#다항시간환원#쿡-레빈정리
Cập nhật lần cuối · 2026-11-14

Bài toán P đối với NP và Tính NP-đầy đủ (NP-Completeness)

1. Tổng quan

A. Định nghĩa

Tính NP-đầy đủ (NP-Completeness) chỉ tập hợp các bài toán quyết định "khó nhất" thuộc NP (thời gian đa thức không tất định), những bài toán mà mọi bài toán trong NP đều có thể quy dẫn về trong thời gian đa thức (polynomial-time reduction); vì chỉ cần một thuật toán thời gian đa thức cho bất kỳ bài toán nào trong số đó cũng khiến toàn bộ NP bằng P, tính NP-đầy đủ nằm ngay tại cốt lõi của bài toán P đối với NP (P versus NP problem).

Bài toán P-NP là câu hỏi mở nền tảng nhất của lý thuyết độ phức tạp tính toán, hỏi ranh giới nằm ở đâu giữa cái giải được bằng thuật toán và cái giải được một cách hiệu quả. Bài toán P-NP có thể tóm gọn trong một câu hỏi: "một bài toán mà kiểm chứng lời giải là dễ (thời gian đa thức) thì tìm lời giải có dễ không?" Lấy Sudoku làm ví dụ, kiểm tra một lưới đã hoàn thành có tuân thủ quy tắc hay không mất thời gian tỉ lệ với số ô và kết thúc gần như tức thì, nhưng tìm lời giải từ một lưới trống lại khó lên một cách đột biến khi lưới lớn dần. Bài toán P-NP hỏi liệu vô số bài toán trông "dễ kiểm chứng nhưng khó tìm kiếm" có thực sự khó về bản chất hay chỉ là ta chưa tìm ra phương pháp nhanh; tính NP-đầy đủ là cơ chế ràng buộc các bài toán này lại với nhau về mặt toán học dưới sự thật rằng chúng chia sẻ một số phận chung.

Để định nghĩa "dễ" và "khó" một cách chặt chẽ, lý thuyết độ phức tạp lấy thời gian đa thức làm đường cơ sở của hiệu quả. Một bài toán giải được trong thời gian tỉ lệ với một đa thức theo kích thước đầu vào được xếp loại "dễ xử lý (tractable)", một bài toán có vẻ cần thời gian hàm mũ được xếp "khó xử lý (intractable)", và bài toán P-NP chính là cuộc tranh luận về đường ranh giới một tập hợp bài toán khổng lồ thuộc về phía nào. Tính NP-đầy đủ đặt tên cho những bài toán nằm chông chênh ngay trên đường ranh giới ấy, những bài toán chưa ai chứng minh được thuộc về phía nào.

Hàm ý của tính NP-đầy đủ đối với thực tiễn CNTT là rõ ràng. Một khi một bài toán được chứng tỏ là NP-đầy đủ, việc cố tìm một thuật toán "nhanh và chính xác trên mọi đầu vào" chẳng khác nào đâm vào một bức tường đã đứng vững như một bài toán mở tầm thế giới suốt hàng chục năm, nên nhà thiết kế phải lập tức xoay sang thuật toán xấp xỉ, heuristic, ràng buộc bài toán, hoặc đầu vào đặc biệt. Với Kỹ sư chuyên nghiệp, do đó, tính NP-đầy đủ không phải lý thuyết trừu tượng mà là một tiêu chí thực tiễn để quyết định liệu đòi hỏi một thuật toán tối ưu hoàn hảo có hợp lý hay phải chấp nhận một lời giải đủ tốt.

B. Bối cảnh ra đời và tính cần thiết

Cho đến thập niên 1960, nghiên cứu thuật toán tập trung tìm phương pháp nhanh hơn cho từng bài toán riêng lẻ, nhưng khi các bài toán như Bài toán người bán hàng (TSP), bài toán thỏa được (SAT) và quy hoạch nguyên chất đống lên — những bài toán "trông dễ về trực giác nhưng kháng cự một phương pháp thời gian đa thức dù đã nỗ lực hàng chục năm" — mối ngờ vực lớn dần rằng chúng không khó một cách tình cờ mà chia sẻ một rào cản cấu trúc chung. Năm 1971 Stephen Cook và năm 1973 Leonid Levin độc lập chứng minh rằng "bài toán SAT là bài toán khó phổ quát mà mọi bài toán trong NP đều quy về" (định lý Cook-Levin), cuối cùng đem lại một định nghĩa toán học cho khái niệm "bài toán khó nhất"; năm sau Richard Karp gộp 21 bài toán tiêu biểu thành NP-đầy đủ, cho thấy khái niệm này áp dụng cho một dải rộng các bài toán thực tế.

Tính cần thiết của khám phá này nằm ở chỗ "ngăn sự lãng phí nỗ lực gần như bất khả thi". Không có lý thuyết NP-đầy đủ, một kỹ sư đứng trước một bài toán tối ưu có thể đốt tài nguyên vào hy vọng hão rằng "chỉ cần khôn khéo thêm chút nữa là ra một thuật toán nhanh". Nhưng một khi một bài toán được chứng minh NP-đầy đủ bằng một phép quy dẫn duy nhất, ta thu được cận dưới mạnh mẽ rằng "tìm một phương pháp chính xác hiệu quả cho bài toán này cũng khó như chứng minh P=NP", và có thể lập tức chuyển hướng nỗ lực sang các phương án thực tế. Tính NP-đầy đủ do đó không phải "chứng minh không giải được" mà là "chứng minh khả năng giải dễ là hết sức mong manh", đóng vai trò la bàn cho các quyết định kỹ thuật.

Hơn nữa, tính NP-đầy đủ chạm đến nền tảng của an ninh thông tin hiện đại. An toàn của các hệ mật dựa trên giả định rằng "phá bản mã mà không có khóa là khó về mặt tính toán", nên nếu P=NP được chứng minh là đúng, nhiều hệ mật khóa công khai bao gồm RSA ([[rsa-dsa]]) về nguyên tắc có thể bị vô hiệu hóa. Như vậy bài toán P-NP không chỉ là sự tò mò lý thuyết mà là một câu hỏi nền tảng định nghĩa khả năng và giới hạn của CNTT nói chung — thiết kế thuật toán, tối ưu, mật mã và tìm kiếm AI — nên Kỹ sư chuyên nghiệp phải nắm chính xác cấu trúc và cách ứng phó thực tiễn của nó.

2. Cấu trúc các lớp độ phức tạp tính toán

Để hiểu bài toán P-NP, trước hết phải vẽ ra địa hình các lớp độ phức tạp (complexity class) phân loại bài toán quyết định (bài toán có đáp án có/không) theo độ khó. Sơ đồ dưới đây thể hiện quan hệ bao hàm giữa các lớp trong thế giới P≠NP được giả định rộng rãi.

flowchart TB
    subgraph NPSPACE["Thế giới NP (giả định P≠NP)"]
        P["P<br/>(giải được trong thời gian đa thức)"]
        NPC["NP-đầy đủ<br/>(bài toán khó nhất trong NP)"]
        NPonly["NP (khác)<br/>vd: đẳng cấu đồ thị?"]
    end
    NPHARD["NP-khó<br/>(khó bằng NP hoặc hơn)"]
    P --> NPonly
    NPonly --> NPC
    NPC --> NPHARD
    NPHARD --> UNDEC["Bài toán không quyết định được<br/>(bài toán dừng, v.v.)"]

P (Polynomial time) là tập các bài toán giải được bằng thuật toán tất định trong thời gian đa thức, chẳng hạn O(nᵏ), theo kích thước đầu vào n. Hầu hết các bài toán ta gọi là "giải được hiệu quả trong thực tế" — sắp xếp ([[sorting-algorithms]]), đường đi ngắn nhất, cây khung nhỏ nhất — đều ở đây. Lý do P được dùng làm đại diện (proxy) cho "giải được hiệu quả" là thời gian đa thức tăng thoai thoải khi đầu vào lớn lên và có thể được hấp thụ bởi tiến bộ phần cứng, trong khi thời gian hàm mũ đòi hỏi khối lượng tính toán vượt quá tuổi của vũ trụ chỉ với đầu vào lớn hơn vài chục đơn vị. Sự tương phản hiện rõ qua con số: ở n=50, n³ khoảng 120.000 phép tính và tức thì, nhưng 2ⁿ khoảng 10¹⁵ và mất nhiều ngày, còn ở n=100, 2ⁿ vượt 10³⁰, thực tế bất khả thi ngay cả với siêu máy tính hiện nay. Khoảng cách này là ranh giới thực chất tách P khỏi các bài toán thời gian hàm mũ và giải thích vì sao phân biệt trừu tượng "đa thức đối với hàm mũ" lại mang tính quyết định trong kỹ thuật.

NP (Nondeterministic Polynomial time) là tập các bài toán mà, cho trước một đáp án ứng viên (chứng chỉ, certificate), ta có thể kiểm chứng trong thời gian đa thức xem nó có đúng không. Điểm cốt lõi là độ khó của "kiểm tra", không phải "tìm". Chẳng hạn, hỏi một đồ thị có chứa một clique (đồ thị con đầy đủ) kích thước k hay không thuộc NP, vì cho trước một tập đỉnh ứng viên ta kiểm tra mọi cặp đều nối trong O(k²). Mọi bài toán P hiển nhiên nằm trong NP (kiểm chứng có thể thay bằng tính lại) nên P⊆NP là hiển nhiên; câu hỏi thế kỷ là chiều ngược lại NP⊆P, tức liệu P=NP có đúng không.

NP-khó (NP-hard) nghĩa là bài toán "mà mọi bài toán trong NP đều quy dẫn về trong thời gian đa thức"; nó không nhất thiết phải thuộc NP, nên có thể bao gồm bài toán tối ưu không phải bài toán quyết định, hoặc thậm chí bài toán không quyết định được. NP-đầy đủ (NP-complete) được định nghĩa là bài toán vừa NP-khó vừa đồng thời thuộc NP, tức "bài toán khó nhất trong NP". Bảng dưới tóm tắt quan hệ bốn lớp, nhưng cái "vì sao" của mỗi định nghĩa phải được bổ sung bằng phần văn xuôi ở trên.

Lớp Định nghĩa (cốt lõi) Thuộc NP? Ví dụ tiêu biểu
P Giải được trong thời gian đa thức Luôn thuộc NP Đường đi ngắn nhất, sắp xếp, 2-SAT
NP Lời giải kiểm chứng được trong thời gian đa thức Thuộc NP theo định nghĩa Đường Hamilton, tổng con, clique
NP-đầy đủ NP-khó ∩ NP Thuộc NP 3-SAT, TSP (dạng quyết định), tô màu đồ thị
NP-khó Độ khó mà toàn NP quy về Có thể thuộc hoặc không TSP (dạng tối ưu), bài toán dừng

Mặt khác, trong địa hình độ phức tạp còn tồn tại một lớp song sinh gọi là co-NP. Nếu NP là tập các bài toán mà đáp án "có" kiểm chứng được trong thời gian đa thức, thì co-NP là tập mà đáp án "không" kiểm chứng được trong thời gian đa thức, tức phần bù của các bài toán NP. Ví dụ, "công thức logic này có bất khả thỏa (UNSAT) không?" là bài toán co-NP tiêu biểu. Liệu NP=co-NP cũng chưa có lời giải, và nếu một bài toán NP-đầy đủ nào đó được chứng tỏ cũng thuộc co-NP thì NP=co-NP sẽ kéo theo và nhiều phỏng đoán của lý thuyết độ phức tạp sẽ sụp đổ. Việc chính sự bất đối xứng "có/không" của bài toán quyết định mang ý nghĩa cấu trúc sâu sắc cho thấy tính NP-đầy đủ là một lý thuyết thăm dò bản chất của tính toán, chứ không đơn thuần là phân loại.

Ngoài ra, bài toán tối ưu trong thực tế thường hỏi "chi phí nhỏ nhất là bao nhiêu", một dạng tối ưu, trong khi tính NP-đầy đủ được định nghĩa ở dạng quyết định "có tồn tại lời giải với chi phí tối đa k không?" Điều này không tùy tiện mà vì dạng quyết định và dạng tối ưu quy dẫn lẫn nhau được trong thời gian đa thức — gọi lặp lại một bộ giải dạng quyết định qua tìm kiếm nhị phân sẽ tìm ra giá trị tối ưu trong thời gian đa thức. Do đó mệnh đề "TSP dạng quyết định là NP-đầy đủ" hàm ý "TSP dạng tối ưu cũng khó giải hiệu quả", tạo một cây cầu giữa lý thuyết và thực tiễn.

Điểm nhìn quan trọng nhất trong cấu trúc này là các bài toán NP-đầy đủ tạo thành một cộng đồng số phận duy nhất. Theo định nghĩa, bài toán NP-đầy đủ A bất kỳ bao hàm mọi bài toán NP khác, nên nếu tìm được một thuật toán thời gian đa thức cho A, theo chuỗi quy dẫn thì mọi bài toán trong NP giải được trong thời gian đa thức và P=NP đúng. Ngược lại, nếu chỉ một trong số đó được chứng minh là không giải được trong thời gian đa thức (một cận dưới hàm mũ), thì P≠NP được xác lập. Tức là số phận duy nhất của chỉ một trong hàng nghìn bài toán NP-đầy đủ quyết định số phận của tất cả.

3. Quy dẫn thời gian đa thức và chứng minh tính NP-đầy đủ

Động cơ của khái niệm NP-đầy đủ là quy dẫn thời gian đa thức (polynomial-time reduction). Quy dẫn bài toán A về bài toán B nghĩa là biến đổi đầu vào bất kỳ của A thành đầu vào của B trong thời gian đa thức, sao cho "đáp án của A là có" trùng khớp chính xác với "đáp án của B đã biến đổi là có" (ký hiệu A ≤ₚ B). Khi quan hệ này đúng, "nếu B dễ thì A dễ" tự động theo sau, nên quy dẫn trở thành một kênh truyền độ khó giữa các bài toán.

flowchart LR
    START["Chứng minh tính NP-đầy đủ<br/>của bài toán mới X"] --> S1["Bước 1: X thuộc NP<br/>(lời giải kiểm chứng được trong thời gian đa thức)"]
    S1 --> S2["Bước 2: chọn bài toán NP-đầy đủ đã biết Y<br/>(vd: 3-SAT)"]
    S2 --> S3["Bước 3: dựng quy dẫn Y ≤ₚ X<br/>(biến đầu vào Y thành đầu vào X trong thời gian đa thức)"]
    S3 --> S4["Bước 4: chứng minh phép biến đổi bảo toàn đáp án<br/>(có↔có, không↔không)"]
    S4 --> DONE["X là NP-đầy đủ<br/>(độ khó của Y được truyền)"]
    S1 -. "nếu bước nào thất bại" .-> FAIL["Không NP-đầy đủ<br/>(cần cách tiếp cận khác)"]
    S3 -. "nếu bước nào thất bại" .-> FAIL

Quy trình chuẩn để chứng minh một bài toán mới X là NP-đầy đủ gồm hai trục, như sơ đồ thể hiện. Thứ nhất, chỉ ra X thuộc NP (trình bày rằng cho trước một đáp án ứng viên thì kiểm chứng được trong thời gian đa thức). Thứ hai, quy dẫn một bài toán Y đã biết là NP-đầy đủ về X (Y ≤ₚ X) để truyền cận dưới "khó bằng Y". Ở đây chiều của quy dẫn là cốt lõi: phải quy dẫn Y về X thì "độ khó của Y mới được kế thừa sang X"; đảo chiều thì không chứng minh được gì. "Bẫy chiều quy dẫn" này là lỗi phổ biến nhất ở cả thi cử lẫn thực tiễn, nên phải hết sức lưu ý.

Điểm xuất phát của mọi chuỗi quy dẫn này chính là định lý Cook-Levin (Cook-Levin Theorem). Trong trạng thái chưa có bất kỳ bài toán NP-đầy đủ nào đã biết để quy dẫn từ đó, định lý này chứng minh trực tiếp rằng SAT (thỏa được Boolean) là NP-đầy đủ. Cốt lõi của chứng minh là "toàn bộ quá trình tính toán của một máy Turing không tất định giải một bài toán NP bất kỳ có thể được mã hóa, trong thời gian đa thức, thành một công thức logic khổng lồ (CNF) tương đương với việc máy đó có chấp nhận đáp án hay không". Tức là bất kỳ bài toán NP nào cũng có thể dịch "lịch sử tính toán" của nó thành một công thức SAT, nên giải được SAT là giải được mọi bài toán NP. Kể từ khi SAT được xác lập là bài toán NP-đầy đủ đầu tiên, chứng minh bài toán mới chuyển từ việc "tạo ra cái gì đó từ hư không" thành công việc tương đối máy móc là "quy dẫn một bài toán khó đã biết".

Lý do quy dẫn có thể làm kênh truyền độ khó nằm ở tính bắc cầu (transitivity) của nó. Nếu A ≤ₚ B và B ≤ₚ C thì A ≤ₚ C đúng, vì hợp của các đa thức vẫn là đa thức. Một khi định lý Cook-Levin xác lập SAT là NP-đầy đủ, và chuỗi quy dẫn kéo dài SAT ≤ₚ 3-SAT ≤ₚ clique ≤ₚ phủ đỉnh ≤ₚ …, thì mọi bài toán trên chuỗi tự động trở thành NP-đầy đủ. Tính bắc cầu cũng là lý do Karp có thể gộp 21 bài toán thành NP-đầy đủ cùng một lúc; hàng nghìn bài toán NP-đầy đủ được biết đến nay đều là các nhánh của một cây quy dẫn khổng lồ mọc ra từ một gốc duy nhất (SAT). Khi chứng minh một bài toán mới, chọn khéo "quy dẫn từ bài toán đã biết nào" có thể khiến chứng minh gọn hơn hẳn, nên việc chọn điểm xuất phát của quy dẫn tự nó là một phán đoán thiết kế.

Lấy ví dụ cụ thể về quy dẫn, hãy xét quy dẫn từ 3-SAT về bài toán clique. Cho một công thức 3-SAT có m mệnh đề (clause), tạo 3m đỉnh, mỗi đỉnh cho một trong ba literal của mỗi mệnh đề, và chỉ nối bằng cạnh những literal thuộc các mệnh đề khác nhau và không mâu thuẫn (một bên là x và bên kia không phải ¬x). Chỉ ra rằng sự tồn tại một clique kích thước m trong đồ thị này trùng khớp chính xác với việc công thức gốc thỏa được sẽ hoàn tất quy dẫn. Vì việc tạo đỉnh/cạnh kết thúc trong một đa thức theo kích thước công thức, đây là quy dẫn thời gian đa thức, và một lần dựng này chứng minh rằng "nếu SAT khó thì clique cũng khó". Năng lực thiết kế quy dẫn cụ thể này là kỹ năng cốt lõi trong việc xử lý tính NP-đầy đủ.

Một hiểu lầm phổ biến trong thực tiễn là vội kết luận "bài toán của tôi dễ vì tôi có thể biến nó thành một bài toán dễ đã biết". Nhưng để chứng minh tính NP-đầy đủ, ngược lại phải quy dẫn một bài toán khó đã biết về bài toán của tôi. Quy dẫn bài toán của tôi về một bài toán dễ lại là công việc ngược lại, cho một cận trên rằng "bài toán của tôi có thể dễ". Sự nhầm lẫn chiều này có thể sinh ra niềm tin sai lầm rằng "tôi đã chứng minh NP-đầy đủ" và bóp méo quyết định thiết kế, nên phải phân biệt rõ ở mỗi bước chiều của quy dẫn và cái nó truyền (cận dưới hay cận trên).

4. So sánh các bài toán tiêu biểu và ranh giới P-NP

Đặt các bài toán NP-đầy đủ cạnh những bài toán "giống" chúng nhưng thuộc P cho thấy một khác biệt điều kiện tinh vi đến mức nào chia cắt ranh giới độ khó. Bảng sau và phần văn xuôi sau nó tóm tắt các trường hợp tiêu biểu.

Bài toán khó (NP-đầy đủ) Bài toán dễ giống (P) Điều kiện chia ranh giới
3-SAT (3 literal mỗi mệnh đề) 2-SAT (2 mỗi mệnh đề) Độ dài mệnh đề ≤2 giải tuyến tính qua đồ thị kéo theo
Đường Hamilton (mỗi đỉnh một lần) Đường Euler (mỗi cạnh một lần) Điều kiện cạnh giải được thời gian đa thức bằng kiểm tra bậc
Tô 3 màu đồ thị tổng quát Tô 2 màu (kiểm tra đồ thị hai phía) Với 2 màu, quyết định tuyến tính bằng BFS
Ba lô 0/1 (chọn nguyên) Ba lô phân số (chia được) Nếu chia được, tham lam ([[greedy-algorithm]]) là tối ưu
TSP (hành trình ngắn nhất) Cây khung nhỏ nhất (MST) Ràng buộc hành trình (chu trình) phá vỡ tham lam

Ví dụ ấn tượng nhất là tương phản giữa 2-SAT và 3-SAT. Nếu mỗi mệnh đề có tối đa 2 biến, tính thỏa được có thể quyết định trong thời gian tuyến tính bằng cách tìm thành phần liên thông mạnh trong một đồ thị kéo theo biểu diễn các suy diễn kiểu "nếu a đúng thì b cũng phải đúng". Nhưng khoảnh khắc số biến mỗi mệnh đề lên 3, cấu trúc thanh lịch này biến mất và nó trở thành NP-đầy đủ. Một khác biệt của một literal chia cắt "thời gian tuyến tính" khỏi "thời gian hàm mũ phỏng đoán". Điều này cho thấy tính NP-đầy đủ sinh ra không phải từ vẻ ngoài của bài toán mà từ cấu trúc tổ hợp nội tại của nó.

Hai biến thể của bài toán ba lô cũng mang tính giáo huấn. Ba lô phân số, nơi vật phẩm có thể chia nhỏ, là tối ưu chứng minh được với chiến lược tham lam nhét theo thứ tự giá trị trên đơn vị khối lượng cao nhất, nhưng ba lô 0/1, nơi vật phẩm không chia được, phá vỡ tham lam vì cách lựa chọn rời rạc "nhét bây giờ hay không" ảnh hưởng đến tương lai, và là NP-đầy đủ. Tuy vậy ba lô 0/1 giải được bằng quy hoạch động ([[dynamic-programming]]) trong O(nW); điều này trông đa thức nhưng vì W là "giá trị" của một con số, nó hàm mũ theo số bit đầu vào — một thuật toán giả đa thức (pseudo-polynomial). Phân biệt "NP-đầy đủ nghĩa yếu" với "NP-đầy đủ nghĩa mạnh" cũng quan trọng với phán đoán thực tiễn.

Cuối cùng, tương phản giữa TSP và MST là nguyên mẫu của một ràng buộc làm thay đổi độ khó. Một cây chi phí nhỏ nhất nối mọi thành phố (MST) giải được bằng tham lam trong thời gian đa thức, nhưng khoảnh khắc đòi hỏi một hành trình chi phí nhỏ nhất thăm mỗi thành phố đúng một lần và trở về điểm xuất phát, nó trở thành NP-khó. Thêm ràng buộc nhỏ chuyển từ "cây" thành "chu trình Hamilton" lật ngược việc có tồn tại lời giải hiệu quả hay không. Đây chính là lý do nền tảng khiến tối ưu tuyến đường logistics khó trong thực tế.

Bài học thực tiễn của các trường hợp ranh giới này là tính NP-đầy đủ không phải một hiện tượng hiếm chỉ ẩn trong các bài toán toán học đặc biệt mà hiện diện khắp nơi trong hệ thống thông tin. Lập lịch công việc trên dây chuyền sản xuất, bố trí tài nguyên đám mây (bin packing), cấp phát thanh ghi trong trình biên dịch (tô màu đồ thị), bố trí và đi dây mạch điện, xếp thời khóa biểu, và cấp phát tần số trong mạng viễn thông đều là biến thể của các bài toán NP-đầy đủ. Việc con người và hệ thống xử lý "tạm ổn" những bài toán gặp vô số lần mỗi ngày này là vì đầu vào thực tế không có cấu trúc tổ hợp xấu nhất hoặc vì chúng thỏa hiệp với xấp xỉ chấp nhận được. Kỹ sư chuyên nghiệp do đó phải rèn một con mắt định lượng được "từ bỏ sự hoàn hảo thì được và mất gì".

5. Chuyên sâu: Chiến lược ứng phó thực tiễn và hiện trạng P=NP

Một bài toán được chứng minh NP-đầy đủ không phải là cớ để từ bỏ. Trong thực tiễn, ta nới lỏng một trong ba điều kiện "trên mọi đầu vào, luôn tối ưu, nhanh" để thu một lời giải thực tế. Thứ nhất, thuật toán xấp xỉ (approximation algorithm) cung cấp, thay cho tối ưu, một lời giải trong một tỉ lệ được bảo đảm trong thời gian đa thức. Chẳng hạn, phủ đỉnh được bảo đảm trong hệ số 2 bằng tham lam đơn giản, và TSP Euclid trong 1,5 bằng thuật toán Christofides. Thứ hai, heuristic và metaheuristic ([[metaheuristics]]) không có bảo đảm nhưng cho lời giải rất tốt trên thực địa — các bộ giải SAT hiện đại (CDCL) giải các thực thể công nghiệp hàng triệu biến trong vài giây dù trường hợp xấu nhất là hàm mũ, và được dùng thường quy trong kiểm chứng EDA và kiểm tra mô hình phần mềm. Thuật toán di truyền, luyện thép mô phỏng (simulated annealing) và tìm kiếm tabu đều đặn cho lời giải gần tối ưu trên TSP và lập lịch quy mô lớn, và "khoảng cách giữa độ khó lý thuyết và tính khả dụng thực tiễn" này chính là sân khấu của kỹ thuật hiện đại cho các bài toán NP-đầy đủ.

Thứ ba, độ phức tạp tham số hóa (parameterized complexity) giam số mũ không vào kích thước đầu vào mà vào một tham số k cụ thể (vd: kích thước phủ, độ rộng cây), thiết kế các thuật toán FPT dạng f(k)·nᶜ. Trên đầu vào thực nơi k giữ nhỏ, chúng hoạt động thực chất như thời gian đa thức. Thứ tư là chiến lược giới hạn bài toán vào đầu vào hoặc cấu trúc đặc biệt — nhiều bài toán NP-đầy đủ trên đồ thị tổng quát lại giải được trong thời gian đa thức trên cây, đồ thị phẳng, hay đồ thị khoảng. Sơ đồ dưới tóm tắt quyết định ứng phó khi đối mặt một bài toán NP-đầy đủ.

flowchart TB
    NPC["Bài toán được chứng minh NP-đầy đủ"] --> Q1{"Đầu vào có nhỏ không?"}
    Q1 -->|"Có"| EXACT["Thuật toán chính xác<br/>(nhánh-cận, DP, bộ giải SAT/ILP)"]
    Q1 -->|"Không"| Q2{"Có cần chất lượng bảo đảm?"}
    Q2 -->|"Có"| APPROX["Thuật toán xấp xỉ<br/>(tỉ lệ bảo đảm)"]
    Q2 -->|"Không"| HEUR["Heuristic/metaheuristic<br/>(di truyền, luyện thép, tìm kiếm cục bộ)"]
    NPC --> Q3{"Cấu trúc đặc biệt, tham số nhỏ?"}
    Q3 -->|"Có"| FPT["Thuật toán FPT/đầu vào giới hạn<br/>(đồ thị cây, phẳng, khoảng)"]

Ngay cả khi cần một lời giải chính xác, các thuật toán chính xác "hàm mũ nhưng nhanh nhất có thể" vẫn được nghiên cứu sôi nổi. Chẳng hạn, TSP là O(n!) bằng vét cạn ngây thơ nhưng quy hoạch động Held-Karp giảm nó xuống O(2ⁿ·n²), khiến nó giải được thực tế với n quanh 20. Liên quan đến đó, Giả thuyết thời gian hàm mũ (ETH, Exponential Time Hypothesis) giả định "3-SAT không giải được trong 2^o(n)"; đây là tiền đề mạnh hơn P≠NP và cung cấp một cận dưới tinh hơn rằng "với các bài toán NP-đầy đủ, dù khôn khéo đến đâu, không thể giảm cơ số của số mũ về gần 1". Chấp nhận ETH cho phép lập luận tính tối ưu có điều kiện cho nhiều bài toán rằng "không gì nhanh hơn một cách bản chất so với thuật toán này là khả dĩ", đóng vai trò bánh lái cho nghiên cứu thuật toán.

Việc chọn trong các chiến lược ứng phó này phụ thuộc đặc tính bài toán và chất lượng yêu cầu, và thường là kết hợp vài chiến lược theo tầng ngay cả trong một hệ thống duy nhất. Chẳng hạn, một động cơ định tuyến logistics quy mô lớn trước tiên sinh nhanh các tuyến ban đầu bằng heuristic, cải thiện chúng bằng tìm kiếm cục bộ trong thời gian cho phép, rồi tái tối ưu chỉ các đoạn cốt lõi bằng thuật toán chính xác, thỏa mãn "tốc độ-chất lượng-độ chính xác" cùng lúc.

Bản thân bài toán P=NP vẫn còn mở, đứng như một trong bảy Bài toán Giải thưởng Thiên niên kỷ do Viện Toán học Clay tuyển chọn năm 2000 (giải thưởng: một triệu đô la). Đa số chuyên gia tin P≠NP, nhưng không bên nào được chứng minh, và chỉ có các siêu lý thuyết tích tụ về lý do các kỹ thuật chứng minh hiện có thất bại, như rào cản chứng minh tự nhiên (natural proofs) và rào cản tương đối hóa (relativization). Nếu P=NP được chứng minh một cách kiến thiết, tối ưu, thiết kế thuốc và chứng minh định lý sẽ trở nên dễ một cách cách mạng, trong khi phần lớn mật mã khóa công khai hiện đại sẽ sụp đổ, buộc tái tổ chức toàn diện mô hình an ninh. Thú vị là tính toán lượng tử ([[qubit]]) không phải lời giải cho bài toán này — các thuật toán lượng tử giải nhanh một số bài toán như phân tích thừa số nguyên, nhưng không có bằng chứng chúng giải các bài toán NP-đầy đủ nói chung trong thời gian đa thức (tìm kiếm Grover chỉ cho tăng tốc căn bậc hai), đó là lý do mật mã kháng lượng tử ([[post-quantum-cryptography]]) như các lược đồ dựa trên lưới được nghiên cứu riêng.

6. Các điểm cân nhắc và hàm ý

Tính NP-đầy đủ định nghĩa giới hạn của thiết kế thuật toán đồng thời đòi hỏi tư duy chiến lược lách qua các giới hạn đó về mặt kỹ thuật. Từ góc nhìn của Kỹ sư chuyên nghiệp, cần cân nhắc tổng hợp những điều sau.

  • Thực hiện phân loại bài toán sớm trong thiết kế. Khi nhận một bài toán tối ưu, lập lịch hay bố trí, điều đầu tiên cần kiểm tra là "cái này có quy về một bài toán NP-đầy đủ đã biết không?" Nếu phán là NP-đầy đủ, rút lại đòi hỏi một "phương pháp tối ưu hoàn hảo" và xoay sang xấp xỉ/heuristic là chìa khóa ngăn lãng phí tài nguyên; ngược lại, cũng phải đề phòng việc vội tuyên nó "khó" và bỏ sót các biến thể thực ra thuộc P (2-SAT, MST, v.v.). Bản thân phân loại chi phối chất lượng thiết kế.

  • Khớp đánh đổi độ chính xác-thời gian-tính phổ quát với yêu cầu. Nếu đầu vào nhỏ và độ chính xác là tuyệt đối, chọn lời giải chính xác qua nhánh-cận hay bộ giải ILP/SAT; với môi trường thời gian thực quy mô lớn, một thuật toán có tỉ lệ xấp xỉ bảo đảm; nơi hiệu năng trung bình quan trọng hơn bảo đảm chất lượng, một metaheuristic. Ghi lại rõ ràng điểm cân bằng này theo yêu cầu SLA, chi phí và an toàn, và thống nhất với các bên liên quan về tiêu chí chấp nhận một "lời giải đủ tốt" sẽ giảm thất bại.

  • Tích cực khai thác giả đa thức và tham số hóa. Khi dải giá trị số bị chặn, như ở ba lô 0/1, DP giả đa thức trở thành lời giải thực tế, và khi các tham số cấu trúc như kích thước phủ hay độ rộng cây nhỏ, các thuật toán FPT hoạt động thực chất như thời gian đa thức. Vứt bỏ lưỡng phân "NP-đầy đủ = không giải được" và phân tích đặc tính của đầu vào thực (độ lớn giá trị, thưa cấu trúc) để khai quật tính dễ xử lý thời gian đa thức ẩn giấu là một năng lực thiết kế cao cấp.

  • Hiểu các giả định an toàn mật mã và chuẩn bị cho chuyển đổi. An toàn của nhiều lược đồ khóa công khai dựa trên độ khó tính toán giả định của các bài toán cụ thể, điều này đứng trên tiền đề lớn hơn là P≠NP. Vì một đột phá trong thuật toán hoặc tiến bộ của tính toán lượng tử có thể lung lay giả định này, kiến trúc an ninh nên sở hữu tính linh hoạt mật mã (crypto-agility), bảo đảm trước một lộ trình di trú sang mật mã kháng lượng tử. Theo dõi thay đổi trong các giả định độ khó là một phần của chiến lược an ninh dài hạn.

  • Kiểm chứng và giám sát chất lượng lời giải heuristic. Khi đưa một heuristic không bảo đảm vào vận hành, ước lượng khoảng tối ưu so với cận dưới/trên (vd: cận dưới nới lỏng LP) và liên tục quan sát suy giảm chất lượng khi phân phối đầu vào dịch chuyển. Để một "đáp án nhanh" không trở thành một "đáp án sai", một thiết kế đưa chỉ số chất lượng của lời giải xấp xỉ vào hệ giám sát dịch vụ và tự động chuyển sang một thuật toán chính xác hơn khi vượt ngưỡng sẽ nâng độ tin cậy.

Tài liệu tham khảo


Tóm tắt một câu: Bài toán P-NP hỏi liệu một bài toán dễ kiểm chứng (NP) có dễ giải (P) không, và tính NP-đầy đủ, qua quy dẫn thời gian đa thức và định lý Cook-Levin, ràng buộc các bài toán "khó nhất" mà toàn NP quy về thành một cộng đồng số phận duy nhất. Một khi một bài toán được chứng tỏ NP-đầy đủ, phải xoay từ một phương pháp tối ưu hoàn hảo sang các chiến lược xấp xỉ, heuristic, tham số hóa và đầu vào đặc biệt, và phán đoán phân loại cùng đánh đổi này là cốt lõi của chất lượng thiết kế và chiến lược an toàn mật mã.