Lý thuyết độ phức tạp tính toán

Trường hợp

Một vấn đề tính toán có thể xem là một tập vô hạn các trường hợp cùng với lời giải cho mỗi trường hợp. Không nên nhầm lẫn giữa dữ liệu vào cho mỗi vấn đề tính toán, còn gọi là một trường hợp, và bản thân vấn đề. Trong lý thuyết độ phức tạp tính toán, một vấn đề là một câu hỏi trừu tượng cần giải quyết. Một trường hợp là một trường hợp cụ thể của câu hỏi trừu tượng đó. Để rõ hơn, ta xem xét vấn đề kiểm tra tính nguyên tố. Một trường hợp là một số nguyên (ví dụ như 15) và lời giải là "có" nếu như số đó là nguyên tố và "không" nếu nó không là nguyên tố (trong trường hợp này, lời giải là "không").

Biểu diễn trường hợp

Khi xem xét các vấn đề tính toán, một trường hợp là một xâu ký tự trong một bảng chữ cái nhất định. Bảng chữ cái thường dùng là bảng chữ cái nhị phân (gồm 2 ký tự 0 và 1). Cũng như trong máy tính trên thực tế, các đối tượng toán học cần phải được mã hóa hợp lý dưới dạng các dãy bit. Ví dụ như một số nguyên cần phải được biểu diễn dưới dạng nhị phân, đồ thị có thể được biểu diễn dưới dạng ma trận kề, hoặc mã hóa danh sách kề dưới dạng nhị phân.

Mặc dù một số chứng minh của các định lý trong lý thuyết độ phức tạp tính toán giả sử một mã hóa nhất định của dữ liệu vào, người ta thường cố gắng giữ cho các lập luận đủ trừu tượng để không phụ thuộc vào cách mã hóa. Điều này có thể đạt được bằng cách đảm bảo có thể được chuyển từ cách mã hóa này sang cách mã hóa khác một cách hiệu quả.

Bài toán quyết định dưới dạng ngôn ngữ hình thức

Bài toán quyết định là một trong những đối tượng trọng tâm nghiên cứu của lý thuyết độ phức tạp tính toán. Một bài toán quyết định là một trường hợp đặc biệt của bài toán tính toán, với câu trả lời là có hoặc không, hay nói cách khác là 0 hoặc 1. Một bài toán quyết định có thể được xem là một ngôn ngữ hình thức, trong đó các xâu ký tự thành viên của ngôn ngữ là các những trường hợp có câu trả lời là có, các xâu ký tự không là thành viên là những trường hợp có câu trả lời là không. Mục tiêu của bài toán là sử dụng một thuật toán để quyết định xem một xâu cho trước có là thành viên của ngôn ngữ hình thức đang xem xét hay không. Nếu thuật toán quyết định là có, thì ta nói thuật toán chấp nhận xâu dữ liệu vào, nếu không thì ta nói thuật toán từ chối xâu dữ liệu vào.

Một ví dụ của bài toán quyết định là như sau. Dữ liệu vào là một đồ thị bất kì. Bài toán yêu cầu quyết định xem đồ thị có liên thông hay không. Ngôn ngữ hình thức tương ứng cho bài toán này là tập tất cả các đồ thị liên thông. Dĩ nhiên để định nghĩa chặt chẽ bài toán, cần phải quyết định xem đồ thị được mã hóa như thế nào dưới dạng xâu nhị phân.

Bài toán hàm

Một bài toán hàm là một bài toán tính toán trong đó mỗi dữ liệu vào cho đúng một kết quả, nhưng kết quả đó phức tạp hơn kết quả của bài toán quyết định, nghĩa là nó không chỉ là có hay không. Ví dụ như bài toán người bán hàng, và bài toán phân tích ra thừa số nguyên tố.

Thoạt nhìn có vẻ khái niệm bài toán hàm là rộng hơn khái niệm bài toán tính toán. Tuy nhiên, điều này không hẳn là đúng do các bài toán hàm có thể được viết lại dưới dạng bài toán quyết định. Ví dụ như bài toán nhân hai số nguyên có thể được biểu diễn dưới dạng tập hợp các bộ ba (a, b, c) sao cho a × b < c. Quyết định xem liệu một bộ ba cho trước có phải là thành viên của tập hợp đó hay không tương ứng với việc nhân hai số.

Kích thước của trường hợp

Để đánh giá độ khó của một bài toán tính toán, một thước đo phổ biến là lượng thời gian thuật toán tốt nhất cần dùng để giải nó. Tuy nhiên, thời gian cần thiết nói chung phụ thuộc vào từng trường hợp cụ thể. Trường hợp lớn hơn thường đòi hỏi nhiều thời gian hơn. Do đó thời gian cần thiết để giải quyết bài toán (hoặc bộ nhớ, hay bất kì một thông số độ phức tạp nào) là một hàm số của kích thước trường hợp. Kích thước thường được đo bằng kích thước dữ liệu vào với đơn vị bit. Lý thuyết độ phức tạp quan tâm đến hành vi của thuật toán khi kích thước dữ liệu vào tăng lên. Ví dụ như trong bài toán kiểm tra xem một đồ thị có liên thông hay không, thời gian cần thiết để kiểm tra một đồ thị kích thước 2n là bao nhiêu so với thời gian để kiểm tra đồ thị kích thước n?

Khi kích thước dữ liệu vào là n, thời gian có thể được biểu diễn dưới dạng một hàm số của n. Do thời gian cần thiết cho các trường hợp cùng kích thước có thể khác nhau, thời gian trong trường hợp xấu nhất T(n) được định nghĩa là lượng thời gian lớn nhất trong tất cả các trường hợp có kích thước n. Nếu T(n) là đa thức của n, thì ta nói thuật toán chạy thời gian đa thức.

Máy Turing

Máy Turing là một mô hình toán học cho một máy tính tổng quát. Nó là một thiết bị lý thuyết thao tác trên các ký hiệu nằm trên một dải băng. Máy Turing không nhằm thiết kế thiết bị tính toán trên thực tế, mà chỉ là một thiết bị trừu tượng đại diện cho máy tính. Người ta tin rằng nếu một vấn đề có thể được giải quyết bởi một thuật toán, thì cũng có một máy Turing giải quyết vấn đề đó. Tất cả các mô hình tính toán hiện nay chẳng hạn như máy RAM, Trò chơi cuộc sống của Conway, automat tế bào, hay bất kì ngôn ngữ lập trình nào cũng đều có thể tính được trên máy Turing. Do máy Turing phù hợp cho việc nghiên cứu bằng toán học, và được xem là mạnh ngang bất kì mô hình tính toán nào, máy Turing là mô hình tính toán phổ biến nhất trong lý thuyết độ phức tạp tính toán.

Các mô hình khác

Có nhiều mô hình khác ngoài mô hình chuẩn máy Turing nhiều băng đã được nghiên cứu, chẳng hạn như máy truy cập ngẫu nhiên. Tất cả các mô hình này đều có thể được chuyển hóa lẫn nhau mà không cần thêm khả năng tính toán đặc biệt nào. Tuy vậy, thời gian và bộ nhớ của các mô hình khác nhau có thể khác nhau.^[1].

Các thông số độ phức tạp

Để định nghĩa cụ thể thời gian và bộ nhớ cần thiết để giải quyết một vấn đề, cần định rõ một mô hình tính toán cụ thể, chẳng hạn như máy Turing tất định. Thời gian cần thiết cho một máy Turing M giải quyết dữ liệu vào x là số lượng lần chuyển trạng thái, hay số bước, của máy trước khi máy ngừng và thông báo kết quả ("có" hoặc "không"). Một máy Turing chạy trong thời gian f(n) nếu thời gian máy sử dụng cho tất cả các dữ liệu vào kích thước n là không quá f(n). Có thể định nghĩa lượng bộ nhớ cần thiết một cách tương tự như vậy. Mặc dù thời gian và bộ nhớ là hai thông số phổ biến nhất, nhiều thông số phức tạp khác cũng có thể xem là tài nguyên tính toán. Các thông số độ phức tạp được định nghĩa tổng quát bởi các tiên đề độ phức tạp Blum. Một vài thông số độ phức tạp khác được dùng trong lý thuyết độ phức tạp bao gồm độ phức tạp truyền thông, độ phức tạp mạch, và độ phức tạp cây quyết định.

Định nghĩa lớp độ phức tạp

Một lớp độ phức tạp là một tập hợp các vấn đề có độ phức tạp tương tự nhau. Các lớp độ phức tạp thường được định nghĩa theo các yếu tố sau:

• Thể loại vấn đề: thể loại phổ biến nhất là bài toán quyết định. Ngoài ra còn có bài toán hàm, bài toán đếm, bài toán tối ưu, bài toán có lời hứa, v.v.
• Mô hình tính toán: mô hình phổ biến nhất là máy Turing tất định. Ngoài ra còn có máy Turing bất định, mạch Boole, máy Turing lượng tử, mạch đơn điệu, v.v.
• Loại tài nguyên bị giới hạn và giới hạn cụ thể: chẳng hạn như "thời gian đa thức", "bộ nhớ lôgarit", v.v.

Các lớp độ phức tạp quan trọng

Theo định lý Savitch, PSPACE = NPSPACE và EXPSPACE = NEXPSPACE.

Một số lớp độ phức tạp quan trọng khác bao gồm BPP, ZPP, RP là các lớp định nghĩa trên máy Turing ngẫu nhiên, AC và NC là các lớp định nghĩa trên mạch logic Boole, và BQP và QMA là các lớp định nghĩa trên máy Turing lượng tử. #P là một lớp độ phức tạp quan trọng cho các bài toán đếm. Các lớp như IP và AM được định nghĩa thông qua hệ thống chứng minh tương tác. ALL là lớp tất cả các bài toán quyết định.

Các định lý cấp bậc

Với các lớp độ phức tạp định nghĩa như trên, một vấn đề đáng quan tâm là liệu với nhiều tài nguyên hơn, chẳng hạn như nhiều thời gian hơn, tập hợp các bài toán giải được có nhiều lên hay không. Cụ thể hơn, mặc dù DTIME(n) rõ ràng là tập hợp con của DTIME(n²), một câu hỏi lý thú là liệu mối quan hệ tập hợp con có chặt hay không. Với thời gian và bộ nhớ, câu hỏi trên được trả lời bởi các định lý cấp bậc thời gian và bộ nhớ. Cụ thể hơn, định lý cấp bậc thời gian là

${\displaystyle \operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}}$ .

Định lý cấp bậc bộ nhớ là

${\displaystyle \operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}}$ .

Các định lý cấp bậc thời gian và bộ nhớ là cơ sở cho hầu hết các kết quả phân tách các lớp độ phức tạp. Ví dụ như định lý cấp bậc thời gian cho ta thấy P là tập hợp con chặt của EXPTIME, và định lý cấp bậc bộ nhớ cho ta thấy L là tập con chặt của PSPACE.

Quy về

Nhiều lớp độ phức tạp được định nghĩa thông qua khái niệm phép quy về. Một phép quy về là một biến đổi từ một bài toán này thành một bài toán khác. Nó thâu tóm khái niệm trực giác một bài toán ít nhất là khó bằng một bài toán khác. Nếu một bài toán X có thể được giải bằng thuật toán cho bài toán Y thì X không khó hơn Y, và ta nói X quy về Y. Có nhiều kiểu quy về khác nhau, tùy theo phương pháp quy về, chẳng hạn như phép quy về Cook, phép quy về Karp, phép quy về Levin, và tùy theo độ phức tạp của phép quy về, chẳng hạn như quy về trong thời gian đa thức, hoặc quy về trong bộ nhớ lôgarit.

Phép quy về phổ biến nhất là quy về trong thời gian đa thức. Điều này có nghĩa là thuật toán quy về chạy trong thời gian đa thức. Ví dụ như bài toán tính bình phương của một số nguyên có thể được quy về bài toán nhân hai số nguyên. Có nghĩa là thuật toán nhân hai số nguyên có thể dùng để tính bình phương một số bằng cách dùng số nguyên cần tính bình phương làm cả hai thừa số cho thuật toán nhân số. Do đó, tính bình phương không khó hơn phép nhân, bởi vì tính bình phương có thể quy về phép nhân.

Định nghĩa trên dẫn tới khái niệm khó cho một lớp độ phức tạp. Một bài toán X là khó cho lớp bài toán C nếu mọi bài toán trong C có thể quy về X. Khi đó, không có bài toán nào trong C là khó hơn X do một thuật toán cho X có thể giải bất kì bài toán nào trong C. Dĩ nhiên khái niệm bài toán khó tùy thuộc vào loại quy về được sử dụng. Cho các lớp độ phức tạp lớn hơn P, quy về trong thời gian đa thức thường được sử dụng. Ví dụ như tập hợp các bài toán khó cho NP là tập hợp các bài toán NP-khó.

Nếu bài toán X nằm trong C và là khó cho C, thì X là đầy đủ cho C. Điều này có nghĩa là X là bài toán khó nhất trong C. (Do có thể có nhiều bài toán cùng độ khó, có thể nói là X là một trong những bài toán khó nhất trong C). Do vậy, lớp NP-đầy đủ chứa những bài toán khó nhất trong NP, theo nghĩa chúng là những bài toán có nhiều khả năng nhất không giải được trong P. Do bài toán P = NP vẫn chưa được giải, nếu có thể quy một bài toán NP-đầy đủ, Π₂ về bài toán Π₁ thì chưa có thuật toán thời gian đa thức nào cho Π₁. Bởi vì nếu có thuật toán thời gian đa thức cho Π₁ thì cũng có thuật toán thời gian đa thức cho Π₂. Tương tự như vậy, do mọi bài toán trong NP đều có thể quy về các bài toán NP-đầy đủ, nếu có thể giải được một bài toán NP-đầy đủ trong thời gian đa thức thì P = NP.^[2]

Bài toán P so với NP

Lớp độ phức tạp P thường được xem là mô hình toán học cho các vấn đề tính toán có thuật toán hiệu quả. Giả thuyết này được gọi là luận đề Cobham-Edmonds. Trong khi đó lớp độ phức tạp NP chứa nhiều bài toán quan trọng cần được giải quyết hiệu quả, nhưng vẫn chưa có thuật toán hiệu quả nào, chẳng hạn như bài toán thỏa mãn biểu thức logic, bài toán đường đi Hamilton, và bài toán phủ đỉnh. Do máy Turing đơn định là trường hợp đặc biệt của máy Turing không đơn định, có thể dễ dàng nhận thấy mọi bài toán trong P đều nằm trong NP.

Câu hỏi liệu P có bằng NP hay không là một trong những câu hỏi quan trọng nhất trong lý thuyết khoa học máy tính do tính áp dụng rộng rãi của lời giải.^[2] Nếu câu trả lời là có, thì nhiều bài toán quan trọng có thể được giải quyết hiệu quả. Những bài toán này bao gồm nhiều loại quy hoạch nguyên trong vận trù học, nhiều vấn đề trong hậu cần, dự đoán cấu trúc protein trong sinh học,^[3] và khả năm tìm chứng minh chặt chẽ cho các định lý toán học.^[4] Bài toán P so với NP là một trong những bài toán giải thưởng thiên niên kỷ lựa chọn bởi Viện Toán học Clay. Có một giải thưởng US$1.000.000 cho việc giải quyết bài toán.^[5]

Bài toán trong NP không nằm trong P và không là NP-đầy đủ

Ladner đã chứng minh rằng nếu P ≠ NP thì tồn tại bài toán trong NP không nằm trong P cũng như không là NP-đầy đủ.^[6] Các bài toán như vậy gọi là bài toán NP-trung bình. Bài toán đồ thị đẳng cấu, bài toán tính lôga rời rạc, và bài toán phân tích ra thừa số nguyên tố là các ví dụ của những bài toán được tin là NP-trung bình. Chúng nằm trong số rất ít bài toán trong NP không biết có nằm trong P và cũng không biết có là NP-đầy đủ.

Phân biệt giữa các lớp độ phức tạp khác

Có nhiều lớp độ phức tạp được tin là khác nhau những vẫn chưa được chứng minh. Ví dụ như P ⊆ NP ⊆ PP ⊆ PSPACE và hoàn toàn có thể P=PSPACE. Nếu P không bằng NP thì P không bằng PSPACE. Do có rất nhiều lớp độ phức tạp giữa P và PSPACE, chẳng hạn như RP, BPP, PP, BQP, MA, PH, v.v., hoàn toàn có thể là tất cả các lớp này đều bằng nhau. Chứng minh bất kì hai lớp nào trong số đó là khác nhau sẽ là một bước tiến lớn trong lý thuyết độ phức tạp.

Tương tự như vậy, co-NP là lớp chứa các bài toán phần bù (các bài toán với câu trả lời có/không đảo ngược) của các bài toán trong NP. Người ta tin rằng ^[7] NP không bằng co-NP, nhưng điều này vẫn chưa được chứng minh. Nếu hai lớp này không bằng nhau thì P cũng không bằng NP.

Tương tự như vậy, vẫn chưa biết liệu L (tập hợp các bài toán giải được trong bộ nhớ lôgarit) có bằng P hay không. Có nhiều lớp độ phức tạp nằm giữa hai lớp, chẳng hạn như NL và NC, và vẫn chưa biết liệu chúng bằng nhau hay khác nhau.

P và BPP có nhiều khả năng là bằng nhau. Tuy nhiên hiện vẫn chưa biết liệu BPP có bằng NEXP.

Trước khi có các nghiên cứu chuyên về độ phức tạp tính toán của các thuật toán, nhiều vấn đề cơ sở đã được các nhà nghiên cứu tìm hiểu. Có ảnh hưởng lớn nhất là định nghĩa máy Turing của Alan Turing năm 1936, một định nghĩa rất vững chắc và linh hoạt cho máy tính.

Theo Fortnow & Homer (2003), việc nghiên cứu có hệ thống độ phức tạp tính toán bắt đầu từ bài báo quan trọng mang tên "On the Computational Complexity of Algorithms" của Juris Hartmanis và Richard Stearns (1965). Bài báo này đã đưa ra định nghĩa của độ phức tạp thời gian và bộ nhớ và chứng minh các định lý cấp bậc.

Theo Fortnow & Homer (2003), các bài báo đầu tiên nghiên cứu các bài toán giải được bằng máy Turing với giới hạn tài nguyên bao gồm định nghĩa của John Myhill cho automat giới hạn tuyến tính (Myhill 1960), nghiên cứu của Raymond Smullyan về các tập hợp thô sơ (1961), bài báo của Hisao Yamada về tính toán thời gian thực (1962).^[8] Trước đó, Boris Trakhtenbrot (1956), một nhà nghiên cứu tiên phong trong ngành ở Liên Xô, cũng đã nghiên cứu một thông số độ phức tạp khác.^[9]

Năm 1967, Manuel Blum đã xây dựng các tiên đề cho lý thuyết độ phức tạp và chứng minh một kết quả quan trọng, nay gọi là định lý tăng tốc. Lý thuyết độ phức tạp bắt đầu phát triển mạnh sau khi nhà nghiên cứu Mỹ Stephen Cook và, một cách độc lập, nhà nghiên cứu Liên Xô Leonid Levin, chứng minh rằng tồn tại bài toán có liên hệ thực tế là NP-đầy đủ. Năm 1972, Richard Karp đã đưa ra một bước tiến lớn với bài báo "Reducibility Among Combinatorial Problems", trong đó ông chứng minh 21 bài toán rất khác nhau trong tổ hợp và lý thuyết đồ thị, tất cả đều rất nổi bật về độ khó, là NP-đầy đủ.^[10]

Sách tham khảo

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4 Đã định rõ hơn một tham số trong |author= và |last1= (trợ giúp)
• Du, Ding-Zhu (2000), Theory of Computational Complexity, Ko, Ker-I, John Wiley & Sons, ISBN 978-0-471-34506-0 Đã bỏ qua tham số không rõ |country= (trợ giúp)
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press
• van Leeuwen, Jan biên tập (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Computational Complexity (ấn bản 1), Addison Wesley, ISBN 0201530821
• Sipser, Michael (2006), Introduction to the Theory of Computation (ấn bản 2), USA: Thomson Course Technology, ISBN 0534950973

Bài báo tổng quan

• Khalil, Hatem; Ulery, Dana (1976), A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations, ACM '76 Proceedings of the 1976 Annual Conference, tr. 197, doi:10.1145/800191.805573
• Cook, Stephen (1983), “An overview of computational complexity”, Commun. ACM, ACM, 26 (6): 400–408, doi:10.1145/358141.358144, ISSN 0001-0782
• Fortnow, Lance; Homer, Steven (2003), “A Short History of Computational Complexity” (PDF), Bulletin of the EATCS, 80: 95–133
• Mertens, Stephan (2002), “Computational Complexity for Physicists”, Computing in Science and Engg., Piscataway, NJ, USA: IEEE Educational Activities Department, 4 (3): 31–47, arXiv:cond-mat/0012185, doi:10.1109/5992.998639, ISSN 1521-9615 Đã bỏ qua tham số không rõ |unused_data= (trợ giúp)