PCP theorem
গণনামূলক জটিলতা তত্ত্বে, পিসিপি উপপাদ্য (পিসিপি চরিত্রায়ন উপপাদ্য নামেও পরিচিত) বলে যে এনপি জটিলতা শ্রেণীর প্রতিটি সিদ্ধান্তের সমস্যার ধ্রুবক অনুসন্ধান জটিলতা এবং লগারিদমিক র্যান্ডমনেস জটিলতার (র্যান্ডম বিটের লগারিদমিক সংখ্যা ব্যবহার করে) সম্ভাব্যভাবে পরীক্ষা করা যায় এমন প্রমাণ (প্রমাণ যা একটি র্যান্ডমাইজড অ্যালগরিদম দ্বারা পরীক্ষা করা যেতে পারে) রয়েছে। পিসিপি উপপাদ্য বলে যে, কিছু সার্বজনীন ধ্রুবক কে-এর জন্য, প্রতিটি এন-এর জন্য, দৈর্ঘ্য এন-এর বিবৃতির জন্য যে কোনও গাণিতিক প্রমাণকে দৈর্ঘ্যের পলি (এন)-এর একটি ভিন্ন প্রমাণ হিসাবে পুনর্লিখন করা যেতে পারে যা একটি এলোমেলো অ্যালগরিদম দ্বারা 99 শতাংশ নির্ভুলতার সাথে আনুষ্ঠানিকভাবে যাচাইযোগ্য যা সেই প্রমাণের শুধুমাত্র কে অক্ষরগুলি পরীক্ষা করে। পি. সি. পি উপপাদ্যটি আনুমানিক গণনামূলক কঠোরতা তত্ত্বের ভিত্তি, যা বিভিন্ন অপ্টিমাইজেশান সমস্যার জন্য দক্ষ আনুমানিক অ্যালগরিদম ডিজাইনের অন্তর্নিহিত অসুবিধা তদন্ত করে। ইঙ্গো ওয়েগেনার এটিকে "কুকের উপপাদ্যের পর থেকে জটিলতা তত্ত্বের সবচেয়ে গুরুত্বপূর্ণ ফলাফল" হিসাবে বর্ণনা করেছেন এবং ওডেড গোল্ডরিচ এটিকে "উদ্ভাবনী ধারণায় সমৃদ্ধ চিত্তাকর্ষক কাজের ক্রমের চূড়ান্ত পরিণতি" হিসাবে বর্ণনা করেছেন। আনুষ্ঠানিক বিবৃতি পি. সি. পি উপপাদ্য বলে যে এন. পি = পি. সি. পি [ও (লগ এন), ও (1)], যেখানে পি. সি. পি [আর (এন), কিউ (এন)] হল সমস্যাগুলির শ্রেণী যার জন্য একটি সমাধানের সম্ভাব্যভাবে যাচাইযোগ্য প্রমাণ দেওয়া যেতে পারে, যাতে প্রমাণটি যাদৃচ্ছিকতার আর (এন) বিট ব্যবহার করে বহুপদী সময়ে পরীক্ষা করা যেতে পারে এবং প্রমাণের কিউ (এন) বিটগুলি পড়ে, সঠিক প্রমাণগুলি সর্বদা গৃহীত হয় এবং ভুল প্রমাণগুলি কমপক্ষে 1/2 সম্ভাবনার সাথে প্রত্যাখ্যান করা হয়। n হল একটি সমস্যার দৃষ্টান্তের বিবরণের দৈর্ঘ্য। আরও লক্ষ্য করুন যে যাচাইকরণ অ্যালগরিদমটি অ-অভিযোজিতঃ পরীক্ষা করার জন্য প্রমাণের বিটগুলির পছন্দ কেবল এলোমেলো বিট এবং সমস্যার উদাহরণের বর্ণনার উপর নির্ভর করে, প্রমাণের প্রকৃত বিটগুলির উপর নয়। পি. সি. পি এবং আনুমানিক কঠোরতা পি. সি. পি উপপাদ্যের একটি বিকল্প গঠনে বলা হয়েছে যে একটি সীমাবদ্ধ সন্তুষ্টি সমস্যার সন্তোষজনক সীমাবদ্ধতার সর্বাধিক ভগ্নাংশ কিছু ধ্রুবক ফ্যাক্টরের মধ্যে এন. পি-হার্ড থেকে আনুমানিক। আনুষ্ঠানিকভাবে, কিছু ধ্রুবক q এবং α <1-এর জন্য, নিম্নলিখিত প্রতিশ্রুতি সমস্যাটি (লাইজ, Lno) একটি NP-কঠোর সিদ্ধান্ত সমস্যাঃ লাইজ = {φ: φ-এর সমস্ত সীমাবদ্ধতাগুলি একযোগে সন্তোষজনক} Lno = {φ: প্রতিটি অ্যাসাইনমেন্ট φ-এর সীমাবদ্ধতার একটি α ভগ্নাংশের চেয়ে কম সন্তুষ্ট করে}, যেখানে φ হল একটি বুলিয়ান বর্ণমালার উপর একটি সীমাবদ্ধ সন্তুষ্টি সমস্যা (CSP) যেখানে প্রতি সীমাবদ্ধতায় সর্বাধিক q ভেরিয়েবল থাকে। উপরে উল্লিখিত ক্লাস পিসিপির সাথে সংযোগটি লক্ষ্য করে দেখা যায় যে একটি প্রমাণের মধ্যে স্থির সংখ্যক বিট q পরীক্ষা করা প্রমাণের সেই বিটগুলিতে q বুলিয়ান ভেরিয়েবলের একটি সীমাবদ্ধতার মূল্যায়ন হিসাবে দেখা যেতে পারে। যেহেতু যাচাইকরণ অ্যালগরিদম এলোমেলোভাবে ও (লগ এন) বিট ব্যবহার করে, তাই এটি পলি (এন) সীমাবদ্ধতার সাথে উপরে বর্ণিত সিএসপি হিসাবে প্রতিনিধিত্ব করা যেতে পারে। পিসিপি উপপাদ্যের অন্য বৈশিষ্ট্যটি তখন α = 1/2 দিয়ে প্রতিশ্রুতির শর্তের নিশ্চয়তা দেয়ঃ যদি এনপি সমস্যার উত্তর হ্যাঁ হয়, তবে প্রতিটি সীমাবদ্ধতার (যা এলোমেলো বিটগুলির জন্য একটি নির্দিষ্ট মানের সাথে মিলে যায়) একটি সন্তোষজনক অ্যাসাইনমেন্ট (একটি গ্রহণযোগ্য প্রমাণ) থাকে; অন্যথায়, যে কোনও প্রমাণ কমপক্ষে 1/2 সম্ভাবনার সাথে প্রত্যাখ্যান করা উচিত, যার অর্থ যে কোনও অ্যাসাইনমেন্টকে অবশ্যই সীমাবদ্ধতার 1/2 এরও কম পূরণ করতে হবে (যার অর্থ এটি 1/2 এর চেয়ে কম সম্ভাবনার সাথে গৃহীত হবে)। অতএব, প্রতিশ্রুতি সমস্যার জন্য একটি অ্যালগরিদম অন্তর্নিহিত এনপি সমস্যার সমাধান করতে সক্ষম হবে এবং তাই প্রতিশ্রুতি সমস্যাটি অবশ্যই এনপি কঠিন হতে হবে। এই উপপাদ্যের ফলস্বরূপ, এটি দেখানো যেতে পারে যে সর্বাধিক বুলিয়ান সূত্র সন্তোষজনকতা, গ্রাফের সর্বাধিক স্বাধীন সেট এবং ল্যাটিসের জন্য সংক্ষিপ্ততম ভেক্টর সমস্যা সহ অনেক প্রাকৃতিক অপ্টিমাইজেশান সমস্যার সমাধান দক্ষতার সাথে আনুমানিক করা যায় না যদি না পি = এনপি। এই ধরনের সমস্যার সমাধানের সমস্যাকে উপরের ফর্মের একটি প্রতিশ্রুতি সমস্যার আনুমানিক সমাধানের সমস্যাকে হ্রাস করে এটি করা যেতে পারে। এই ফলাফলগুলিকে কখনও কখনও পিসিপি উপপাদ্যও বলা হয় কারণ এগুলিকে কিছু অতিরিক্ত কাঠামো সহ এনপি-র জন্য সম্ভাব্যভাবে যাচাইযোগ্য প্রমাণ হিসাবে দেখা যেতে পারে। ডেক্সটার কোজেনের একটি বক্তৃতায় দুর্বল ফলাফলের প্রমাণ, এনপি পিসিপি [এন3,1] দেওয়া হয়েছে। পি. সি. পি উপপাদ্য হল ইন্টারেক্টিভ প্রমাণ এবং সম্ভাব্যভাবে পরীক্ষা করা যায় এমন প্রমাণের উপর একটি দীর্ঘ লাইনের কাজের সমাপ্তি। স্ট্যান্ডার্ড প্রুফ এবং সম্ভাব্যভাবে যাচাইযোগ্য প্রুফ সম্পর্কিত প্রথম উপপাদ্যটি হল সেই বিবৃতি যা এনইএক্সপি পিসিপি [পলি (এন), পলি (এন)] দ্বারা প্রমাণিত হয়েছে। আদ্যক্ষরগুলির উৎপত্তি পি. সি. পি. সি (এন), এস (এন) [আর (এন), কিউ (এন)] স্বরলিপিটি সম্ভাব্যভাবে পরীক্ষা করা যায় এমন প্রমাণগুলিতে ব্যাখ্যা করা হয়েছে। স্বরলিপি হল এমন একটি ফাংশন যা একটি নির্দিষ্ট জটিলতা শ্রেণী প্রদান করে। উপরে বর্ণিত ব্যাখ্যাটি দেখুন। এই উপপাদ্যের নাম ("পিসিপি উপপাদ্য") সম্ভবত "পিসিপি" থেকে এসেছে যার অর্থ "সম্ভাব্যভাবে পরীক্ষা করা যায় এমন প্রমাণ", অথবা উপরে উল্লিখিত স্বরলিপি (বা উভয়) থেকে এসেছে। প্রথম উপপাদ্য [1990 সালে] পরবর্তীকালে, এই কাজে ব্যবহৃত পদ্ধতিগুলি 1991 সালে বাবাই, ল্যান্স ফোর্টনো, লেভিন এবং সেজেডি, ফিগে, গোল্ডওয়াসার, লুন্ড, সাফরা এবং সেজেডি (1991), এবং অরোরা এবং সাফরা 1992 সালে অরোরা, লুন্ড, মোটওয়ানি, সুদান এবং সেজেডি দ্বারা 1998 সালে পিসিপি উপপাদ্যের প্রমাণ দেওয়ার জন্য প্রসারিত হয়েছিল। 2001 সালে সঞ্জীব অরোরা, উরিয়েল ফাইজি, শফি গোল্ডওয়াসার, কার্স্টেন লুন্ড, লাস্লো লাভাজ, রাজীব মোতওয়ানি, শমুয়েল সাফরা, মধু সুদান এবং মারিয়ো সেজেদিকে পিসিপি উপপাদ্য এবং আনুমানিক কঠোরতার সাথে এর সংযোগের জন্য গোডেল পুরস্কার প্রদান করা হয়। 2005 সালে ইরিট দিনুর এক্সপ্যান্ডার গ্রাফ ব্যবহার করে পিসিপি উপপাদ্যের একটি উল্লেখযোগ্যভাবে সহজ প্রমাণ আবিষ্কার করেন। এর জন্য তিনি 2019 সালের গডেল পুরস্কার পেয়েছেন। 2012 সালে, থমাস ভিদিক এবং সুয়োশি ইতো একটি ফলাফল প্রকাশ করেছিলেন যা "মাল্টিপ্লেয়ার গেমে জড়িত প্রবক্তাদের মিলিত হওয়ার ক্ষমতার উপর একটি শক্তিশালী সীমাবদ্ধতা" দেখিয়েছিল। এটি পিসিপি উপপাদ্যের কোয়ান্টাম অ্যানালগ প্রমাণ করার দিকে একটি পদক্ষেপ হতে পারে, যেহেতু যখন ফলাফলটি গণমাধ্যমে প্রকাশিত হয়েছিল, তখন অধ্যাপক ডরিট আহারোনভ এটিকে "মাল্টিপ্রোভার ইন্টারেক্টিভ প্রমাণের উপর পূর্ববর্তী গবেষণাপত্রের কোয়ান্টাম অ্যানালগ" বলে অভিহিত করেছিলেন যা "মূলত পিসিপি উপপাদ্যের দিকে পরিচালিত করেছিল"। 2018 সালে, থমাস ভিডিক এবং আনন্দ নটরাজন র্যান্ডমাইজড রিডাকশনের অধীনে কোয়ান্টাম পিসিপি উপপাদ্যের একটি গেম বৈকল্পিক প্রমাণ করেছিলেন। এতে বলা হয়েছে যে কিউএমএ * এমআইপি * [লগ (এন), 1,1/2], যেখানে এমআইপি * [এফ (এন), সি, এস] হল এফ (এন)-বিট শাস্ত্রীয় যোগাযোগ সহ বহু-প্রমাণ কোয়ান্টাম ইন্টারেক্টিভ প্রুফ সিস্টেমের একটি জটিলতা শ্রেণী, এবং সম্পূর্ণতা সি এবং সাউন্ডনেস এস। তারা আরও দেখিয়েছে যে কোয়ান্টাম পিসিপি অনুমানের হ্যামিল্টনিয়ান সংস্করণ, অর্থাৎ ধ্রুবক প্রতিশ্রুতি ফাঁক সি-এস সহ একটি স্থানীয় হ্যামিল্টনিয়ান সমস্যা কিউএমএ-হার্ড, গেমের কোয়ান্টাম পিসিপি উপপাদ্যকে বোঝায়। এনএলটিএস অনুমান একটি মৌলিক অমীমাংসিত বাধা এবং পিসিপির কোয়ান্টাম অ্যানালগের অগ্রদূত। উল্লেখগুলি উল্লেখ করুন। । । । । । গণনামূলক জটিলতা তত্ত্বে এলোমেলো অ্যালগরিদম উপপাদ্য