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

Lý thuyết độ phức tạp tính toán (tiếng Anh: computational complexity theory) là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng. Ở đây, một vấn đề tính toán được hiểu là một vấn đề có thể giải được bằng máy tính (nói chung có nghĩa là vấn đề có thể được diễn đạt dưới dạng toán học). Một vấn đề tính toán có thể hiểu là một tập các trường hợp và lời giải cho các trường hợp đó. Ví dụ như kiểm tra tính nguyên tố là vấn đề xác định xem một số cho trước có phải số nguyên tố hay không. Mỗi trường hợp của vấn đề là một số tự nhiên, và lời giải cho mỗi trường hợp là có hoặc không tùy theo số đó có là nguyên tố hay không.
Một vấn đề được coi là khó nếu lời giải của nó đòi hỏi nhiều tài nguyên, bất kể sử dụng thuật toán nào. Lý thuyết độ phức tạp tính toán chuyển ý tưởng trực quan này thành mệnh đề toán học chặt chẽ, bằng cách đưa ra các mô hình tính toán để nghiên cứu các vấn đề này và tính lượng tài nguyên cần thiết để giải quyết chúng, chẳng hạn như thời gian hay bộ nhớ. Ngoài ra còn có những tài nguyên khác cũng được sử dụng, chẳng hạn như lượng thông tin liên lạc (dùng trong độ phức tạp truyền thông), số lượng cổng logic trong mạch (dùng trong độ phức tạp mạch) và số lượng bộ xử lý (dùng trong tính toán song song). Một trong những nhiệm vụ của lý thuyết độ phức tạp tính toán là xác định các giới hạn của những gì máy tính có thể làm và không thể làm.
Hai ngành khác trong lý thuyết khoa học máy tính có liên hệ chặt chẽ với độ phức tạp tính toán là phân tích thuật toán và lý thuyết khả tính. Điểm khác biệt mấu chốt giữa phân tích thuật toán và lý thuyết độ phức tạp tính toán là ngành thứ nhất tập trung vào phân tích lượng tài nguyên cần thiết cho một thuật toán nhất định, trong khi ngành thứ hai nghiên cứu các câu hỏi về tất cả các thuật toán có thể dùng để giải quyết vấn đề. Cụ thể hơn, nó tìm cách phân loại các vấn đề theo lượng tài nguyên cần thiết để giải quyết chúng. Việc giới hạn lượng tài nguyên là điểm khác biệt giữa độ phức tạp tính toán và lý thuyết khả tính: lý thuyết khả tính nghiên cứu xem những vấn đề nào có thể giải được về mặt nguyên tắc, mà không giới hạn tài nguyê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.

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.

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.

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 đủ. 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  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.

Lịch sử

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). 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.
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 đủ.