Co-NP-complete
জটিলতা তত্ত্বে, সহ-এন. পি-সম্পূর্ণ গণনামূলক সমস্যাগুলি হল সেগুলি যা সহ-এন. পি-র সবচেয়ে কঠিন সমস্যা, এই অর্থে যে সহ-এন. পি-র যে কোনও সমস্যাকে যে কোনও সহ-এন. পি-সম্পূর্ণ সমস্যার একটি বিশেষ ক্ষেত্রে শুধুমাত্র বহুপদী ওভারহেড সহ পুনর্বিন্যাস করা যেতে পারে। যদি পি সহ-এনপি থেকে আলাদা হয়, তবে সহ-এনপি-সম্পূর্ণ সমস্ত সমস্যা বহুপদী সময়ে সমাধানযোগ্য নয়। যদি একটি কো-এনপি-সম্পূর্ণ সমস্যা দ্রুত সমাধান করার উপায় থাকে, তাহলে সেই অ্যালগরিদমটি সমস্ত কো-এনপি সমস্যা দ্রুত সমাধান করতে ব্যবহার করা যেতে পারে। প্রতিটি সহ-এনপি-সম্পূর্ণ সমস্যা একটি এনপি-সম্পূর্ণ সমস্যার পরিপূরক। এনপি এবং কো-এনপি উভয় ক্ষেত্রেই কিছু সমস্যা রয়েছে, উদাহরণস্বরূপ পি বা ইন্টিজার ফ্যাক্টরাইজেশনের সমস্ত সমস্যা। তবে, সেটগুলি সমান কিনা তা জানা যায় না, যদিও বৈষম্যের সম্ভাবনা বেশি বলে মনে করা হয়। আরও বিস্তারিত জানার জন্য কো-এন. পি এবং এন. পি-কমপ্লিট দেখুন। ফরচুন 1979 সালে দেখিয়েছিল যে কোনও বিরল ভাষা যদি সহ-এন. পি-সম্পূর্ণ (বা এমনকি কেবল সহ-এন. পি-কঠোর) হয়, তবে, মাহানির উপপাদ্যের জন্য একটি সমালোচনামূলক ভিত্তি। আনুষ্ঠানিক সংজ্ঞা একটি সিদ্ধান্ত সমস্যা সি সহ-এনপি-সম্পূর্ণ হয় যদি এটি সহ-এনপিতে থাকে এবং যদি সহ-এনপিতে প্রতিটি সমস্যা বহুপদী-সময় বহু-এক হ্রাসযোগ্য হয়। এর মানে হল যে প্রতিটি কো-এনপি সমস্যা এল-এর জন্য একটি বহুপদী সময় অ্যালগরিদম রয়েছে যা এল-এর যে কোনও দৃষ্টান্তকে একই সত্য মান সহ সি-এর উদাহরণে রূপান্তরিত করতে পারে। ফলস্বরূপ, যদি আমাদের কাছে সি-এর জন্য একটি পলিনোমিয়াল টাইম অ্যালগরিদম থাকে, তাহলে আমরা পলিনোমিয়াল সময়ে সমস্ত কো-এনপি সমস্যা সমাধান করতে পারি। উদাহরণ সহ-এন. পি-সম্পূর্ণ সমস্যার একটি উদাহরণ হল স্বরলিপি, একটি প্রদত্ত বুলিয়ান সূত্র একটি স্বরলিপি কিনা তা নির্ধারণের সমস্যা; অর্থাৎ, ভেরিয়েবলগুলিতে সত্য/মিথ্যা মানগুলির প্রতিটি সম্ভাব্য বরাদ্দ একটি সত্য বিবৃতি দেয় কিনা। এটি বুলিয়ান সন্তোষজনকতার সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত, যা জিজ্ঞাসা করে যে এ জাতীয় কমপক্ষে একটি অ্যাসাইনমেন্ট রয়েছে কিনা এবং এটি এনপি-সম্পূর্ণ। তথ্যসূত্র বাহ্যিক লিঙ্ক জটিলতা শ্রেণী