Pseudo-polynomial time
கணக்கீட்டு சிக்கலான கோட்பாட்டில், ஒரு எண் வழிமுறை போலி-பல்லுறுப்புக்கோவை நேரத்தில் இயங்குகிறது, அதன் இயங்கும் நேரம் உள்ளீட்டின் எண் மதிப்பில் (உள்ளீட்டில் இருக்கும் மிகப்பெரிய முழு எண்) ஒரு பல்லுறுப்புக்கோவை என்றால்-ஆனால் உள்ளீட்டின் நீளத்தில் அவசியமில்லை (அதைக் குறிக்கத் தேவையான பிட்களின் எண்ணிக்கை), இது பல்லுறுப்புக்கோவை நேர வழிமுறைகளுக்கு பொருந்தும். பொதுவாக, உள்ளீட்டின் எண் மதிப்பு உள்ளீட்டு நீளத்தில் அதிவேகமானது, அதனால்தான் ஒரு போலி-பல்லுறுப்புக்கோவை நேர வழிமுறை உள்ளீட்டு நீளத்தைப் பொறுத்தவரை பல்லுறுப்புக்கோவை நேரத்தில் இயங்க வேண்டிய அவசியமில்லை. அறியப்பட்ட போலி-பல்லுறுப்புக்கோவை நேர வழிமுறைகளுடன் ஒரு NP-முழுமையான சிக்கல் பலவீனமான NP-முழுமையானது என்று அழைக்கப்படுகிறது. ஒரு போலி-பல்லுறுப்புக்கோவை நேர வழிமுறை மூலம் தீர்க்க முடியாது என்று நிரூபிக்கப்பட்டால், ஒரு NP-முழுமையான சிக்கலை வலுவாக NP-முழுமையானது என்று அழைக்கப்படுகிறது. NP-கடினத்தன்மையின் வலுவான/பலவீனமான வகைகள் ஒத்த முறையில் வரையறுக்கப்படுகின்றன. எடுத்துக்காட்டுகள் முதன்மை சோதனை ஒரு எண் n பகா எண் என்பதைச் சோதிக்கும் சிக்கலைக் கவனியுங்கள், அதில் உள்ள எந்த எண்ணும் சமமாக வகுக்கப்படவில்லையா என்பதை அப்பாவித்தனமாகச் சரிபார்க்கவும். இந்த அணுகுமுறை பிரிவுகள் வரை எடுக்கலாம், இது n இன் மதிப்பில் துணை-நேரியல் ஆனால் n இன் நீளத்தில் அதிவேகமானது (இது சுமார்). எடுத்துக்காட்டாக, n இன் நீளம் 11 இலக்கங்கள் மட்டுமே என்றாலும், அதை விட சற்றே குறைவான ஒரு எண்ணுக்கு சுமார் 100,000 பிரிவுகள் தேவைப்படும். மேலும், இந்த வழிமுறை நடைமுறைக்கு சாத்தியமற்ற ஒரு உள்ளீட்டை (300 இலக்க எண் என்று சொல்லுங்கள்) ஒருவர் எளிதாக எழுதலாம். கணக்கீட்டு சிக்கலானது (குறியிடப்பட்ட) உள்ளீட்டின் நீளத்தைப் பொறுத்து சிரமத்தை அளவிடுவதால், இந்த அப்பாவித்தனமான வழிமுறை உண்மையில் அதிவேகமானது. இருப்பினும், இது போலி-பல்லுறுப்புக்கோவை நேரம். இந்த வழிமுறையை ஒரு உண்மையான பல்லுறுப்புக்கோவை எண் வழிமுறையுடன் ஒப்பிடுங்கள்-கூட்டலுக்கான நேரடியான வழிமுறைஃ இரண்டு 9 இலக்க எண்களைச் சேர்ப்பது சுமார் 9 எளிய படிகளை எடுக்கும், பொதுவாக வழிமுறை உள்ளீட்டின் நீளத்தில் உண்மையிலேயே நேரியல் ஆகும். சேர்க்கப்பட்ட உண்மையான எண்களுடன் ஒப்பிடும்போது (பில்லியன்களில்), வழிமுறையை "போலி-மடக்கை நேரம்" என்று அழைக்கலாம், இருப்பினும் அத்தகைய சொல் நிலையானது அல்ல. எனவே, 300 இலக்க எண்களைச் சேர்ப்பது நடைமுறைக்கு மாறானது அல்ல. இதேபோல், நீண்ட பிரிவு இருபடிஃ ஒரு m-இலக்க எண்ணை ஒரு n-இலக்க எண்ணால் படிகளில் வகுக்கலாம் (பிக் ஓ குறியீட்டைப் பார்க்கவும்). முதன்மைத்தன்மையைப் பொறுத்தவரை, n என்பது நேரத்திற்குள் இயங்குகிற பகா எண் (2002 இல் கண்டுபிடிக்கப்பட்டது) என்பதைச் சோதிப்பதற்கான வேறுபட்ட வழிமுறை உள்ளது. நாப்சாக் சிக்கல் நாப்சாக் சிக்கலில், எடை மற்றும் மதிப்புடன் கூடிய பொருட்கள் நமக்கு வழங்கப்படுகின்றன, அதோடு ஒரு நாப்சாக்கின் அதிகபட்ச எடை திறன். பின்வரும் உகப்பாக்கம் சிக்கலைத் தீர்ப்பதே குறிக்கோள்; முறைசாரா முறையில், மதிப்பை அதிகரிக்க பொருட்களை நாப்சாக்கில் பொருத்த சிறந்த வழி எது? மற்றும் க்கு உட்பட்டு அதிகரிக்கவும். இந்த சிக்கலைத் தீர்ப்பது NP-கடினமானது, எனவே ஒரு பல்லுறுப்புக்கோவை நேர வழிமுறை இல்லையென்றால் சாத்தியமற்றது. இருப்பினும், டைனமிக் நிரலாக்கத்தைப் பயன்படுத்தி ஒரு நேர வழிமுறை சாத்தியமாகும்; இந்த எண்ணை விவரிக்க பிட்கள் மட்டுமே தேவைப்படுவதால், இந்த வழிமுறை போலி-பல்லுறுப்புக்கோவை நேரத்தில் இயங்குகிறது. போலி-பல்லுறுப்புக்கோவை நேரம் என்ற கருத்து கிட்டத்தட்ட பிரத்தியேகமாக எண் சிக்கல்களுக்கு பயன்படுத்தப்பட்டாலும், கருத்தை பொதுமைப்படுத்தலாம்ஃ m (n) சிக்கல் அளவு n இன் பல்லுறுப்புக்கோவை செயல்பாட்டை விட அதிகமாக இல்லாவிட்டால் m செயல்பாடு போலி-பல்லுறுப்புக்கோவை மற்றும் உள்ளீட்டின் கூடுதல் பண்பு, k (n). (அநேகமாக, k என்பது சிக்கலுக்கு பொருத்தமான ஒன்றாகத் தேர்ந்தெடுக்கப்படுகிறது.) இது k ஐ உள்ளீட்டின் எண் மதிப்பாக எடுத்துக்கொள்வதன் மூலம் எண் பல்லுறுப்புக்கோவை சிக்கல்களை ஒரு சிறப்பு நிகழ்வாக ஆக்குகிறது. ஒரு எண்ணின் மதிப்புக்கும் அதன் நீளத்திற்கும் இடையிலான வேறுபாடு குறியீட்டில் ஒன்றாகும்ஃ எண் உள்ளீடுகள் எப்போதும் யூனரியில் குறியிடப்பட்டால், போலி-பல்லுறுப்புக்கோவை பல்லுறுப்புக்கோவையுடன் ஒத்துப்போகும். மேலும் காண்க வலுவான NP-முழுமையான அரை-பல்லுறுப்புக்கோவை நேர குறிப்புகள் வழிமுறைகளின் பகுப்பாய்வு சிக்கலான வகுப்புகள் கணக்கீட்டு சிக்கலான கோட்பாடு போலி-பல்லுறுப்புக்கோவை நேர வழிமுறைகள்