NP (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, NP là viết tắt của "nondeterministic polynomial time" (thuật toán bất định trong thời gian đa thức). Cụ thể hơn, NP là tập hợp các bài toán quyết định giải được trong thời gian đa thức bởi máy Turing bất định. Một định nghĩa khác của NP là tập hợp các bài toán quyết định mà trong trường hợp câu trả lời là "có", tồn tại một chứng minh có độ dài đa thức có thể kiểm chứng được trong thời gian đa thức bởi máy Turing tất định.

Định nghĩa

Một thuật toán kiểm chứng V cho ngôn ngữ A là một thuật toán (tất định) sao cho

• Với mọi chuỗi x trong ngôn ngữ A, tồn tại chuỗi y sao cho V(x,y)=1.
• Với mọi chuỗi x không nằm trong A, V(x,y)=0 với mọi y.

Thời gian thực thi của V được tính theo tham số là độ dài của x.

NP được định nghĩa là tập hợp các ngôn ngữ/bài toán có thuật toán kiểm chứng chạy trong thời gian đa thức.o

Ví dụ

• Tất cả các bài toán trong P.
• Phiên bản quyết định của bài toán phân tích số: cho 2 số nguyên n và k, xác định xem có tồn tại 1<f<k sao cho f chia hết n.
• Bài toán đồ thị đẳng cấu
• Tất cả các bài toán NP-đầy đủ, chẳng hạn như: bài toán người bán hàng, bài toán xếp ba lô

Quan hệ với các lớp bài toán khác

NP là tập hợp con của EXPTIME, MA.

NP=PCP(log n, O(1)) ^[1]

Ghi chú

1. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. “Proof verification and hardness of approximation problems”. Journal of the ACM 45(3):501-555, 1998. ECCC TR98-008.