Valiant–Vazirani theorem
ভ্যালিয়েন্ট-ভাজিরানি উপপাদ্যটি গণনামূলক জটিলতা তত্ত্বের একটি উপপাদ্য যা বলে যে যদি দ্ব্যর্থহীন-স্যাটের জন্য একটি বহুপদী সময় অ্যালগরিদম থাকে, তবে এনপি = আরপি। লেসলি ভ্যালিয়েন্ট এবং বিজয় ভাজিরানি তাদের গবেষণাপত্রে এনপি 1986 সালে প্রকাশিত অনন্য সমাধান সনাক্ত করার মতোই সহজ বলে প্রমাণ করেছেন। প্রমাণটি মুলমুলে-ভাজিরানি-ভাজিরানি বিচ্ছিন্নতা লেমার উপর ভিত্তি করে তৈরি, যা পরবর্তীকালে তাত্ত্বিক কম্পিউটার বিজ্ঞানের বেশ কয়েকটি গুরুত্বপূর্ণ প্রয়োগের জন্য ব্যবহৃত হয়েছিল। ভ্যালিয়েন্ট-ভাজিরানি উপপাদ্যটি বোঝায় যে বুলিয়ান সন্তোষজনক সমস্যা, যা এনপি-সম্পূর্ণ, একটি গণনামূলকভাবে কঠিন সমস্যা হিসাবে রয়ে গেছে, এমনকি যদি ইনপুট দৃষ্টান্তগুলিতে সর্বাধিক একটি সন্তোষজনক অ্যাসাইনমেন্ট থাকার প্রতিশ্রুতি দেওয়া হয়। প্রমাণের রূপরেখা দ্ব্যর্থহীন-স্যাট হল একটি প্রদত্ত বুলিয়ান সূত্র যার সর্বাধিক একটি সন্তোষজনক অ্যাসাইনমেন্ট রয়েছে তা সন্তোষজনক নয় বা ঠিক একটি সন্তোষজনক অ্যাসাইনমেন্ট রয়েছে কিনা তা নির্ধারণ করার প্রতিশ্রুতি সমস্যা। প্রথম ক্ষেত্রে, দ্ব্যর্থহীন-স্যাটের জন্য একটি অ্যালগরিদম প্রত্যাখ্যান করা উচিত এবং দ্বিতীয় ক্ষেত্রে এটি সূত্রটি গ্রহণ করা উচিত। যদি সূত্রটিতে একাধিক সন্তোষজনক অ্যাসাইনমেন্ট থাকে, তবে অ্যালগরিদমের আচরণের কোনও শর্ত নেই। প্রতিশ্রুতি সমস্যা দ্ব্যর্থহীন-স্যাট একটি অনির্ধারিত টুরিং মেশিন দ্বারা সিদ্ধান্ত নেওয়া যেতে পারে যার সর্বাধিক একটি গ্রহণযোগ্য গণনার পথ রয়েছে। এই অর্থে, এই প্রতিশ্রুতি সমস্যাটি জটিলতা শ্রেণী ইউ. পি-র অন্তর্গত (যা সাধারণত শুধুমাত্র ভাষার জন্য সংজ্ঞায়িত করা হয়)। ভ্যালিয়েন্ট-ভাজিরানি উপপাদ্যের প্রমাণ এস. এ. টি থেকে এস. এ. টি-তে একটি সম্ভাব্য হ্রাস নিয়ে গঠিত যাতে, সম্ভাবনার সাথে কমপক্ষে, আউটপুট সূত্রের সর্বাধিক একটি সন্তোষজনক অ্যাসাইনমেন্ট থাকে এবং এইভাবে দ্ব্যর্থহীন-এস. এ. টি সমস্যার প্রতিশ্রুতি পূরণ করে। আরও সুনির্দিষ্টভাবে বলতে গেলে, হ্রাস হল একটি র্যান্ডমাইজড পলিনোমিয়াল-টাইম অ্যালগরিদম যা একটি বুলিয়ান সূত্রের সাথে ভেরিয়েবল সহ একটি বুলিয়ান সূত্রের মানচিত্র তৈরি করে যাতে প্রতিটি সন্তোষজনক অ্যাসাইনমেন্টও সন্তুষ্ট হয় এবং যদি সন্তোষজনক হয়, তবে সম্ভাবনার সাথে কমপক্ষে একটি অনন্য সন্তোষজনক অ্যাসাইনমেন্ট থাকে। প্রতিবার নতুন স্বাধীন র্যান্ডম বিট দিয়ে, একটি বহুপদী সংখ্যা হ্রাস চালানোর মাধ্যমে, আমরা সূত্র পাই। বেছে নিলে, আমরা পাই যে অন্তত একটি সূত্র অনন্যভাবে সন্তোষজনক হওয়ার সম্ভাবনা অন্তত যদি সন্তোষজনক হয়। এটি টুরিংকে এস. এ. টি থেকে দ্ব্যর্থহীন-এস. এ. টি-তে হ্রাস দেয় কারণ দ্ব্যর্থহীন-এস. এ. টি-র জন্য একটি অনুমিত অ্যালগরিদম চালু করা যেতে পারে। তারপর SAT-এর স্ব-হ্রাসযোগ্যতা একটি সন্তোষজনক অ্যাসাইনমেন্ট গণনা করতে ব্যবহার করা যেতে পারে, যদি এটি বিদ্যমান থাকে। সামগ্রিকভাবে, এটি প্রমাণ করে যে এনপি = আরপি যদি দ্ব্যর্থহীন-স্যাট আরপিতে সমাধান করা যায়। হ্রাসের ধারণাটি হল সূত্রটির সমাধান স্থানটিকে এলোমেলো অ্যাফিন হাইপারপ্লেনের সাথে ছেদ করা, যেখানে এলোমেলোভাবে অভিন্নভাবে বেছে নেওয়া হয়। একটি বিকল্প প্রমাণ মুলমুলে, ভাজিরানি এবং ভাজিরানির বিচ্ছিন্নতা লেম্মার উপর ভিত্তি করে তৈরি। তারা আরও সাধারণ সেটিং বিবেচনা করে এবং এখানে সেটিংয়ে প্রয়োগ করে এটি শুধুমাত্র একটি বিচ্ছিন্নতা সম্ভাবনা দেয়। তথ্যসূত্র কাঠামোগত জটিলতা তত্ত্ব গণনামূলক জটিলতা তত্ত্বের উপপাদ্য