Các sự cố "khó nhất" bằng cách sử dụng thời gian đa thức là gì?

Question

Gần đây tôi đọc a seminar work mà nói:

Việc kết hợp thuật toán [cho đồ thị nói chung] có thể được mở rộng với trường hợp có trọng số, mà dường như là một trong những vấn đề tối ưu hóa "khó khăn nhất" tổ hợp có thể được được giải quyết trong thời gian đa thức.

Ngay lập tức những câu dưới đây lóe lên trong óc tôi:

Bạn có biết những vấn đề khác "P-cứng"?

Hiện tại tôi muốn xác định P-hard là: "Một thuật toán đa thức đã được tìm thấy rất muộn (sau năm 1950) trong tài liệu cho vấn đề đó". (Hoặc làm cách nào để xác định tốt hơn "cứng" nếu đã có một thuật toán xác định giải quyết vấn đề trong thời gian đa thức?)

Answer 1

Có thực sự "P-hoàn thành" vấn đề, có nghĩa là mọi vấn đề khác có thể được tính toán trong thời gian đa thức có thể được giảm xuống chúng. Xem http://en.wikipedia.org/wiki/P-complete.

Answer 2

Primes is in P.

Answer 3

Một "cứng" P vấn đề được giải quyết "quy hoạch tuyến tính":

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Answer 4

The Assignment Problem có thể được giải quyết trong thời gian O (n) do biến đổi Hungarian Algorithm.

Answer 5

Nếu bạn muốn uốn cong các quy tắc một chút, thì pseudo-polynomial time algorithms là "khó nhất" mà bạn có thể giải quyết trong "thời gian đa thức".

Ví dụ kinh điển về thuật toán đa thức giả là giải pháp lập trình động O(nW) động cho knapsack problem.