Bài toán lớn nhất của tin học: P và NP

Có 7 bài toán được đánh giá là khó và thú vị đến mức Viện Toán học Clay gọi chúng là các bài toán thiên niên kỉ; ai giải được bài nào sẽ nhận giải thưởng 1 triệu đô la. Một trong số đó liên quan đến tin học và có tên là bài toán P và NP. Ta hãy cùng tìm hiểu bài toán này thực chất nói về điều gì.

Nói thật nhé. Đừng tự dối mình rằng giải thích nó sẽ dễ dàng. Dù sao đây cũng là một bài toán thiên niên kỉ. Vậy hãy đi pha một ấm trà xanh ngon 🍵 rồi ta bắt đầu. Trước hết, ta sẽ xem 4 bài toán khác nhau trong thế giới tin học và thuật toán. Ta sẽ phân tích từng bài và xem chúng liên quan thế nào đến các chữ P và NP.

Bài toán số 1: Tìm số nhỏ nhất

P và NP liên quan đến thuật toán và độ phức tạp của chúng. Hãy tưởng tượng tôi đổ ra trước mặt bạn 100 mẩu giấy, trên mỗi mẩu ghi một số, và nhờ bạn tìm mẩu giấy ghi số nhỏ nhất. Bạn sẽ mất bao lâu?

Nửa phút? 2 phút?

Trong tin học lí thuyết, ta không mấy quan tâm đến những đơn vị thời gian như vậy. Điều ta quan tâm hơn là số phép toán. Vì vậy có thể hỏi theo cách khác: phải kiểm tra bao nhiêu mẩu giấy để chắc chắn đã tìm được số nhỏ nhất? Câu trả lời là phải kiểm tra tất cả các mẩu giấy – vì số nhỏ nhất có thể nằm ở mẩu giấy cuối cùng. Nếu tôi đổ ra 100 mẩu giấy, bạn phải kiểm tra 100 mẩu giấy. Nếu tôi đổ ra 1.000 mẩu, bạn phải kiểm tra 1.000 mẩu. Tổng quát, nếu tôi đổ ra n mẩu giấy, bạn phải kiểm tra n mẩu giấy.

Đây là điều ta gọi là độ phức tạp của thuật toán. Nếu với n mẩu giấy bạn phải thực hiện n phép toán để tìm số nhỏ nhất, thì thuật toán tìm số nhỏ nhất này có độ phức tạp n; ta còn gọi đó là độ phức tạp tuyến tính, vì độ phức tạp được mô tả bằng một hàm số bậc nhất.

Được rồi, bạn đã xem hết 100 mẩu giấy và thông báo rằng số nhỏ nhất là 17. Làm sao tôi kiểm tra được là bạn nói đúng? Không có cách nào khác ngoài việc lại xem hết các mẩu giấy và kiểm tra rằng không mẩu nào ghi số nhỏ hơn. Tức là bạn phải xem n mẩu giấy để tìm số nhỏ nhất, còn tôi, khi muốn kiểm tra, cũng phải làm đúng như vậy. Vậy độ phức tạp của việc kiểm tra kết quả cũng là n, độ phức tạp tuyến tính.

Có thuật toán nào mà kiểm tra kết quả lại dễ hơn tìm ra kết quả không?

Bài toán số 2: Tích của một cặp số

Hãy tưởng tượng tôi đổ ra trước mặt bạn hai chồng mẩu giấy có số mẩu bằng nhau, trên mỗi mẩu lại ghi một số. Tôi nhờ bạn tìm một số trong chồng A và một số trong chồng B sao cho tích của chúng bằng 918. Ví dụ, cho hai chồng số sau:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

Làm sao tìm được cặp số có tích bằng 918? Đơn giản là thử mọi khả năng. Có bao nhiêu khả năng? Khá nhiều: 25 khả năng. Ta bắt đầu bằng cách nhân số đầu tiên trong chồng A, tức là số 49, với từng số trong chồng B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Không cặp nào cho tích 918. Vậy ta làm tương tự với các số còn lại trong chồng A, tức là 5 cặp nữa với số 11, 5 cặp nữa với số 32, 5 cặp nữa với số 54 và 5 cặp cuối cùng với số 15. Tổng cộng có thể thử 25 cặp số. Cuối cùng ta thấy 54 · 17 = 918.

Độ phức tạp của thuật toán này là bao nhiêu? Ta quan tâm đến việc phải nhân bao nhiêu cặp số. Mỗi chồng có 5 mẩu giấy, và ta phải thử từng số trong 5 số của chồng thứ nhất với từng số trong 5 số của chồng thứ hai. Tổng cộng ta đã thử 5 · 5 = 25 cặp. Nếu tôi đổ ra hai chồng, mỗi chồng 10 mẩu giấy, bạn sẽ phải thử 10 · 10 = 100 cặp. Tổng quát, nếu tôi đổ ra hai chồng, mỗi chồng n mẩu giấy, bạn phải thử n · n = n² cặp.

Ta nói thuật toán này có độ phức tạp n², độ phức tạp bậc hai, vì nó được mô tả bằng một hàm số bậc hai.

Nhưng kiểm tra kết quả thì phức tạp đến mức nào? Nếu bạn trả lời rằng 54 và 17 là hai số có tích bằng 918, tôi không cần xem lại mọi cặp số từ hai chồng như bạn đã phải làm. Tôi chỉ cần nhân đúng một cặp 54 · 17 là biết bạn nói đúng hay sai. Như vậy, để giải bài toán này cần tính tới n² tích, còn để kiểm tra thì chỉ cần tính 1 tích. Việc kiểm tra có độ phức tạp hằng, bằng 1.

Đây là điểm khác biệt lớn so với bài toán trước, nơi việc tính toán và việc kiểm tra cần số bước như nhau.

Bài toán này cũng phức tạp hơn bài toán trước nhiều bậc. Nếu tôi đổ ra trước mặt bạn 10 nghìn mẩu giấy và nhờ tìm số nhỏ nhất, có lẽ bạn sẽ tìm được trong một ngày. Nhưng nếu tôi đổ ra hai chồng, mỗi chồng 10 nghìn mẩu giấy, và nhờ bạn tìm tích, bạn sẽ phải kiểm tra 10 nghìn nhân 10 nghìn tích, tức là 100 triệu phép tính. Dù mỗi giây bạn thử được một tích thì cũng mất khoảng 3 năm.

Bài toán số 3: Tổng tập con

Ta hãy xem bài toán thứ ba. Lần này tôi đổ ra trước mặt bạn 12 mẩu giấy ghi số và nhờ bạn tìm một nhóm mẩu giấy (số lượng tuỳ ý) có tổng các số bằng 0. Ví dụ:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Hãy chọn trong các số này một nhóm số bất kì có tổng bằng 0. Chẳng hạn các số

$24 + 48 - 69 + 1$

có tổng bằng 4, nên không phải là câu trả lời đúng. Câu trả lời đúng là nhóm số… mà bạn biết không? Hãy tự tìm, coi như bài tập về nhà 😉. Chỉ có đúng một nhóm số có tổng bằng 0. Ít ra bạn sẽ tự thấy bài toán này khó đến mức nào.

Bây giờ ta cần biết độ phức tạp của bài toán này. Phép tính này không còn quá đơn giản và dành cho những ai thực sự thích thú. Nếu bạn muốn biết cách tính độ phức tạp của bài toán này, hãy đọc tiếp. Nếu không, có thể bỏ qua sang phần sau. ⏩

Vậy làm sao tìm được nhóm số có tổng bằng 0? Đơn giản là phải thử mọi tổ hợp số có thể. Phải thử mọi cặp số, mọi bộ ba, bộ bốn, bộ năm, v.v., và với mỗi nhóm phải kiểm tra tổng có bằng 0 không. Có bao nhiêu nhóm như vậy?

Ta xét trên một tập hợp số nhỏ hơn. Từ bộ ba số B = {5, 7, 9} có thể lập được bao nhiêu nhóm số khác nhau, hay nói cách khác, bao nhiêu tập con? Có tất cả 8 tập con:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Lưu ý rằng ta đã tính cả tập rỗng B₁. Lúc này nó không có ích lắm, nhưng cho đầy đủ ta vẫn giữ lại. Để tính cho đơn giản, ta gán cho mỗi tập con một vectơ nhị phân. Vectơ nhị phân đơn giản là một dãy các chữ số 0 và 1, chẳng hạn 00101010. Ta sẽ làm việc với các vectơ nhị phân độ dài 3. Ta gán như sau: vectơ 101 được gán cho tập con chứa “số thứ nhất và số thứ ba của tập ban đầu, nhưng không chứa số thứ hai”, tức là tập {5, 9}. Vectơ 110 được gán cho tập con chứa “số thứ nhất và số thứ hai của tập ban đầu, nhưng không chứa số thứ ba”, tức là tập {5, 7}, v.v.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

Ta thấy mỗi tập con có đúng một vectơ nhị phân độ dài 3. Và mỗi vectơ nhị phân độ dài 3 ứng với đúng một tập con. Vì vậy, nếu tính được có bao nhiêu vectơ nhị phân khác nhau độ dài n, ta sẽ biết có thể lập được bao nhiêu nhóm khác nhau từ n số cho trước. Ta hãy tính số đó.

Có 2 vectơ nhị phân độ dài 1: 0 và 1.

Các vectơ nhị phân độ dài 2 nhận được bằng cách lấy mọi vectơ nhị phân độ dài 1 và thêm 0 vào cuối mỗi vectơ: ta được các vectơ 00 và 10. Lại lấy mọi vectơ độ dài 1 và thêm 1 vào cuối: 01 và 11. Như vậy ta được mọi vectơ độ dài 2: 00, 01, 10 và 11.

Các vectơ nhị phân độ dài 3 nhận được bằng cách lấy mọi vectơ nhị phân độ dài 2 và thêm vào cuối chữ số 0: 000, 010, 100 và 110, và chữ số 1: 001, 011, 101 và 111.

Cứ như vậy với mỗi độ dài tiếp theo. Ta thấy khi độ dài vectơ nhị phân tăng thêm 1, số vectơ nhị phân khác nhau tăng gấp đôi. Với độ dài 4, ta sẽ có tất cả 2 · 2 · 2 · 2, tức là 16, nhóm khác nhau.

Tổng quát, nếu tập hợp M có n phần tử thì số tập con của M bằng số vectơ nhị phân khác nhau độ dài n, và bằng

$\underset{n thừa số}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ hay n² – chẳng phải như nhau sao? 🤷‍♂

Vậy từ một tập hợp n số có thể lập được 2ⁿ tập con khác nhau. Ở đây ta có n = 12 số, nên phải kiểm tra 2¹² nhóm khác nhau, tức là 4096 nhóm. Ta nói bài toán này có độ phức tạp 2ⁿ, độ phức tạp mũ, vì nó được mô tả bằng một hàm số mũ.

Lưu ý rằng bài toán trước có độ phức tạp n², còn bài này có độ phức tạp 2ⁿ. Trông rất giống nhau, phải không? Nhưng số mũ là hằng số hay là biến n thì khác nhau rất nhiều. Hãy để ý rằng khi n = 4, ta được

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Được rồi, đến đây kết quả vẫn bằng nhau. Còn khi n = 10 thì sao?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Ồ, hàm số mũ vọt lên và bỗng lớn hơn hàm số bậc hai khoảng 10 lần. Với n = 20 thì được bao nhiêu?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

Với n = 20, độ phức tạp mũ có giá trị lớn hơn độ phức tạp bậc hai khoảng 2.600 lần. Vậy ta thấy hàm số mũ tăng nhanh hơn rất nhiều so với hàm số bậc hai. Hãy nhớ điều này khi lại có một đại dịch lây lan trong dân số với tốc độ theo hàm mũ.

Như vậy, nếu tôi đổ ra trước mặt bạn 20 mẩu giấy, bạn sẽ phải kiểm tra 1.048.576 nhóm. Khá nhiều đấy.

Kiểm tra kết quả như thế nào?

Tôi sẽ mất bao lâu để kiểm tra rằng nhóm số tìm được thực sự có tổng bằng 0? Việc này khá nhanh: tôi chỉ cần cộng các số trong nhóm đó; nếu tổng bằng 0 thì bạn đã tìm đúng nhóm mẩu giấy, nếu tổng khác 0 thì bạn đã tìm sai.

Một lần nữa ta thấy kiểm tra kết quả dễ hơn tìm ra kết quả rất nhiều bậc.

Bài toán số 4: Bài toán người du lịch

Bài toán người du lịch là một trong những bài toán thuật toán nổi tiếng nhất. Nói đại khái, có một người bán hàng rong chuyên bán… mưa. Người này phải đi rất nhiều nơi để kiếm sống. Vì vậy anh ta quyết định ghé thăm 14 thành phố lớn ở Việt Nam. Vì không muốn lãng phí, anh ta muốn tìm con đường ngắn nhất đi qua tất cả 14 thành phố này. Nhiệm vụ của ta là tìm con đường ngắn nhất đó.

Làm sao tìm được con đường ngắn nhất này? Thử mọi khả năng.

Ta có thể đơn giản hoá bài toán. Giả sử giữa hai thành phố bất kì có đúng một con đường ngắn nhất. Làm sao tìm được con đường ngắn nhất qua tất cả các thành phố? Có 14 thành phố, nên có 14 cách chọn điểm xuất phát. Giả sử ta xuất phát từ Hà Nội. Từ Hà Nội có thể đi đâu? Về lí thuyết có thể đi đến bất kì thành phố nào khác. Vậy ta có thể chọn một trong 13 thành phố còn lại.

Ngay bây giờ ta đã tính được có tất cả 14 · 13 cách ghé thăm hai thành phố đầu tiên – có 14 cách chọn điểm xuất phát, sau đó có 13 thành phố còn lại để chọn.

Khi đến thành phố thứ hai, ta phải đi tiếp. Ta đã đến hai thành phố, nên có thể đi đến một trong 12 thành phố còn lại. Vậy có tất cả 14 · 13 · 12 cách ghé thăm ba thành phố đầu tiên.

Khi đã ghé thành phố thứ ba, ta phải chọn một trong 11 thành phố còn lại, rồi một trong 10 thành phố còn lại, v.v.

Khi đã ghé thăm hết, ta sẽ thấy mình có tất cả

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

khả năng để lựa chọn. Điều này có thể làm bạn nhớ đến giai thừa, kí hiệu bằng dấu chấm than. Vậy có thể nói tích này bằng 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

do đó có 14! con đường đi qua tất cả 14 thành phố. Như vậy có nhiều không? Khá nhiều, vì

$14! = 87 178 291 200.$

Tổng quát, nếu tìm con đường ngắn nhất qua n thành phố, ta phải thử n! con đường khác nhau. Vậy độ phức tạp của cách giải này là n!.

Làm sao ta kiểm tra được rằng đã tìm ra kết quả đúng? Nếu bạn nói với tôi rằng con đường ngắn nhất là từ Hải Phòng đến Hà Nội, rồi đến Đà Nẵng, v.v., làm sao tôi kiểm tra được bạn nói đúng? Khá khó đấy 🤷‍♂. Vì nhìn vào con đường đó, tôi không có cách nào dễ dàng để biết nó có đúng là ngắn nhất không. Thực ra tôi phải làm lại toàn bộ phép tính. Vậy việc kiểm tra kết quả cũng có độ phức tạp n!.

Lớp P và lớp NP

Ta đã xem 4 bài toán và các thuật toán giải chúng, đồng thời phân tích xem tìm ra lời giải phức tạp đến mức nào và kiểm tra lời giải phức tạp đến mức nào. Có thể tóm tắt trong bảng sau:

Bài toán	Độ phức tạp khi giải	Độ phức tạp khi kiểm tra
Số nhỏ nhất	n	n
Tích của một cặp số	n²	1
Tổng tập con	2ⁿ	n
Người du lịch	n!	n!

Bây giờ ta chia các bài toán thành hai nhóm. Nhóm thứ nhất gồm các bài toán dễ giải. Đó là những bài toán giải được với độ phức tạp n, n², n³, n⁴, v.v. Vì những biểu thức như n² được gọi là đa thức (polynomial), lớp bài toán này được kí hiệu bằng chữ P. Như vậy, lớp P gồm các bài toán giải được trong thời gian đa thức (tức là có độ phức tạp, chẳng hạn, n² hay n⁷). Nói chung, đó là những bài toán giải được tương đối dễ dàng.

Như vậy, lớp P chứa bài toán số 1, tìm số nhỏ nhất, vì nó có độ phức tạp khi giải là n, và bài toán số 2, tích của một cặp số, vì độ phức tạp khi giải là n²; cả hai đều là đa thức.

Lớp thứ hai là lớp NP. Lớp này gồm các bài toán mà lời giải kiểm tra được trong thời gian đa thức. Vậy lớp NP chứa mọi bài toán ở trên, trừ bài toán cuối cùng. Ta không biết cách kiểm tra lời giải của bài toán người du lịch trong thời gian đa thức. Ba bài toán trước thì kiểm tra được trong thời gian đa thức.

Bài toán người du lịch thì ta không biết cách giải, cũng không biết cách kiểm tra trong thời gian đa thức. Vì vậy với bài toán người du lịch, ta sẽ cần thêm một lớp nữa, chứa những bài toán còn khó hơn. Lớp đó có tồn tại, nhưng lúc này không cần quan tâm.

Rõ ràng lớp P là tập con của lớp NP. Tức là mọi bài toán thuộc lớp P cũng thuộc lớp NP. Điều này hợp lí – nếu ta giải được một bài toán trong thời gian đa thức thì cũng kiểm tra được kết quả trong thời gian đa thức.

Bài toán P và NP

Điều ngược lại có đúng không? Mọi bài toán thuộc lớp NP có cũng thuộc lớp P không? Tức là, nếu có cách kiểm tra lời giải của một bài toán trong thời gian đa thức, thì có tồn tại thuật toán giải bài toán đó trong thời gian đa thức không?

Ví dụ, ta biết rằng có thể kiểm tra lời giải của bài toán số 3, tổng tập con, trong thời gian đa thức. Nhưng để giải nó, ta đã dùng một thuật toán không phải đa thức: thuật toán đó có độ phức tạp mũ 2ⁿ. Liệu ta có biết chắc rằng bài toán này không có thuật toán nào với độ phức tạp đa thức không?

Không biết!

Rất có thể với mọi bài toán mà lời giải kiểm tra được trong thời gian đa thức, đều tồn tại thuật toán giải nó trong thời gian đa thức. Ta không biết. Ta không chứng minh được sự tồn tại của một thuật toán như vậy, nhưng cũng không bác bỏ được.

Nếu với mọi bài toán thuộc lớp NP đều có thuật toán giải nó trong thời gian đa thức, thì lớp NP thực ra sẽ trùng với lớp P. Mọi bài toán thuộc lớp P đều thuộc lớp NP và mọi bài toán thuộc lớp NP đều thuộc lớp P – hai lớp bằng nhau, trùng nhau.

Vậy bài toán P và NP là câu hỏi: lớp P có trùng với lớp NP không, hay đó là hai lớp bài toán khác nhau?

Hoặc P = NP, hoặc P ≠ NP. Không ai biết câu trả lời, và nếu bạn tìm ra, bạn sẽ nhận giải thưởng 1 triệu đô la, vinh quang bất diệt và có lẽ cả giải Turing – một giải thưởng được ví như giải Nobel của ngành tin học.

Điều gì sẽ xảy ra nếu P = NP?

Điều gì sẽ xảy ra nếu P = NP? Thật ra không dễ nói trước. Ta sẽ biết rằng mọi bài toán thuộc lớp NP đều có thuật toán giải trong thời gian đa thức. Chẳng hạn, bài toán số 3, tổng tập con, có thuật toán giải trong thời gian đa thức. Nhưng có ba điều cần lưu ý:

Biết rằng một thuật toán như vậy tồn tại không có nghĩa là ta tìm được nó. Ta chỉ biết rằng có, tồn tại một thuật toán giải bài toán trong thời gian đa thức, nhưng có thể còn 100 năm nữa ta vẫn chưa xây dựng được nó. Điều này cũng giống như thuyết tương đối rộng đã tiên đoán sự tồn tại của lỗ đen, nhưng phải mất thêm vài chục năm nữa ta mới chụp được “bức ảnh” đầu tiên của một lỗ đen.
Tiếc là thuật toán chạy trong thời gian đa thức chưa chắc đã nhanh. Ta có thể tìm được một thuật toán có độ phức tạp n¹⁰⁰. Bởi vì biểu thức n¹⁰⁰ cũng là một đa thức. So sánh độ phức tạp 2ⁿ và n¹⁰⁰, ta sẽ thấy rằng khi n còn tương đối nhỏ, thuật toán có độ phức tạp 2ⁿ vẫn cần ít phép toán hơn. Chẳng hạn, với n = 20 ta có 2²⁰ = 1.048.576, trong khi biểu thức 20¹⁰⁰ là một số có khoảng 130 chữ số, lớn hơn 1.048.576 khoảng 120 bậc. Vì vậy, trong thực tế, thuật toán đa thức của ta sẽ chậm hơn thuật toán mũ. Ít ra là khi n còn tương đối nhỏ.
Nếu ta thực sự tìm được một thuật toán nhanh chạy trong thời gian đa thức, ta có thể giải nhiều bài toán nhanh hơn và chính xác hơn. Tất nhiên đó là tin tốt, nhưng cũng có mặt trái. Có một lĩnh vực dựa vào việc một số bài toán rất khó giải, đó là mật mã học – mã hoá thông tin. Khi đó có thể việc phá các hệ mật mã hiện nay sẽ trở nên dễ dàng hơn rất nhiều bậc.

Ngoài lề một chút: vì bạn đã đọc đến tận đây, tôi xin tiết lộ phần thưởng: lời giải của bài toán số 3 là 24 + 1 − 60 + 16 − 83 + 48 + 54.

Điều gì sẽ xảy ra nếu P ≠ NP?

Nếu hai lớp bài toán P và NP khác nhau thì cũng không có gì thay đổi nhiều, vì đó gần như là hiện trạng. Hiện nay ta không có thuật toán nào giải một bài toán khó thuộc NP trong thời gian đa thức, và nếu có ai chứng minh được P ≠ NP thì điều đó đơn giản sẽ mãi mãi như vậy. Một chứng minh rằng P = NP mới thực sự là một sự kiện chấn động.

Trong văn hoá đại chúng

Trong một tập phim hoạt hình The Simpsons, Homer lạc vào một thực tại khác, nơi anh ta thấy dòng chữ P = NP. Có thể xem trên youtube.com.
Còn trong phim Futurama, ta thấy trong một nhà kho có hai tập hồ sơ, một tập tên là P và một tập tên là NP. Có thể xem trên youtube.com.
Tập 2 của mùa 2 phim truyền hình Mỹ Elementary, có tên “Solve for X”, kể về vụ án mạng một nhà toán học có lẽ đã giải được bài toán P và NP.

« Bài trước: 1 + 2 + 5 · 0 bằng bao nhiêu? Thứ tự thực hiện phép tính

Bài tiếp: Phương pháp cộng nhanh Trachtenberg »