MAX-3SAT
ম্যাক্স-3এসএটি হল কম্পিউটার বিজ্ঞানের গণনামূলক জটিলতা উপক্ষেত্রের একটি সমস্যা। এটি বুলিয়ান স্যাটিসফায়েবিলিটি প্রবলেম (এসএটি)-কে সাধারণীকরণ করে যা জটিলতা তত্ত্বে বিবেচিত একটি সিদ্ধান্ত সমস্যা। এটি এইভাবে সংজ্ঞায়িত করা হয়েছেঃ একটি 3-সি. এন. এফ সূত্র দেওয়া হয়েছে (অর্থাৎ। প্রতি ধারায় সর্বাধিক 3টি ভেরিয়েবল সহ), এমন একটি অ্যাসাইনমেন্ট খুঁজে বের করুন যা সর্বাধিক সংখ্যক ধারাকে সন্তুষ্ট করে। ম্যাক্স-3এসএটি জটিলতার শ্রেণী ম্যাক্সএসএনপি-র জন্য একটি ক্যানোনিকাল সম্পূর্ণ সমস্যা (পাপাদিমিত্রিউ পিজিতে সম্পূর্ণ দেখানো হয়েছে। 314)। আনুমানিক ম্যাক্স-3এসএটি-র সিদ্ধান্ত সংস্করণটি এনপি-সম্পূর্ণ। অতএব, একটি বহুপদী-সময় সমাধান কেবল তখনই অর্জন করা যেতে পারে যদি পি = এনপি হয়। এই সহজ অ্যালগরিদমের মাধ্যমে 2-এর গুণকের মধ্যে একটি আনুমানিক মান অর্জন করা যেতে পারে, তবেঃ সমাধানটি বের করুন যেখানে বেশিরভাগ ধারা সন্তুষ্ট হয়, যখন সমস্ত চলক = সত্য বা সমস্ত চলক = মিথ্যা হয়। প্রতিটি ধারা দুটি সমাধানের মধ্যে একটি দ্বারা সন্তুষ্ট হয়, তাই একটি সমাধান অন্তত অর্ধেক ধারাকে সন্তুষ্ট করে। কার্লফ-জউইক অ্যালগরিদম বহুপদী-সময়ে চলে এবং 7/8 ধারাকে সন্তুষ্ট করে। যদিও এই অ্যালগরিদমটি এলোমেলোভাবে তৈরি করা হয়েছে, এটি ব্যবহার করে বিচ্ছিন্ন করা যেতে পারে, উদাহরণস্বরূপ, একই আনুমানিক গ্যারান্টি সহ একটি নির্ধারক (বহুপদী-সময়) অ্যালগরিদম প্রদানের কৌশলগুলি। উপপাদ্য 1 (অসামঞ্জস্যতা) পিসিপি উপপাদ্যটি বোঝায় যে একটি ε> 0 রয়েছে যাতে ম্যাক্স-3স্যাটের (1-ε)-সামঞ্জস্য এনপি-হার্ড হয়। প্রমাণঃ পিসিপি উপপাদ্য দ্বারা যে কোনও এনপি-সম্পূর্ণ সমস্যা। x ω L-এর জন্য, একটি 3-CNF সূত্র তৈরি করা হয় যাতে x ω L ωx সন্তোষজনক হয় x ω L ωx-এর (1-ω) m ধারাগুলির চেয়ে বেশি সন্তোষজনক না হয়। ভেরিফায়ার ভি একবারে সমস্ত প্রয়োজনীয় বিট পড়ে। অ-অভিযোজিত প্রশ্ন করে। এটি বৈধ কারণ প্রশ্নের সংখ্যা স্থির থাকে। ধরা যাক q হল প্রশ্নের সংখ্যা। সমস্ত র্যান্ডম স্ট্রিং রি ω ভি গণনা করে, আমরা প্রতিটি স্ট্রিংয়ের দৈর্ঘ্য থেকে পলি (এক্স) স্ট্রিং পাই। প্রতিটি রি ভি-এর জন্য q অবস্থান i1,., iq এবং একটি বুলিয়ান ফাংশন fR: {0,1} q-> {0,1} বেছে নেয় এবং শুধুমাত্র যদি fR (π (i1,., iq)) গ্রহণ করে। এখানে π বলতে ওরাকল থেকে প্রাপ্ত প্রমাণকে বোঝায়। এরপরে আমরা এটি অনুকরণ করার জন্য একটি বুলিয়ান সূত্র খুঁজে বের করার চেষ্টা করি। আমরা বুলিয়ান চলক x1,., xl উপস্থাপন করছি, যেখানে l হল প্রমাণের দৈর্ঘ্য। ভেরিফায়ারটি সম্ভাব্য বহুপদী-সময়ে চলে তা দেখানোর জন্য, আমাদের সন্তোষজনক ধারাগুলির সংখ্যা এবং ভেরিফায়ার গ্রহণ করার সম্ভাবনার মধ্যে একটি যোগাযোগ প্রয়োজন। প্রতিটি আর-এর জন্য, 2কিউ এসএটি ধারা ব্যবহার করে এফআর (xi1,., xiq)-এর প্রতিনিধিত্বকারী ধারা যোগ করুন। দৈর্ঘ্য q-এর ধারাগুলি নতুন (সহায়ক) চলক যোগ করে দৈর্ঘ্য 3-এ রূপান্তরিত করা হয়। x2 * x10 * x11 * x12 = (x2 * x10 * yR) (R * x11 * x12)। এর জন্য সর্বোচ্চ q2q 3-SAT ধারা প্রয়োজন। যদি z ω L হয় তবে একটি প্রমাণ π থাকে যে Vπ (z) প্রতিটি Ri-এর জন্য গ্রহণ করে। সমস্ত ধারা সন্তুষ্ট হয় যদি xi = π (i) এবং সহায়ক চলকগুলি সঠিকভাবে যোগ করা হয়। যদি z′L ইনপুট করা হয় তবে x1,., xl এবং yR-এর প্রতিটি অ্যাসাইনমেন্টের জন্য, সংশ্লিষ্ট প্রমাণ π (i) = xi যাচাইকারীকে সমস্ত R ω {0,1} r (|z।)-এর অর্ধেকের জন্য প্রত্যাখ্যান করে। প্রতিটি আর-এর জন্য, এফআর-এর প্রতিনিধিত্বকারী একটি ধারা ব্যর্থ হয়। সুতরাং, ধারাগুলির একটি ভগ্নাংশ ব্যর্থ হয়। এই উপসংহারে আসা যায় যে, যদি এটি প্রতিটি এনপি-সম্পূর্ণ সমস্যার ক্ষেত্রে প্রযোজ্য হয়, তাহলে পিসিপি উপপাদ্য অবশ্যই সত্য হতে হবে। উপপাদ্য 2 হ্যাস্টাদ উপপাদ্য 1-এর তুলনায় একটি শক্ত ফলাফল প্রদর্শন করে। ε এর জন্য সর্বাধিক পরিচিত মান। তিনি 3-স্যাটের জন্য একটি পিসিপি ভেরিফায়ার তৈরি করেন যা প্রুফ থেকে মাত্র 3 বিট পড়ে। প্রতিটি ε> 0-এর জন্য, 3-স্যাটের জন্য একটি পিসিপি-ভেরিফায়ার এম রয়েছে যা দৈর্ঘ্যের একটি এলোমেলো স্ট্রিং r পড়ে এবং প্রমাণ π এবং একটি বিট বিআর-এ আইআর, জেআর, কেআর অনুসন্ধানের অবস্থান গণনা করে। এটি গ্রহণ করে যদি এবং শুধুমাত্র যদি 'π (IR) ωπ (JR) ωπ (kr) = br. ভেরিফায়ারের সম্পূর্ণতা (1−ε) এবং সুস্থতা 1/2 + ε (পিসিপি (জটিলতা) দেখুন) থাকে। যদি এই দুটি সমীকরণের মধ্যে প্রথমটিকে যথারীতি "= 1"-এর সমতুল্য করা হয়, তবে রৈখিক সমীকরণের একটি পদ্ধতি সমাধান করে π প্রমাণ পাওয়া যেতে পারে (ম্যাক্স-3লাইন-ইক্যুএন দেখুন) যার অর্থ পি = এনপি। যদি z ω L হয়, তবে ধারাগুলির একটি ভগ্নাংশ ω (1 − ε) সন্তুষ্ট হয়। যদি z′L হয়, তাহলে R-এর একটি (1/2−ε) ভগ্নাংশের জন্য 1/4 ধারা পরস্পরবিরোধী। আনুমানিক অনুপাতের কঠোরতা প্রমাণ করার জন্য এটি যথেষ্ট সম্পর্কিত সমস্যা ম্যাক্স-3এসএটি (বি) ম্যাক্স-3এসএটি-র সীমাবদ্ধ বিশেষ ক্ষেত্রে যেখানে প্রতিটি পরিবর্তনশীল সর্বাধিক বি ধারায় ঘটে। পিসিপি উপপাদ্য প্রমাণিত হওয়ার আগে, পাপাডিমিত্রিউ এবং ইয়ানাকাকিস দেখিয়েছিলেন যে কিছু স্থির ধ্রুবক বি-এর জন্য, এই সমস্যাটি ম্যাক্স এসএনপি-হার্ড। ফলস্বরূপ, পিসিপি উপপাদ্যের সাথে, এটি এপিএক্স-হার্ডও। এটি কার্যকর কারণ ম্যাক্স-3এসএটি (বি) প্রায়শই এমনভাবে পিটিএএস-সংরক্ষণ হ্রাস পেতে ব্যবহার করা যেতে পারে যা ম্যাক্স-3এসএটি করতে পারে না। বি-এর সুস্পষ্ট মানগুলির প্রমাণগুলির মধ্যে রয়েছেঃ সমস্ত বি ≤ 13, সঞ্জীব অরোরা, "প্রবেবিলিস্টিক চেকিং অফ প্রুফস অ্যান্ড হার্ডনেস অফ অ্যাপ্রক্সিমেশন প্রবলেম", 1994 সালের আগস্টে সিএস ডিভিশন, ইউসি বার্কলেতে জমা দেওয়া একটি গবেষণামূলক প্রবন্ধের সংশোধিত সংস্করণ। CS-TR-476-94। ধারা 7.2 এবং সমস্ত বি ≤3 (যা সর্বোত্তম সম্ভব)। অধিকন্তু, যদিও 2এসএটি সিদ্ধান্ত সমস্যাটি বহুপদী সময়ে সমাধানযোগ্য, ম্যাক্স-2এসএটি (3) ও এপিএক্স-হার্ড। বি-এর একটি ফাংশন হিসাবে ম্যাক্স-3এসএটি (বি)-এর জন্য সর্বোত্তম সম্ভাব্য আনুমানিক অনুপাত কমপক্ষে এবং সর্বাধিক, যদি না এনপি = আরপি হয়। বি-এর নির্দিষ্ট মানগুলির জন্য আনুমানিক ধ্রুবকের কিছু স্পষ্ট সীমা জানা যায়। বারম্যান, কার্পিনস্কি এবং স্কট প্রমাণ করেছেন যে ম্যাক্স-3এসএটি-র "সমালোচনামূলক" উদাহরণগুলির জন্য যেখানে প্রতিটি আক্ষরিক ঠিক দুবার ঘটে এবং প্রতিটি ধারা ঠিক 3 আকারের হয়, সমস্যাটি কিছু ধ্রুবক ফ্যাক্টরের জন্য আনুমানিক কঠিন। MAX-EkSAT হল MAX-3SAT-এর একটি প্যারামিটারাইজড সংস্করণ যেখানে প্রতিটি ধারার ঠিক আক্ষরিক অক্ষর রয়েছে, k "≤3-এর জন্য। কোডিং তত্ত্ব থেকে ধারণাগুলি ব্যবহার করে আনুমানিক অনুপাতের সাথে এটি দক্ষতার সাথে আনুমানিক করা যেতে পারে। এটি প্রমাণিত হয়েছে যে ম্যাক্স-3এসএটি-র এলোমেলো দৃষ্টান্তগুলি ফ্যাক্টরের মধ্যে আনুমানিক হতে পারে। ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়, বার্কলে থেকে রেফারেন্স লেকচার নোট কোডিং তত্ত্ব বাফেলো সন্তোষজনকতার বিশ্ববিদ্যালয়ের নোট এনপি-হার্ড সমস্যা