Circuit satisfiability problem
তাত্ত্বিক কম্পিউটার বিজ্ঞানে, বর্তনী সন্তোষজনক সমস্যা (সি. আই. আর. সি. ইউ. আই. টি-এস. এ. টি, সার্কিট-এস. এ. টি, সি. এস. এ. টি ইত্যাদি নামেও পরিচিত)। একটি প্রদত্ত বুলিয়ান সার্কিটের ইনপুটগুলির একটি অ্যাসাইনমেন্ট রয়েছে কিনা তা নির্ধারণের সিদ্ধান্ত সমস্যা যা আউটপুটকে সত্য করে তোলে। অন্য কথায়, এটি জিজ্ঞাসা করে যে প্রদত্ত বুলিয়ান সার্কিটের ইনপুটগুলি ধারাবাহিকভাবে 1 বা 0 এ সেট করা যেতে পারে কিনা যাতে সার্কিটটি 1 আউটপুট দেয়। যদি তাই হয়, তবে সার্কিটটিকে সন্তোষজনক বলা হয়। অন্যথায়, সার্কিটটিকে অসন্তুষ্ট বলা হয়। ডানদিকের চিত্রে, বাম সার্কিটটি উভয় ইনপুটকে 1 সেট করে সন্তুষ্ট করা যেতে পারে, তবে ডান সার্কিটটি সন্তোষজনক নয়। সার্কিটস্যাট বুলিয়ান স্যাটিসফায়েবিলিটি প্রবলেম (স্যাট)-এর সঙ্গে ঘনিষ্ঠভাবে সম্পর্কিত এবং একইভাবে, এনপি-সম্পূর্ণ হিসাবে প্রমাণিত হয়েছে। এটি একটি প্রোটোটাইপিক্যাল এনপি-সম্পূর্ণ সমস্যা; কুক-লেভিন উপপাদ্যটি কখনও কখনও স্যাটের পরিবর্তে সার্কিটস্যাটে প্রমাণিত হয় এবং তারপরে সার্কিটস্যাটকে তাদের এনপি-সম্পূর্ণতা প্রমাণ করার জন্য অন্যান্য সন্তোষজনক সমস্যাগুলিতে হ্রাস করা যেতে পারে। নির্বিচারে বাইনারি গেটযুক্ত একটি বর্তনীর সন্তোষজনকতা সময়মতো নির্ধারণ করা যেতে পারে। এনপি-সম্পূর্ণতার প্রমাণ একটি সার্কিট এবং ইনপুটগুলির একটি সন্তোষজনক সেট দেওয়া হলে, প্রতিটি গেটের আউটপুট স্থির সময়ে গণনা করা যেতে পারে। অতএব, বর্তনীর আউটপুট বহুপদী সময়ে যাচাইযোগ্য। এইভাবে সার্কিট স্যাট জটিলতা শ্রেণীর এনপি-র অন্তর্গত। এন. পি-কঠোরতা দেখানোর জন্য, 3এস. এ. টি থেকে সার্কিট এস. এ. টি-তে হ্রাস করা সম্ভব। ধরুন মূল 3এসএটি সূত্রে ভেরিয়েবল এবং অপারেটর (AND, OR, NOT) রয়েছে। একটি সার্কিট এমনভাবে ডিজাইন করুন যাতে প্রতিটি পরিবর্তনশীলের সাথে সম্পর্কিত একটি ইনপুট এবং প্রতিটি অপারেটরের সাথে সম্পর্কিত একটি গেট থাকে। 3এসএটি সূত্র অনুযায়ী গেটগুলি সংযুক্ত করুন। উদাহরণস্বরূপ, যদি 3এসএটি সূত্রটি হয় তবে সার্কিটটিতে 3টি ইনপুট থাকবে, একটি AND, একটি OR, এবং একটি NOT গেট। সংশ্লিষ্ট ইনপুটটি একটি AND গেটে পাঠানোর আগে উল্টানো হবে এবং AND গেটের আউটপুট একটি OR গেটে পাঠানো হবে লক্ষ্য করুন যে 3SAT সূত্রটি উপরে ডিজাইন করা সার্কিটের সমতুল্য, তাই তাদের আউটপুট একই ইনপুটের জন্য একই। অতএব, যদি 3এসএটি সূত্রের একটি সন্তোষজনক অ্যাসাইনমেন্ট থাকে, তবে সংশ্লিষ্ট সার্কিটটি 1 আউটপুট দেবে, এবং তদ্বিপরীত। সুতরাং, এটি একটি বৈধ হ্রাস, এবং সার্কিট স্যাট এনপি-হার্ড। এটি সার্কিট স্যাট এনপি-সম্পূর্ণ হওয়ার প্রমাণ সম্পূর্ণ করে। সীমাবদ্ধ রূপ এবং সম্পর্কিত সমস্যা প্ল্যানার সার্কিট এসএটি ধরে নিন যে আমাদের একটি প্ল্যানার বুলিয়ান সার্কিট দেওয়া হয়েছে (অর্থাৎ। একটি বুলিয়ান সার্কিট যার অন্তর্নিহিত গ্রাফ সমতল) ঠিক দুটি ইনপুট সহ শুধুমাত্র NAND গেট ধারণ করে। প্ল্যানার সার্কিট এসএটি হল এই সার্কিটের ইনপুটগুলির একটি অ্যাসাইনমেন্ট রয়েছে কিনা তা নির্ধারণের সিদ্ধান্ত সমস্যা যা আউটপুটকে সত্য করে তোলে। এই সমস্যাটি এনপি-সম্পূর্ণ। উপরন্তু, যদি বিধিনিষেধগুলি পরিবর্তন করা হয় যাতে সার্কিটের কোনও গেট একটি এনওআর গেট হয়, ফলস্বরূপ সমস্যাটি এনপি-সম্পূর্ণ থাকে। সার্কিট ইউ. এন. এস. এ. টি সার্কিট ইউ. এন. এস. এ. টি হল একটি প্রদত্ত বুলিয়ান সার্কিট তার ইনপুটগুলির সমস্ত সম্ভাব্য অ্যাসাইনমেন্টের জন্য ভুল আউটপুট দেয় কিনা তা নির্ধারণের সিদ্ধান্ত সমস্যা। এটি সার্কিট স্যাট সমস্যার পরিপূরক, এবং তাই কো-এনপি-সম্পূর্ণ। সার্কিটস্যাট বা এর রূপগুলি থেকে সার্কিটস্যাট হ্রাস থেকে হ্রাস নির্দিষ্ট কিছু সমস্যার এনপি-কঠোরতা দেখানোর জন্য ব্যবহার করা যেতে পারে এবং আমাদের দ্বৈত-রেল এবং বাইনারি লজিক হ্রাসের বিকল্প প্রদান করে। এই ধরনের হ্রাসের জন্য যে যন্ত্রগুলি তৈরি করতে হবে সেগুলি হলঃ একটি তারের যন্ত্র। এই গ্যাজেটটি সার্কিটের তারগুলিকে অনুকরণ করে। একটি বিভক্ত গ্যাজেট। এই গ্যাজেটটি নিশ্চিত করে যে সমস্ত আউটপুট তারের মান ইনপুট তারের সমান। সার্কিটের গেটগুলি অনুকরণকারী গ্যাজেটগুলি। একটি সত্যিকারের টার্মিনেটর গ্যাজেট। এই গ্যাজেটটি পুরো সার্কিটের আউটপুটকে ট্রু হতে বাধ্য করতে ব্যবহৃত হয়। একটি টার্ন গ্যাজেট। এই গ্যাজেটটি আমাদের প্রয়োজন অনুযায়ী তারগুলিকে সঠিক দিকে পুনর্নির্দেশ করার অনুমতি দেয়। একটি ক্রসওভার গ্যাজেট। এই গ্যাজেটটি আমাদের দুটি তারকে পরস্পরের সাথে যোগাযোগ না করেই একে অপরকে অতিক্রম করতে দেয়। মাইনসুইপার অনুমান সমস্যা এই সমস্যাটি জিজ্ঞাসা করে যে মাইনসুইপার বোর্ড দেওয়া সমস্ত বোমা সনাক্ত করা সম্ভব কিনা। সার্কিট ইউ. এন. এস. এ. টি সমস্যা হ্রাসের মাধ্যমে এটি সি. ও. এন. পি-সম্পূর্ণ হিসাবে প্রমাণিত হয়েছে। এই হ্রাসের জন্য নির্মিত যন্ত্রগুলি হলঃ তার, বিভক্ত, এবং গেট এবং টার্মিনেটর নয়। এই যন্ত্রগুলি সম্পর্কে তিনটি গুরুত্বপূর্ণ পর্যবেক্ষণ রয়েছে। প্রথমত, স্প্লিট গ্যাজেটটি নট গ্যাজেট এবং টার্ন গ্যাজেট হিসাবেও ব্যবহার করা যেতে পারে। দ্বিতীয়ত, অ্যান্ড অ্যান্ড নট গ্যাজেট তৈরি করাই যথেষ্ট, কারণ তারা একসঙ্গে সর্বজনীন ন্যান্ড গেট অনুকরণ করতে পারে। পরিশেষে, যেহেতু তিনটি ন্যান্ড একটি এক্সওআর বাস্তবায়নের জন্য ছেদ-মুক্ত রচনা করা যেতে পারে, এবং যেহেতু এক্সওআর একটি ক্রসওভার তৈরি করার জন্য যথেষ্ট, এটি আমাদের প্রয়োজনীয় ক্রসওভার গ্যাজেট দেয়। সেয়টিন রূপান্তর হল সার্কিট-স্যাট থেকে স্যাটে সরাসরি হ্রাস। যদি সার্কিটটি সম্পূর্ণরূপে 2-ইনপুট ন্যান্ড গেট (বুলিয়ান অপারেটরদের একটি কার্যকরী-সম্পূর্ণ সেট) থেকে তৈরি করা হয় তবে রূপান্তরটি বর্ণনা করা সহজঃ সার্কিটের প্রতিটি নেটকে একটি পরিবর্তনশীল বরাদ্দ করুন, তারপরে প্রতিটি ন্যান্ড গেটের জন্য, কনজাংক্টিভ নরমাল ফর্ম ক্লজগুলি তৈরি করুন (v1Âv3) Â (v2Âv3) Â (Âv1Âv2Âv3Â), যেখানে v1 এবং v2 ন্যান্ড গেটের ইনপুট এবং v3 আউটপুট। এই ধারাগুলি তিনটি চলকের মধ্যে সম্পর্ককে সম্পূর্ণরূপে বর্ণনা করে। সার্কিটের আউটপুট পরিবর্তনশীলকে সত্য বলে সীমাবদ্ধ করে একটি অতিরিক্ত ধারার সাথে সমস্ত গেটের ধারাগুলিকে সংযুক্ত করা হ্রাসকে সম্পূর্ণ করে; সমস্ত সীমাবদ্ধতাকে সন্তুষ্ট করে এমন ভেরিয়েবলগুলির একটি অ্যাসাইনমেন্ট বিদ্যমান থাকে যদি এবং কেবলমাত্র যদি মূল সার্কিটটি সন্তোষজনক হয় এবং যে কোনও সমাধান সার্কিট আউটপুট তৈরি করে এমন ইনপুটগুলি খুঁজে বের করার মূল সমস্যার সমাধান হয়। বিপরীত-যে স্যাট সার্কিট-স্যাটে হ্রাসযোগ্য-বুলিয়ান সূত্রটিকে একটি সার্কিট হিসাবে পুনর্লিখন করে এবং এটি সমাধান করে তুচ্ছভাবে অনুসরণ করে। আরও দেখুন সার্কিট ভ্যালু প্রবলেম স্ট্রাকচার্ড সার্কিট স্যাটিসফায়েবিলিটি স্যাটিসফায়েবিলিটি প্রবলেম রেফারেন্স এনপি-সম্পূর্ণ সমস্যা গণনামূলক সমস্যা গণনামূলক তত্ত্ব