Unique games conjecture
গণনামূলক জটিলতা তত্ত্বে, অনন্য গেম অনুমান (প্রায়শই ইউজিসি হিসাবে উল্লেখ করা হয়) 2002 সালে সুভাষ খোট দ্বারা তৈরি একটি অনুমান। অনুমানটি অনুমান করে যে একটি নির্দিষ্ট ধরনের খেলার আনুমানিক মান নির্ধারণের সমস্যা, যা একটি অনন্য খেলা হিসাবে পরিচিত, তার এনপি-হার্ড গণনামূলক জটিলতা রয়েছে। আনুমানিক কঠোরতা তত্ত্বে এর বিস্তৃত প্রয়োগ রয়েছে। যদি অনন্য গেম অনুমানটি সত্য হয় এবং পি ষ্ণ এন. পি হয়, তবে অনেক গুরুত্বপূর্ণ সমস্যার জন্য বহুপদী সময়ে সঠিক সমাধান পাওয়া কেবল অসম্ভব নয় (পি বনাম এন. পি সমস্যা দ্বারা অনুমান করা হয়েছে), তবে একটি ভাল বহুপদী-সময়ের অনুমান পাওয়াও অসম্ভব। যে সমস্যাগুলির জন্য এই ধরনের অপ্রতিরোধ্য ফলাফল ধারণ করবে তার মধ্যে রয়েছে সীমাবদ্ধতা সন্তুষ্টি সমস্যা, যা বিভিন্ন শাখায় উদ্ভূত হয়। অনুমানটি অস্বাভাবিক যে এটি সত্য কিনা তা নিয়ে একাডেমিক জগত প্রায় সমানভাবে বিভক্ত বলে মনে হয়। ফর্মুলেশন অনন্য গেম অনুমান বেশ কয়েকটি সমতুল্য উপায়ে বলা যেতে পারে। অনন্য লেবেল প্রচ্ছদ অনন্য গেম অনুমানের নিম্নলিখিত সূত্রটি প্রায়শই আনুমানিকতার কঠোরতায় ব্যবহৃত হয়। অনুমানটি নিম্নলিখিত প্রতিশ্রুতি সমস্যার এন. পি-কঠোরতা অনুমান করে যা অনন্য সীমাবদ্ধতার সাথে লেবেল কভার হিসাবে পরিচিত। প্রতিটি প্রান্তের জন্য, দুটি শীর্ষের রঙগুলি কিছু নির্দিষ্ট ক্রমযুক্ত জোড়ার মধ্যে সীমাবদ্ধ। অনন্য সীমাবদ্ধতার অর্থ হল প্রতিটি প্রান্তের জন্য অর্ডার করা জোড়াগুলির কোনওটিরই একই নোডের জন্য একই রঙ নেই। এর মানে হল যে k আকারের বর্ণমালার উপর অনন্য সীমাবদ্ধতা সহ লেবেল কভারের একটি উদাহরণকে πe: [k] → [k] বিন্যাসের সংগ্রহের সাথে একটি নির্দেশিত গ্রাফ হিসাবে উপস্থাপন করা যেতে পারে, যা গ্রাফের প্রতিটি প্রান্তের জন্য একটি করে। একটি লেবেলের প্রচ্ছদ দৃষ্টান্তের একটি অ্যাসাইনমেন্ট জি-এর প্রতিটি শীর্ষকে সেটের একটি মান দেয় [কে] = {1,2,. কে}, যাকে প্রায়শই "রঙ" বলা হয়। এই ধরনের দৃষ্টান্তগুলি এই অর্থে দৃঢ়ভাবে সীমাবদ্ধ যে একটি শীর্ষের রঙ তার প্রতিবেশীদের রঙকে অনন্যভাবে সংজ্ঞায়িত করে এবং তাই তার সম্পূর্ণ সংযুক্ত উপাদানের জন্য। সুতরাং, যদি ইনপুট ইনস্ট্যান্স একটি বৈধ অ্যাসাইনমেন্ট স্বীকার করে, তবে এই ধরনের অ্যাসাইনমেন্ট একটি একক নোডের সমস্ত রঙের উপর পুনরাবৃত্তি করে দক্ষতার সাথে খুঁজে পাওয়া যেতে পারে। বিশেষত, একটি প্রদত্ত দৃষ্টান্ত একটি সন্তোষজনক কাজ স্বীকার করে কিনা তা সিদ্ধান্ত নেওয়ার সমস্যাটি বহুপদী সময়ে সমাধান করা যেতে পারে। একটি অনন্য লেবেল কভার দৃষ্টান্তের মান হল সীমাবদ্ধতার ভগ্নাংশ যা যে কোনও অ্যাসাইনমেন্ট দ্বারা সন্তুষ্ট করা যেতে পারে। সন্তোষজনক দৃষ্টান্তের জন্য, এই মানটি 1 এবং এটি খুঁজে পাওয়া সহজ। অন্যদিকে, একটি অসন্তোষজনক খেলার মূল্য নির্ধারণ করা খুব কঠিন বলে মনে হয়, এমনকি প্রায়। অনন্য খেলার অনুমান এই অসুবিধাকে আনুষ্ঠানিক করে তোলে। আরও আনুষ্ঠানিকভাবে, অনন্য সীমাবদ্ধতার সাথে (সি, এস)-ফাঁক লেবেল-কভার সমস্যাটি হল নিম্নলিখিত প্রতিশ্রুতি সমস্যা (লাইস, লনো): লাইস = {জিঃ কিছু অ্যাসাইনমেন্ট জি} লনো = {জি-তে সীমাবদ্ধতার কমপক্ষে একটি সি-ভগ্নাংশকে সন্তুষ্ট করেঃ প্রতিটি অ্যাসাইনমেন্ট জি}-তে সীমাবদ্ধতার সর্বাধিক একটি এস-ভগ্নাংশকে সন্তুষ্ট করে যেখানে জি অনন্য সীমাবদ্ধতার সাথে লেবেল কভার সমস্যার একটি উদাহরণ। অনন্য গেম অনুমান বলে যে প্রতিটি যথেষ্ট ছোট জোড়া ধ্রুবকের জন্য ε, δ> 0, একটি ধ্রুবক k রয়েছে যাতে (1 − δ, ε)-ফাঁক লেবেল-কভার সমস্যাটি k আকারের বর্ণমালার উপর অনন্য সীমাবদ্ধতা সহ NP-কঠিন। গ্রাফের পরিবর্তে, লেবেল কভার সমস্যাটি রৈখিক সমীকরণের পরিপ্রেক্ষিতে প্রণয়ন করা যেতে পারে। উদাহরণস্বরূপ, ধরুন যে আমাদের পূর্ণসংখ্যা মডুলো 7-এর উপর রৈখিক সমীকরণের একটি ব্যবস্থা রয়েছেঃ এটি অনন্য সীমাবদ্ধতার সাথে লেবেল কভার সমস্যার একটি উদাহরণ। উদাহরণস্বরূপ, প্রথম সমীকরণটি বিন্যাসের (1,2) সাথে মিলে যায় যেখানে (1,2) (x1) = 2x2 মডুলো 7। টু-প্রোভার প্রুফ সিস্টেম একটি অনন্য গেম হল টু-প্রোভার ওয়ান-রাউন্ড (2পি1আর) গেমের একটি বিশেষ কেস। টু-প্রোভার ওয়ান-রাউন্ড খেলায় দুজন খেলোয়াড় (প্রোভার নামেও পরিচিত) এবং একজন রেফারি থাকে। রেফারি প্রতিটি খেলোয়াড়কে একটি পরিচিত সম্ভাব্যতা বন্টন থেকে নেওয়া একটি প্রশ্ন পাঠান এবং খেলোয়াড়দের প্রত্যেককে একটি উত্তর পাঠাতে হয়। উত্তরগুলি নির্দিষ্ট আকারের একটি সেট থেকে আসে। খেলাটি একটি ভবিষ্যদ্বাণী দ্বারা নির্দিষ্ট করা হয় যা খেলোয়াড়দের কাছে পাঠানো প্রশ্ন এবং তাদের দেওয়া উত্তরের উপর নির্ভর করে। খেলোয়াড়রা আগে থেকে একটি কৌশল নির্ধারণ করতে পারে, যদিও খেলার সময় তারা একে অপরের সাথে যোগাযোগ করতে পারে না। খেলোয়াড়রা জয়ী হয় যদি ভবিষ্যদ্বাণী তাদের প্রশ্ন এবং তাদের উত্তর দ্বারা সন্তুষ্ট হয়। প্রথম খেলোয়াড়ের প্রতিটি প্রশ্ন এবং প্রতিটি উত্তরের জন্য দ্বিতীয় খেলোয়াড়ের ঠিক একটি উত্তর থাকলে দুই-প্রমাণের এক-রাউন্ডের খেলাটিকে একটি অনন্য খেলা বলা হয় এবং এর বিপরীতে খেলোয়াড়দের জয় হয়। একটি খেলার মূল্য হল সমস্ত কৌশলের উপর খেলোয়াড়দের জন্য সর্বোচ্চ জয়ের সম্ভাবনা। অনন্য গেম অনুমান বলে যে প্রতিটি যথেষ্ট ছোট জোড়া ধ্রুবক ε, δ> 0-এর জন্য একটি ধ্রুবক k বিদ্যমান যাতে নিম্নলিখিত প্রতিশ্রুতি সমস্যাটি (লাই, Lno) NP-কঠিন হয়ঃ লাই = {G: G-এর মান কমপক্ষে 1 − δ} Lno = {G: G-এর মান সর্বাধিক ε} যেখানে G একটি অনন্য খেলা যার উত্তরগুলি k আকারের একটি সেট থেকে আসে। সম্ভবত যাচাইযোগ্য প্রমাণ বিকল্পভাবে, অনন্য গেম অনুমান NP-তে সমস্যার জন্য একটি নির্দিষ্ট ধরনের সম্ভাব্যভাবে যাচাইযোগ্য প্রমাণের অস্তিত্বকে অনুমান করে। একটি অনন্য খেলাকে প্রশ্ন জটিলতা 2 সহ একটি বিশেষ ধরনের অ-অভিযোজিত সম্ভাব্য পরীক্ষা-যোগ্য প্রমাণ হিসাবে দেখা যেতে পারে, যেখানে যাচাইকারীর সম্ভাব্য প্রশ্নের প্রতিটি জোড়া এবং প্রথম প্রশ্নের প্রতিটি সম্ভাব্য উত্তরের জন্য, দ্বিতীয় প্রশ্নের ঠিক একটি সম্ভাব্য উত্তর রয়েছে যা যাচাইকারীকে গ্রহণযোগ্য করে তোলে এবং তদ্বিপরীত। অনন্য গেম অনুমান বলে যে প্রতিটি যথেষ্ট ছোট জোড়া ধ্রুবকের জন্য এমন একটি ধ্রুবক রয়েছে যে এনপি-র প্রতিটি সমস্যার সম্পূর্ণতা, দৃঢ়তা এবং এলোমেলো জটিলতা সহ আকারের বর্ণমালার উপর সম্ভাব্যভাবে পরীক্ষা করা যায় এমন প্রমাণ রয়েছে যা একটি অনন্য খেলা। প্রাসঙ্গিকতা 2002 সালে সুভাষ খোট দ্বারা আনুমানিক কঠোরতা তত্ত্বের কিছু প্রশ্নের অগ্রগতি করার জন্য অনন্য গেম অনুমান চালু করা হয়েছিল। অনন্য গেম অনুমানের সত্যতা অনেক পরিচিত আনুমানিক অ্যালগরিদমের অনুকূলতা বোঝায় (পি ষ্ণ এনপি ধরে নিয়ে)। উদাহরণস্বরূপ, একটি গ্রাফের সর্বাধিক কাট আনুমানিক করার জন্য গোম্যানস এবং উইলিয়ামসনের অ্যালগরিদম দ্বারা অর্জিত আনুমানিক অনুপাত অনন্য গেম অনুমান এবং পি ষ্ণ এনপি ধরে নিয়ে যে কোনও যোগাত্মক ধ্রুবকের মধ্যে সর্বোত্তম। অনন্য গেম অনুমানটি যে ফলাফলগুলি বোঝায় তার একটি তালিকা পার্শ্ববর্তী টেবিলে দুর্বল অনুমান পি ষ্ণ এনপি-র জন্য সংশ্লিষ্ট সেরা ফলাফলের সাথে দেখানো হয়েছে। এর একটি ধ্রুবক বা মানে হল যে ফলাফল প্রতিটি ধ্রুবকের জন্য (সমস্যার আকারের সাপেক্ষে) যথাক্রমে এর চেয়ে বেশি বা তার চেয়ে কম কঠোরভাবে ধরে রাখে। আলোচনা এবং বিকল্প বর্তমানে, অনন্য খেলার অনুমানের সত্যতা সম্পর্কে কোনও ঐক্যমত্য নেই। অনুমানের কিছু শক্তিশালী রূপকে অস্বীকার করা হয়েছে। অনুমানের একটি ভিন্ন রূপ অনুমান করে যে যখন একটি অনন্য খেলার মান কমপক্ষে সেই ক্ষেত্রে থেকে আলাদা করা যখন মান সর্বাধিক হয় তখন বহুপদী-সময় অ্যালগরিদমের জন্য অসম্ভব (তবে সম্ভবত এনপি-হার্ড নয়)। অনুমানের এই রূপটি এখনও আনুমানিক কঠোরতার প্রয়োগের জন্য কার্যকর হবে। অনুমানের উপরের সূত্রগুলিতে ধ্রুবকটি প্রয়োজনীয় যদি না পি = এনপি হয়। যদি স্বতন্ত্রতার প্রয়োজনীয়তা অপসারণ করা হয় তবে সমান্তরাল পুনরাবৃত্তি উপপাদ্য দ্বারা সংশ্লিষ্ট বিবৃতিটি সত্য বলে জানা যায়, এমনকি মারেক কার্পিনস্কি এবং ওয়ারেন শুডি অনন্য গেম সমস্যার ঘন দৃষ্টান্তের জন্য রৈখিক সময় আনুমানিক পরিকল্পনা তৈরি করেছেন। 2008 সালে, প্রসাদ রাঘবেন্দ্র দেখিয়েছেন যে যদি অনন্য খেলার অনুমানটি সত্য হয়, তবে প্রতিটি সীমাবদ্ধতা সন্তুষ্টি সমস্যার জন্য সর্বোত্তম আনুমানিক অনুপাত একটি নির্দিষ্ট সহজ সেমিডিফাইনাইট প্রোগ্রামিং উদাহরণ দ্বারা দেওয়া হয়, যা বিশেষত বহুপদী। 2010 সালে, প্রসাদ রাঘবেন্দ্র এবং ডেভিড স্টিয়ারার গ্যাপ-স্মল-সেট সম্প্রসারণ সমস্যার সংজ্ঞা দেন এবং অনুমান করেন যে এটি এনপি-হার্ড। এই অনুমানটি অনন্য খেলার অনুমানকে বোঝায়। সম্পূর্ণ দ্বিদলীয় সাবগ্রাফ খুঁজে বের করার জন্য আনুমানিক ফলাফলের দৃঢ় কঠোরতা প্রমাণ করতেও এটি ব্যবহার করা হয়েছে। 2010 সালে, সঞ্জীব অরোরা, বোয়াজ বারাক এবং ডেভিড স্টিয়ারার অনন্য গেম সমস্যার জন্য একটি সাবএক্সপোনেনশিয়াল সময় আনুমানিক অ্যালগরিদম খুঁজে পেয়েছিলেন। 2012 সালে, এটি দেখানো হয়েছিল যে কমপক্ষে মান সহ দৃষ্টান্তগুলি থেকে সর্বাধিক মান সহ দৃষ্টান্তগুলি আলাদা করা এনপি-হার্ড। 2018 সালে, একাধিক গবেষণাপত্রের পরে, অনুমানের একটি দুর্বল সংস্করণ, যাকে 2-2 গেম অনুমান বলা হয়, প্রমাণিত হয়েছিল। একটি নির্দিষ্ট অর্থে, এটি মূল অনুমানের "অর্ধেক" প্রমাণ করে। এটি অনন্য লেবেল কভারের জন্য সর্বাধিক পরিচিত ব্যবধানকেও উন্নত করেঃ কমপক্ষে মূল্য সহ দৃষ্টান্তগুলি থেকে সর্বাধিক মূল্য সহ দৃষ্টান্তগুলি আলাদা করা এনপি-কঠিন। উল্লেখগুলি উল্লেখ করুন। 2002 আনুমানিক অ্যালগরিদম গণনায় গণনামূলক জটিলতা তত্ত্ব গণনামূলক কঠোরতা অনুমান কম্পিউটার বিজ্ঞানে অমীমাংসিত সমস্যা অনুমান