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