Chứng minh kiểm tra được bằng xác suất

 

Các chứng minh kiểm tra được bằng xác suất (Probabilistically Checkable Proofs - PCP) là một trong những đề tài trung tâm của lý thuyết máy tính hiện đại, với rất nhiều ứng dụng trong mật mã học ( cryptography), lý thuyết độ phức tạp tính toán ( computational complexity theory), độ khó của các giải thuật xấp xỉ (hardness of approximation ), vân vân.

Để hiểu sơ bộ về PCP, ta thử xét một trò chơi đơn giản với hai người chơi: người chứng minh (prover), và người xác minh (verifier). Prover có nhiệm vụ thuyết phục verifier về một mệnh đề nào đó mà prover biết cách chứng minh. Ví dụ: giả thuyết Goldbach (Goldbach conjecture) nói rằng các số chẵn lớn hơn 2 đều là tổng của hai số nguyên tố (giả thuyết này chưa ai chứng minh được). Nếu prover biết rằng giả thuyết Goldbach sai, thì prover có thể trình ra cho verifier thấy một số chẵn (> 2). Verifier thử tất cả các cặp số nguyên dương với tổng đã cho, và kiểm tra xem có cặp nguyên tố nào không. Quá trình kiểm tra này có thể rất mất thì giờ (dù là với máy tính), nhưng rõ là làm được trong khoảng thời gian hữu hạn.

Tuy nhiên, nếu tổng số phép tính verifer phải làm quá lớn (10⁸⁰ chẳng hạn), thì "thời gian hữu hạn" cũng bằng vô hạn. (Tổng số nguyên tử trong vũ trụ nhỏ hơn 10⁸⁰. Từ Big Bang đến nay chỉ có khoảng 10 ¹⁷ giây.) Thế có thể nào thiết lập được một nghi thức giao tiếp (interaction protocol) giữa prover và verifier sao cho verifier phải làm ít việc hơn mà vẫn tin chắc (với xác suất cực lớn) là prover có chứng minh đúng? Nếu có nghi thức như vậy thì tổng số bit thông tin verifier phải hỏi prover là bao nhiêu để có độ tin cậy cho trước? Các câu hỏi này là đối tượng của ngành nghiên cứu PCP. Ví dụ: giáo sư Johan Håstad gần đây đã chứng minh được rằng chỉ cần 3 bít nhị phân là verifier có thể có xác suất đúng hơn 1/2. Nếu lập lại nghi thức này 200 lần độc lập nhau thì xác suất đúng là 1 - 1/2 ²⁰⁰, coi như là bằng 1. (Lưu ý: 2²⁰⁰ > 10⁸⁰.)

Tiến sĩ Laci Lovász (thầy của giáo sư Vũ Hà Văn) có một bài viết nho nhỏ với các ví dụ đời thường về các phép chứng minh kiểm tra được bằng xác suất. Một ví dụ thú vị ông đưa ra là: làm thế nào ta thuyết phục nhân viên nhà băng (máy tính) là ta có mật khẩu tài khoản của mình mà không đưa mật khẩu ra. Trong trường hợp này, ta là prover, còn đối phương là verifier!