Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English

Sổ tay nghiên cứu 01 · ngày 9 tháng 9 năm 2026

P vs NP:
một sổ tay nghiên cứu.

Một công thức có thể lớn lên theo hàm mũ trong khi bài toán nó mô tả vẫn dễ. Cuộc khảo sát đầu tiên của chúng tôi cho thấy chính xác điều đó xảy ra như thế nào, và vì sao sự phân biệt này quan trọng.

P vs NP vẫn chưa được giải quyết. Sổ tay này tái hiện một kết quả đã được thiết lập. Nó không chứa lời giải nào được tuyên bố, cũng không có cận dưới mới nào cho tính toán tổng quát.

Giải quyết P vs NP đòi hỏi những gì?

P gồm các bài toán quyết định mà một thuật toán tất định giải được trong thời gian bị chặn bởi một đa thức theo độ dài đầu vào. NP gồm các bài toán quyết định mà câu trả lời “có” có chứng chỉ độ dài đa thức, và một thuật toán tất định có thể kiểm chứng trong thời gian đa thức. Mọi bài toán trong P đều thuộc NP; chiều ngược lại có đúng hay không vẫn còn bỏ ngỏ.

Một mục tiêu cụ thể là SAT: cho một công thức Boolean, có phép gán đúng và sai nào làm nó đúng không? SAT là NP-đầy đủ. Một thuật toán tất định đúng đắn cho mọi thể hiện của SAT, với cận thời gian trường hợp xấu nhất dạng đa thức đã được chứng minh, sẽ xác lập P = NP. Chứng minh rằng không có thuật toán như vậy sẽ xác lập P ≠ NP. Độ dài đầu vào là độ dài của toàn bộ công thức đã được mã hóa, và số mũ của đa thức phải cố định. Mô tả bài toán chính thức của Stephen Cook đưa ra khung hình thức.

Chúng tôi bắt đầu với một chiến lược hẹp hơn mà chúng tôi thực sự phân tích được: loại bỏ các biến tạm khỏi một công thức ngắn và biểu diễn điều kiện còn lại dưới dạng một danh sách mệnh đề. Danh sách đó có luôn giữ được nhỏ không?

Ba ý tưởng cho cuộc khảo sát này

Tính chẵn lẻ
Số lượng bit 1 là chẵn hay lẻ. XOR, viết là ⊕, theo dõi điều này: 0 ⊕ 1 = 1 và 1 ⊕ 1 = 0.
CNF
Một phép hội (AND) của các mệnh đề. Mỗi mệnh đề là một phép tuyển (OR) của các literal như x hoặc ¬x. Mọi mệnh đề đều phải đúng. Ví dụ: (x ∨ y) ∧ (¬x ∨ z).
Biến phụ trợ
Một biến Boolean tạm thời ghi lại một kết quả trung gian. Loại bỏ nó nghĩa là hỏi xem có cách đặt giá trị nào cho biến đó làm công thức đúng hay không, chứ không đơn giản là xóa mọi mệnh đề có nhắc đến nó.

Xét n bit, từ x₁ đến xₙ. Ta yêu cầu tính chẵn lẻ của chúng bằng một bit đích b: x₁ ⊕ ⋯ ⊕ xₙ = b. Một nửa số phép gán thỏa mãn mỗi giá trị đích. Với một phép gán cho trước, kiểm tra điều kiện này chỉ cần một lượt duyệt qua các bit.

Thử xem: đổi các bit, rồi đổi kích thước

Ví dụ tương tác · sáu bit

Có số lẻ bit 1 không?

Bật hoặc tắt một bit để đổi phép gán. XOR chạy dồn chỉ cần một bit bộ nhớ làm việc.

3 bit 1 → tính chẵn lẻ lẻ → điều kiện được thỏa mãn.

XOR chạy dồn: 0 → 1 → 1 → 0 → 1 → 1

Đây là một ràng buộc chẵn lẻ. SAT tổng quát cho phép những tổ hợp ràng buộc phức tạp hơn nhiều.

Hai cách mô tả cùng một điều kiện

Điều gì xảy ra khi ta loại bỏ các biến trợ giúp?

Có biến trợ giúp77mệnh đề trong chuỗi XOR của chúng tôi · 4n − 3
Không có biến trợ giúp524,288số mệnh đề CNF tối thiểu · 2ⁿ⁻¹

Số lượng chính xác được tính từ các công thức đã chứng minh, không phải thời gian chạy đo được. Chúng tôi chỉ dựng và kiểm tra tường minh các thể hiện đến n = 10. Cách mã hóa dùng biến trợ giúp là một cách dựng thuận tiện, không phải một tuyên bố về tính tối ưu.

Kết quả, kèm một chứng minh đầy đủ

Định lý đã được thiết lập · được tái hiện ở đây

Với n ≥ 1 và b ∈ {0, 1}, mọi CNF chỉ trên x₁, …, xₙ mà thôi biểu diễn x₁ ⊕ ⋯ ⊕ xₙ = b đều cần ít nhất 2ⁿ⁻¹ mệnh đề. Cận này đạt được.

Cận này là kết quả chuẩn; nó được phát biểu trong Emdin, Kulikov, Mihajlin và Slezkin, CNF Encodings of Parity (MFCS 2022). Bài báo của họ nghiên cứu các đánh đổi mạnh hơn khi cho phép biến phụ trợ. Dưới đây là một lập luận sơ cấp cho trường hợp không có biến phụ trợ.

  1. Mọi mệnh đề hữu ích đều phải nhắc đến mọi biến. Loại bỏ các literal trùng lặp và bỏ qua các mệnh đề hằng đúng chứa cả một biến lẫn phủ định của nó. Giả sử một mệnh đề còn lại bỏ sót xⱼ. Đặt các biến được nhắc đến sao cho mọi literal trong mệnh đề đều sai. Đặt các biến bị bỏ sót khác một cách tùy ý, rồi chọn xⱼ để tính chẵn lẻ tổng bằng b. Phép gán này thỏa mãn điều kiện chẵn lẻ nhưng làm sai mệnh đề, mâu thuẫn. Vậy mọi mệnh đề không phải hằng đúng đều có đủ n biến.
  2. Mỗi mệnh đề như vậy loại trừ đúng một phép gán. Một mệnh đề chứa mỗi biến đúng một lần chỉ sai khi mọi literal của nó đều sai. Chỉ có đúng một cách chọn n bit làm được điều đó.
  3. Có 2ⁿ⁻¹ phép gán cần loại trừ. Đảo bit đầu tiên ghép mỗi phép gán có tính chẵn lẻ chẵn với một phép gán có tính chẵn lẻ lẻ. Đúng một nửa trong 2ⁿ phép gán có tính chẵn lẻ sai. Vì một mệnh đề hữu ích chỉ loại trừ một phép gán, cần ít nhất 2ⁿ⁻¹ mệnh đề.
  4. Chừng đó mệnh đề là đủ. Với mỗi phép gán có tính chẵn lẻ sai, đưa vào mệnh đề chỉ sai tại đúng phép gán đó: dùng xᵢ khi bit của nó là 0 và ¬xᵢ khi bit của nó là 1. Phép hội của chúng loại bỏ mọi phép gán sai và chỉ những phép gán sai. Điều này cho đúng 2ⁿ⁻¹ mệnh đề. ∎

Đây là chứng minh cho n tùy ý. Các thí nghiệm bên dưới kiểm tra phần triển khai trên một số hữu hạn các thể hiện; chúng không phải là lý do định lý đúng với mọi n.

Một mô tả ngắn dùng biến tạm

Với n ≥ 2, đưa vào z₂, …, zₙ và yêu cầu:

z₂ = x₁ ⊕ x₂
zᵢ = zᵢ₋₁ ⊕ xᵢ   với 3 ≤ i ≤ n
zₙ = b

Mỗi quan hệ z = a ⊕ c có thể được biểu diễn bằng bốn mệnh đề:

(a ∨ c ∨ ¬z) ∧ (a ∨ ¬c ∨ z)
∧ (¬a ∨ c ∨ z) ∧ (¬a ∨ ¬c ∨ ¬z)

Bốn mệnh đề này loại trừ đúng bốn hàng sai của bảng chân trị ba biến. Điều kiện cuối zₙ = b là một mệnh đề đơn vị. Có n − 1 cổng XOR, nên cách mã hóa của chúng tôi có n − 1 biến trợ giúp, 4n − 3 mệnh đề và 12n − 11 lần xuất hiện của literal. Mỗi mệnh đề có tối đa ba literal. Đây là một ứng dụng chuẩn của cách mã hóa kiểu Tseitin.

Với mọi phép gán cho các bit ban đầu, các quan hệ cổng buộc ra một dãy giá trị trợ giúp duy nhất. Dãy đó thỏa mãn mệnh đề đơn vị cuối khi và chỉ khi tính chẵn lẻ ban đầu là b. Vậy:

∃z₂ ⋯ ∃zₙ Fₙ,ᵦ(x, z)  ⇔  x₁ ⊕ ⋯ ⊕ xₙ = b.

Do đó, loại bỏ mọi biến trợ giúp mà vẫn đòi hỏi một CNF tường minh tương đương trên các bit ban đầu buộc phải có 2ⁿ⁻¹ mệnh đề, mỗi mệnh đề có n literal. Đây là chi phí kích thước đầu ra không thể tránh được đối với phép biến đổi cụ thể này.

Thí nghiệm đã kiểm chứng điều gì

Chúng tôi cài đặt phép loại bỏ lượng từ tồn tại bằng quy tắc phân giải Davis–Putnam. Với một biến z, kết hợp mọi mệnh đề chứa z với mọi mệnh đề chứa ¬z, bỏ z khỏi các mệnh đề phân giải, rồi loại các hằng đúng và các mệnh đề trùng lặp. Những mệnh đề không bao giờ nhắc đến z được giữ lại.

Với n = 2 đến 10 và cả hai giá trị đích của tính chẵn lẻ, chúng tôi loại bỏ các biến trợ giúp theo thứ tự xuôi, ngược và một thứ tự xáo trộn có thể tái hiện. Cả 54 lần chạy đều cho ra đúng CNF chẵn lẻ trực tiếp. Các phép kiểm tra bảng chân trị độc lập xác minh đầu ra; các phép kiểm tra vét cạn nhỏ hơn liệt kê các phép gán biến trợ giúp và mọi mệnh đề không phải hằng đúng có thể có.

Số mệnh đề chính xác. Cách mã hóa dùng biến trợ giúp của chúng tôi có thể lớn hơn với đầu vào nhỏ.
Số bit ban đầu nCách mã hóa dùng biến trợ giúp của chúng tôiCNF không có biến trợ giúpXác minh
252Đã dựng và kiểm tra
4138Đã dựng và kiểm tra
62132Đã dựng và kiểm tra
829128Đã dựng và kiểm tra
1037512Đã dựng và kiểm tra
2077524,288Chỉ suy ra từ định lý
40157549,755,813,888Chỉ suy ra từ định lý

Các kích thước ở trên là số mệnh đề, không phải thời gian thực thi. Với định danh biến dạng nhị phân, kích thước mã hóa theo bit của công thức dùng biến trợ giúp là O(n log n). CNF trực tiếp có n·2ⁿ⁻¹ lần xuất hiện của literal. Sự bùng nổ là theo hàm mũ đối với số biến ban đầu n và siêu đa thức đối với độ dài mã hóa đầu vào; không nên lẳng lặng đánh đồng hai đại lượng này.

Vì sao điều này không giải quyết được P vs NP

Chúng tôi đã chặn một cách biểu diễn, không phải mọi phép tính có thể có. Một thuật toán quyết định SAT được phép chỉ trả về có hoặc không. Nó không cần tạo ra CNF chiếu, xóa các biến trợ giúp, hay dùng mệnh đề ở bên trong.

Thật vậy, họ bài kiểm tra của chính chúng tôi là dễ. Kiểm tra một phép gán dùng n − 1 phép XOR. Khi không có bit đầu vào nào được cố định, việc tìm một phép gán thỏa mãn cho cả hai giá trị chẵn lẻ là tức thì: đặt mọi bit bằng 0 cho tính chẵn lẻ chẵn, hoặc đặt một bit bằng 1 cho tính chẵn lẻ lẻ. Các hệ phương trình XOR cũng có thể giải bằng phép khử trên trường hai phần tử. Một lập luận kết luận rằng “tính chẵn lẻ cần một CNF khổng lồ, nên tính chẵn lẻ đòi hỏi tính toán khổng lồ” sẽ thất bại trên ví dụ này.

Những gì chúng ta có thể kết luận

Chiến lược “luôn loại bỏ mọi biến phụ trợ để có một CNF tường minh nhỏ tương đương” không thể thành công trong trường hợp tổng quát. Họ công thức ở trên là một phản ví dụ, dù mỗi đầu vào là một công thức ngắn, thỏa mãn được, với các mệnh đề có độ rộng tối đa ba.

Những gì còn bỏ ngỏ: liệu các thể hiện SAT tùy ý có thuật toán quyết định thời gian đa thức hay không. Sổ tay này không xác lập P = NP cũng không xác lập P ≠ NP, và không tuyên bố một định lý mới được khám phá.

Điều một chứng minh tương lai phải đối mặt

Cũng có những giới hạn chặt chẽ đối với các kỹ thuật chứng minh rộng. Chúng ràng buộc các hướng tiếp cận; chúng không chứng minh rằng bài toán không thể giải được.

  • Tương đối hóa (relativization). Có những thiết lập oracle trong đó P = NP và những thiết lập khác trong đó P ≠ NP. Một lập luận áp dụng nguyên vẹn tương đối với mọi oracle không thể giải quyết bài toán gốc. Baker, Gill và Solovay (1975).
  • Chứng minh tự nhiên (natural proofs). Với giả định tồn tại các hàm giả ngẫu nhiên đủ mạnh, một lớp rộng các tính chất nhận biết được hiệu quả và đủ phổ biến không thể chứng minh các cận dưới mạch tổng quát mong muốn. Rào cản này có điều kiện và có một định nghĩa cụ thể về “tự nhiên”. Razborov và Rudich (1997).
  • Đại số hóa (algebrization). Ngay cả một số kỹ thuật dùng đại số để vượt ra ngoài các lập luận oracle thông thường vẫn không đủ. Việc giải quyết P vs NP cần một phương pháp nằm ngoài rào cản hình thức này. Aaronson và Wigderson (2009).

Vượt qua một rào cản tự nó chưa phải là một chứng minh. Một lời giải được đề xuất vẫn cần mọi bổ đề được biện minh và kết luận của nó được đối chiếu với mô hình tính toán thực tế.

Tái hiện các phép kiểm tra

Thí nghiệm dùng Python 3.10 trở lên và chỉ dùng thư viện chuẩn. Tải tập lệnh xuống, rồi chạy:

python experiment.py --output results.json

Kết quả mong đợi: status: passed, 18 thể hiện chẵn lẻ và 54 lần chạy loại bỏ. Kết quả bao gồm mã băm SHA-256 của tập lệnh, các hạt giống ngẫu nhiên cố định, số lượng kích thước chính xác, và các khoảng riêng cho từng phép kiểm tra vét cạn. Tập lệnh không truy cập mạng và chỉ ghi tệp kết quả được yêu cầu.

Bộ kiểm thử cũng đối chiếu thủ tục loại bỏ với phép lượng từ tồn tại bằng vét cạn trên 300 công thức nhỏ có hạt giống, bao gồm công thức rỗng, mệnh đề rỗng và các biến không xuất hiện trong mệnh đề. Điều này giúp phát hiện lỗi cài đặt mà chỉ kiểm tra số mệnh đề sẽ bỏ sót.

Cuộc khảo sát sẽ đi đâu tiếp theo

Mục tiêu dài hạn của chúng tôi là một lời giải chặt chẽ cho P vs NP. Cột mốc đầu tiên này bác bỏ một tuyên bố không giới hạn về phép chiếu CNF và thiết lập một cách có thể tái hiện để xem xét các tuyên bố tương tự.

  1. Đặc tả chính xác một phương pháp được đề xuất. Nêu cách biểu diễn đầu vào, đầu ra, bất biến về tính đúng đắn và thước đo tài nguyên trước khi đưa ra tuyên bố về độ phức tạp.
  2. Thử thách tính tổng quát mà nó tuyên bố. Kiểm tra tính chẵn lẻ, các lớp con SAT dễ, các đầu vào mâu thuẫn và các cấu trúc đối kháng. Ghi lại phản ví dụ nhỏ nhất khi một tuyên bố thất bại.
  3. Kiểm toán mọi lập luận còn trụ lại. Xác định các mô hình bị giới hạn và các giả định của nó, xem xét các rào cản chứng minh liên quan, và tìm sự thẩm định độc lập của chuyên gia trước khi gọi nó là một lời giải.

Chúng tôi không giả định trước câu trả lời nào. Các thí nghiệm hữu hạn có thể bác bỏ một thuật toán hay một bất biến; một lời giải cần một chứng minh bao trùm toàn bộ bài toán.

Về sổ tay này

Do Kestrel Exams xuất bản ngày 9 tháng 9 năm 2026. Được viết và kiểm tra bằng máy tính với sự hỗ trợ của AI. Cận chẵn lẻ và phương pháp mã hóa là toán học đã được thiết lập; phần giải thích, cài đặt và gói thí nghiệm được chuẩn bị cho sổ tay này. Công trình này chưa được phản biện ngoài hay xác minh hình thức bằng trợ lý chứng minh.

Chỉnh sửa: support@kestrelexams.com. Nếu có thể, hãy nêu phần, tuyên bố cụ thể, và một phản ví dụ hoặc tài liệu tham khảo.