১৯৮৫ সালে শাফি গোল্ডওয়াসার, সিলভিও মিকালি এবং চার্লস র্যাকফ তাদের যুগান্তকারী গবেষণাপত্র “The Knowledge Complexity of Interactive Proof-Systems” প্রকাশের মাধ্যমে গণিতের হাজার বছরের সনাতন প্রমাণের ধারণাকে আমূল বদলে দেন। প্রাচীনকাল থেকে প্রমাণ বলতে বোঝানো হতো একগুচ্ছ ধাপে ধাপে লেখা যুক্তি। কিন্তু GMR প্রমাণকে সংজ্ঞায়িত করলেন একজন সর্বশক্তিমান প্রুভার এবং একজন পরিমিত ক্ষমতার ভেরিফায়ারের মধ্যকার একটি ইন্টারেক্টিভ সংলাপ হিসেবে। এর মাধ্যমে প্রমাণিত হলো যে কোনো সত্যকে শতভাগ নির্ভুলভাবে প্রমাণ করা সম্ভব সেই সত্যের গোপন তথ্য এক বিন্দুও প্রকাশ না করে।
১. ইন্টারেক্টিভ প্রুফ সিস্টেম (IP) ও জটিলতা তত্ত্ব
একটি ইন্টারেক্টিভ প্রুফ সিস্টেমে (IP) প্রুভার (P) এবং ভেরিফায়ার (V)-এর মধ্যে বহু রাউন্ডের মেসেজ আদান-প্রদান হয়। এই ব্যবস্থার দুটি অপরিবর্তনীয় ভিত্তিস্তম্ভ রয়েছে:
- কমপ্লিটনেস (Completeness): যদি বক্তব্যটি সত্য হয় ((x in L)), তবে সৎ প্রুভার ভেরিফায়ারকে শতভাগ নিশ্চিত করতে পারবে:
[
Pr[langle P, V
angle(x) = 1] ge 1 – 2^{-n}
] - সাউন্ডনেস (Soundness): যদি বক্তব্যটি মিথ্যা হয় ((x
otin L)), তবে চরম ধূর্ত ও অসীম ক্ষমতাসম্পন্ন মিথ্যাবাদী প্রুভারও ভেরিফায়ারকে ফাঁকি দিতে পারবে না (প্রতারণার সম্ভাবনা নগণ্য):
[
orall P^*, quad Pr[langle P^*, V
angle(x) = 1] le ext{negl}(n)
]
১৯৯২ সালে আদি শামির প্রমাণ করেন জটিলতা বিজ্ঞানের বিখ্যাত সমীকরণ (mathbf{IP} = mathbf{PSPACE})। অর্থাৎ সাধারণ কম্পিউটার যে গণনা করতে মহাবিশ্বের বয়সের সমান সময় নিত, পলিনোমিয়াল স্পেস ও ইন্টারেক্টিভ প্রুফের সাহায্যে তা নিমিষেই যাচাই করা যায়।
২. জিরো-নলেজের সংজ্ঞা: সিমুলেশন প্যারাডাইম (Simulation Paradigm)
একটি প্রমাণ থেকে “কোনো তথ্য ফাঁস হয়নি” তা গণিতে কীভাবে প্রমাণ করা যায়? GMR উদ্ভাবন করলেন এক গভীর দার্শনিক ও গাণিতিক কাঠামো—সিমুলেটর মডেল।
ধরা যাক ( ext{View}_V(x)) হলো প্রমাণের সময় ভেরিফায়ারের রেকর্ড করা সম্পূর্ণ কথোপকথন (ইনপুট, র্যান্ডম কয়েন টস এবং প্রুভারের বার্তা)। একটি ইন্টারেক্টিভ প্রমাণকে জিরো-নলেজ বলা হবে যদি:
একটি সাধারণ পলিনোমিয়াল-টাইম অ্যালগরিদম (S) (সিমুলেটর) থাকে—যা গোপন তথ্য (উইটনেস) না জেনেই এবং প্রুভারের সাথে কোনো কথা না বলেই নিজে নিজে আসল প্রমাণের অবিকল ট্রানস্ক্রিপ্ট তৈরি করতে পারে।
[
S(x) approx_c ext{View}_V^{langle P, V
angle}(x)
]
এর পেছনের যুক্তি অত্যন্ত শক্তিশালী: ভেরিফায়ার যদি প্রুভারের সাথে কথা বলার আগেই নিজের সাধারণ ল্যাপটপে বসে ঠিক একই ধরণের কথোপকথনের খসড়া তৈরি করে ফেলতে পারে, তবে নিশ্চিতভাবেই প্রমাণটির মাধ্যমে প্রুভারের কাছ থেকে তার ভেতর নতুন কোনো তথ্য প্রবেশ করেনি। অর্থাৎ সিস্টেমটি শতভাগ জিরো-নলেজ।
৩. ক্লাসিক্যাল উদাহরণ: গ্রাফ ৩-কালারিং জিরো-নলেজ প্রুফ
১৯৯১ সালে গোল্ডরাইখ, মিকালি ও উইগডারসন (GMW) প্রমাণ করেন যে: NP জটিলতা ক্লাসের যেকোনো সমস্যাকেই জিরো-নলেজে প্রমাণ করা সম্ভব। তারা NP-কমপ্লিট গ্রাফ ৩-কালারিং ব্যবহার করে এটি দেখান:
- গ্রাফের সূচনা: প্রুভারের কাছে একটি জটিল গ্রাফের ৩-কালার সমাধান (phi) আছে যাতে কোনো সংলগ্ন নোডের রঙ এক না হয়।
- রঙের পারমিউটেশন ও কমিটমেন্ট: প্রুভার প্রতি রাউন্ডে তিনটি রঙকে এলোমেলোভাবে অদলবদল করে ((pi in S_3))। প্রতিটি নোডের রঙকে তালাবদ্ধ বক্সে (কমিটমেন্টে) ভরে ভেরিফায়ারের কাছে পাঠায়।
- ভেরিফায়ারের চ্যালেঞ্জ: ভেরিফায়ার যেকোনো একটি র্যান্ডম এজ বা সংযোগ রেখা বেছে নিয়ে বলে, “এই রেখার দুই প্রান্তের নোড দুটি খুলে দেখাও।”
- প্রুভারের উত্তর: প্রুভার কেবল ওই নির্দিষ্ট দুটি নোডের তালা খুলে রঙ দেখায়।
- যাচাইকরণ: ভেরিফায়ার দেখে যে দুটি নোডের রঙ ভিন্ন।
যদি প্রুভার মিথ্যা বলে থাকে, তবে অন্তত একটি রেখায় একই রঙ থাকবে এবং সে ধরা পড়ার সম্ভাবনা থাকবে। এই খেলাটি বারবার খেললে প্রতারণার সম্ভাবনা শূন্যে নেমে আসে। অথচ প্রতি রাউন্ডে রঙ এলোমেলো বদলানোর কারণে ভেরিফায়ার কেবল দুটি ভিন্ন রঙ দেখে, কিন্তু পুরো গ্রাফটি কীভাবে রঙিন করা হয়েছে তার কোনো ধারণাই পায় না।
