Xem mã nguồn của 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 [[092 183 000 006195 khách hàng 18001090|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.

==Vấn đề (bài toán) 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ó [[tập hợp liên thông|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 tính toán và các thông số độ phức tạp==
===Máy Turing===
[[Hình:Maquina.png|nhỏ|Hình minh họa nghệ thuật cho máy Turing]]
{{chính|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.<ref>Xem {{harvnb|Arora|Barak|2009|loc=Chương 1: The computational model and why it doesn't matter}}</ref>.

===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]].

==Các lớp độ phức tạp==
===Đị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===
[[Hình:Complexity subsets pspace.svg|300px|nhỏ|phải|Quan hệ giữa các lớp độ phức tạp]]
{| class="wikitable"
|-

! Lớp độ phức tạp

! Mô hình tính toán

! Giới hạn tài nguyên
|-
| [[DTIME]](''f''(''n''))
| Máy Turing đơn định
| Thời gian ''f''(''n'')
|-
| [[P (độ phức tạp)|P]]
| Máy Turing đơn định
| Thời gian poly(''n'')
|-
| [[EXPTIME]]
| Máy Turing đơn định
| Thời gian 2<sup>poly(''n'')</sup>
|-
| [[NTIME]](''f''(''n''))
| Máy Turing không đơn định
| Thời gian ''f''(''n'')
|-
| [[NP (độ phức tạp)|NP]]
| Máy Turing không đơn định
| Thời gian poly(''n'')
|-
| [[NEXPTIME]]
| Máy Turing không đơn định
| Thời gian 2<sup>poly(''n'')</sup>
|-
| [[DSPACE]](''f''(''n''))
| Máy Turing đơn định
| Bộ nhớ ''f''(''n'')
|-
| [[L (độ phức tạp)|L]]
| Máy Turing đơn định
| Bộ nhớ O(log ''n'')
|-
| [[PSPACE]]
| Máy Turing đơn định
| Bộ nhớ poly(''n'')
|-
| [[EXPSPACE]]
| Máy Turing đơn định
| Bộ nhớ 2<sup>poly(''n'')</sup>
|-
| [[NSPACE]](''f''(''n''))
| Máy Turing không đơn định
| Bộ nhớ ''f''(''n'')
|-
| [[NL (độ phức tạp)|NL]]
| Máy Turing không đơn định
| Bộ nhớ O(log ''n'')
|-
| [[NPSPACE]]
| Máy Turing không đơn định
| Bộ nhớ poly(''n'')
|-
| [[NEXPSPACE]]
| Máy Turing không đơn định
| Bộ nhớ 2<sup>poly(''n'')</sup>
|}

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 (độ phức tạp)|BPP]], [[ZPP (độ phức tạp)|ZPP]], [[RP (độ phức tạp)|RP]] là các lớp định nghĩa trên [[máy Turing ngẫu nhiên]], [[AC (độ phức tạp)|AC]] và [[NC (độ phức tạp)|NC]] là các lớp định nghĩa trên mạch logic Boole, và [[BQP (độ phức tạp)|BQP]] và [[QMA (độ phức tạp)|QMA]] là các lớp định nghĩa trên máy Turing lượng tử. [[Sharp-P|#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 (độ phức tạp)|IP]] và [[AM (độ phức tạp)|AM]] được định nghĩa thông qua [[hệ thống chứng minh tương tác]]. [[ALL (độ phức tạp)|ALL]] là lớp tất cả các bài toán quyết định.

===Các định lý cấp bậc===
{{chính|định lý cấp bậc thời gian|định lý cấp bậc bộ nhớ}}
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<sup>2</sup>''), 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à
:<math>\operatorname{DTIME}\big(f(n) \big) \subsetneq \operatorname{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.

[[Định lý cấp bậc bộ nhớ]] là
:<math>\operatorname{DSPACE}\big(f(n)\big) \subsetneq \operatorname{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>.

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ề===
{{chính|quy về (độ phức tạp)}}
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 đủ (độ phức tạp)|đầ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 đủ, ''Π<sub>2</sub>'' về bài toán ''Π<sub>1</sub>'' thì chưa có thuật toán thời gian đa thức nào cho ''Π<sub>1</sub>''. Bởi vì nếu có thuật toán thời gian đa thức cho ''Π<sub>1</sub>'' thì cũng có thuật toán thời gian đa thức cho ''Π<sub>2</sub>''. 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.<ref name="Sipser2006"/>

==Các bài toán mở quan trọng==
===Bài toán P so với NP===
{{chính|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.<ref name="Sipser2006">Xem {{harvnb|Sipser|2006|loc= Chương 7: Time complexity}}</ref> 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]],<ref>{{chú thích|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|journal=Journal of Computational Biology|year=1998|volume=5|number=1|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|issue=1|postscript=. }}</ref> và khả năm tìm chứng minh chặt chẽ cho các định lý toán học.<ref>{{chú thích|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|year=2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|access-date=ngày 18 tháng 10 năm 2006|postscript=.|archive-date=2010-12-12|archive-url=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf}}</ref> 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.<ref>{{chú thích|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|access-date = ngày 18 tháng 10 năm 2006 |postscript=.}}</ref>

===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 đủ'''.<ref name="Ladner75">{{chú thích|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|journal=[[Journal of the ACM]] (JACM)|volume=22|year=1975|pages=151&ndash;171|url=http://delivery.acm.org/10.1145/330000/321877/p155-ladner.pdf?key1=321877&key2=7146531911&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618|format=PDF|doi=10.1145/321864.321877|issue=1|postscript=.}}</ref> 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 (độ phức tạp)|'''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ù (độ phức tạp)|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 <ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Khóa học của Boaz Barak về lý thuyết độ phức tạp tính toán] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Bài giảng thứ 2]</ref> '''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 {{Harvtxt|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 {{Harvtxt|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).<ref>{{chú thích tạp chí 
| last1 = Yamada | first1 = H. 
| title = Real-Time Computation and Recursive Functions Not Real-Time Computable 
| journal = IEEE Transactions on Electronic Computers 
| volume = EC-11 
| issue = 6 
| pages = 753–760 
| year = 1962 
| doi = 10.1109/TEC.1962.5219459
}}</ref> 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.<ref>Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski
Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (tiếng Nga)</ref>

Năm 1967, [[Manuel Blum]] đã xây dựng các [[tiên đề Blum|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 Blum|đị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 (toán học)|tổ hợp]] và [[lý thuyết đồ thị]], tất cả đều rất nổi bật về độ khó, là NP-đầy đủ.<ref>{{chú thích | author = Richard M. Karp | chapter = [http://www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems] | title = Complexity of Computer Computations |editor= R. E. Miller and J. W. Thatcher  | publisher = New York: Plenum | pages = 85&ndash;103 | year = 1972}}</ref>

==Ghi chú==
{{Tham khảo}}

===Sách tham khảo===
* {{chú thích
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
| title=Computational Complexity: A Modern Approach
| url = http://www.cs.princeton.edu/theory/complexity/
| publisher=[[Cambridge University Press|Cambridge]]
| year=2009
| isbn=978-0-521-42426-4
| author=Sanjeev Arora, Boaz Barak
}}
* {{chú thích
| last=Du
| first=Ding-Zhu
|others=Ko, Ker-I
| title=Theory of Computational Complexity
| publisher=[[John Wiley & Sons]]
| year=2000
| country=US
| isbn=978-0-471-34506-0
}}
* {{chú thích
| last=Goldreich
| first=Oded
| authorlink=Oded Goldreich
| url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html
| title = Computational Complexity: A Conceptual Perspective
| publisher = Cambridge University Press
| year = 2008
}}
* {{chú thích
| editor1-last=van Leeuwen
| editor1-first=Jan
| editor1-link = Jan van Leeuwen
| title=Handbook of theoretical computer science (vol. A): algorithms and complexity
| publisher=[[MIT Press]]
| isbn=978-0-444-88071-0
| year=1990
}}
* {{chú thích
 | last = Papadimitriou
 | first = Christos
 | authorlink = Christos Papadimitriou
 | title = Computational Complexity
 |edition=1 | year = 1994
 | publisher = Addison Wesley
 | isbn = 0201530821
}}
* {{chú thích
|last=Sipser
|first=Michael
|authorlink=Michael Sipser
|title=[[Introduction to the Theory of Computation]]
|edition=2 |year=2006
|publisher=[[Thomson Learning|Thomson Course Technology]]
|location=USA
|isbn=0534950973
}}

===Bài báo tổng quan===
* {{chú thích | last1=Khalil | first1=Hatem | last2=Ulery | first2=Dana | author2-link=Dana Ulery | title=A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations | publisher=ACM '76 Proceedings of the 1976 Annual Conference | year=1976 | pages=197 | url = http://portal.acm.org/citation.cfm?id=800191.805573 | doi=10.1145/800191.805573}}
* {{chú thích | last1=Cook | first1=Stephen | author1-link=Stephen Cook | title=An overview of computational complexity | publisher=ACM | year=1983 | journal=Commun. ACM | issn=0001-0782 | volume=26 | issue=6 | pages=400–408 | doi=10.1145/358141.358144}}
* {{chú thích | last1=Fortnow | first1=Lance | last2=Homer | first2=Steven | title=A Short History of Computational Complexity | year=2003 | journal=Bulletin of the EATCS | volume=80 | pages=95–133 | url = http://people.cs.uchicago.edu/~fortnow/papers/history.pdf}}
* {{chú thích | last1=Mertens | first1=Stephan | title=Computational Complexity for Physicists | publisher=IEEE Educational Activities Department | location=Piscataway, NJ, USA | year=2002 | journal=Computing in Science and Engg. | issn=1521-9615 | volume=4 | issue=3 | pages=31–47 | doi=10.1109/5992.998639 | arxiv=cond-mat/0012185 | unused_data=arXiv}}

{{refend}}

{{Lớp độ phức tạp}}
{{Khoa học Máy tính}}

[[Thể loại:Lý thuyết độ phức tạp tính toán| ]]
[[Thể loại:Lĩnh vực tính toán học]]