NP என்பது பல்லுறுப்புக்கோவை நேர சரிபார்ப்பாளர்களைக் கொண்ட மொழிகளின் வகுப்பாகும்
வகுப்பு NP, இது "நிர்ணையமற்ற பல்லுறுப்புக்கோவை நேரத்தை" குறிக்கிறது, இது கோட்பாட்டு கணினி அறிவியலின் துணைப் பகுதியான கணக்கீட்டு சிக்கலான கோட்பாட்டில் ஒரு அடிப்படைக் கருத்தாகும். NP ஐப் புரிந்து கொள்ள, முடிவெடுக்கும் சிக்கல்கள் பற்றிய கருத்தை ஒருவர் முதலில் புரிந்து கொள்ள வேண்டும், அவை ஆம்-அல்லது-இல்லை என்ற பதிலைக் கொண்ட கேள்விகளாகும். இந்த சூழலில் ஒரு மொழி என்பது சில எழுத்துக்களின் மீது உள்ள சரங்களின் தொகுப்பைக் குறிக்கிறது, அங்கு ஒவ்வொரு சரமும் ஒரு முடிவெடுக்கும் சிக்கலின் நிகழ்வை குறியாக்குகிறது.
(L) க்கு ஒரு பல்லுறுப்புக்கோவை-நேர சரிபார்ப்பு இருந்தால் ஒரு மொழி (L) NP இல் இருக்கும் என்று கூறப்படுகிறது. சரிபார்ப்பு என்பது இரண்டு உள்ளீடுகளை எடுக்கும் ஒரு நிர்ணய அல்காரிதம் (V) ஆகும்: ஒரு நிகழ்வு (x) மற்றும் ஒரு சான்றிதழ் (y). சான்றிதழ் (y) "சாட்சி" அல்லது "ஆதாரம்" என்றும் அறியப்படுகிறது. சரிபார்ப்பாளர் (V) சான்றிதழ் (y) (x) மொழிக்கு (L) சொந்தமானது என்பதை உறுதிப்படுத்துகிறதா என்பதைச் சரிபார்க்கிறது. முறைப்படி, ஒரு பல்லுறுப்புக்கோவை-நேர அல்காரிதம் (V) மற்றும் ஒரு பல்லுறுப்புக்கோவை (p(n)) இருந்தால், ஒரு மொழி (L) NP இல் இருக்கும், அதாவது ஒவ்வொரு சரத்திற்கும் (L இல் x), உடன் ஒரு சரம் (y) உள்ளது. |y|. leq p(|x|)) மற்றும் (V(x, y) = 1). மாறாக, ஒவ்வொரு சரத்திற்கும் (x notin L), (V(x, y) = 1) போன்ற சரம் (y) இல்லை.
இந்த கருத்தை தெளிவுபடுத்த, "பூலியன் திருப்தி" (SAT) இன் நன்கு அறியப்பட்ட சிக்கலைக் கவனியுங்கள். SAT சிக்கல், கொடுக்கப்பட்ட பூலியன் சூத்திரத்தில் மாறிகளுக்கு உண்மை மதிப்புகளின் ஒதுக்கீடு உள்ளதா என்று கேட்கிறது. SAT சிக்கல் NP இல் உள்ளது, ஏனெனில், பூலியன் சூத்திரம் (பை) மற்றும் அதன் மாறிகளுக்கு உண்மை மதிப்புகளின் ஒதுக்கீடு (ஆல்பா) கொடுக்கப்பட்டால், (ஆல்பா) திருப்தியடைகிறதா (பை) என்பதை பல்லுறுப்புக்கோவை நேரத்தில் ஒருவர் சரிபார்க்க முடியும். இங்கே, நிகழ்வு ( x ) என்பது பூலியன் சூத்திரம் ( ஃபை ), மற்றும் சான்றிதழ் ( y ) என்பது அசைன்மென்ட் ( ஆல்பா ) ஆகும். சரிபார்ப்பானது (V ) ( ஆல்ஃபா ) ( ஃபை ) உண்மையா என்பதைச் சரிபார்க்கிறது, இது ( ஃபை ) அளவைப் பொறுத்து பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம்.
மற்றொரு விளக்க உதாரணம் "ஹாமில்டோனியன் பாதை" பிரச்சனை. கொடுக்கப்பட்ட வரைபடத்தில் ஒவ்வொரு உச்சியையும் சரியாக ஒரு முறை பார்வையிடும் பாதை உள்ளதா என்று இந்தப் பிரச்சனை கேட்கிறது. ஹாமில்டோனியன் பாதைச் சிக்கல் NP யிலும் உள்ளது, ஏனெனில், ஒரு வரைபடம் (G ) மற்றும் செங்குத்துகளின் வரிசை (P ) கொடுக்கப்பட்டால், (P ) ( G ) இல் உள்ள ஹாமில்டோனியன் பாதையா என்பதை பல்லுறுப்புக்கோவை நேரத்தில் ஒருவர் சரிபார்க்க முடியும். இந்த வழக்கில், நிகழ்வு ( x ) என்பது வரைபடம் ( ஜி ), மற்றும் சான்றிதழ் ( y ) என்பது செங்குத்துகளின் வரிசை ( பி ) ஆகும். சரிபார்ப்பான் ( V ) ( P ) ஒரு ஹாமில்டோனியன் பாதையை உருவாக்குகிறதா என்பதைச் சரிபார்க்கிறது, இது (G ) அளவைப் பொறுத்து பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம்.
பல்லுறுப்புக்கோவை-நேரச் சரிபார்ப்பு என்ற கருத்து முக்கியமானது, ஏனெனில் இது தீர்வைக் கண்டறிவது கணக்கீட்டு ரீதியாக சாத்தியமற்றதாக இருந்தாலும், திறமையாகச் சரிபார்க்கக்கூடிய சிக்கல்களை வகைப்படுத்துவதற்கான வழியை வழங்குகிறது. இது (P = NP) என்ற பிரபலமான கேள்விக்கு இட்டுச் செல்கிறது, இது பல்லுறுப்புக்கோவை நேரத்தில் சரிபார்க்கக்கூடிய ஒவ்வொரு பிரச்சனையும் பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படுமா என்று கேட்கிறது. வர்க்கம் (P ) முடிவெடுக்கும் சிக்கல்களைக் கொண்டுள்ளது, இது ஒரு தீர்மானகரமான டூரிங் இயந்திரம் மூலம் பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படும். (P = NP ) எனில், பல்லுறுப்புக்கோவை-நேர சரிபார்ப்பானில் உள்ள ஒவ்வொரு பிரச்சனையும் ஒரு பல்லுறுப்புக்கோவை-நேர தீர்வையும் கொண்டுள்ளது என்று அர்த்தம். இந்த கேள்வி கணினி அறிவியலில் மிக முக்கியமான திறந்த பிரச்சனைகளில் ஒன்றாகும்.
NP இன் முக்கிய பண்புகளில் ஒன்று, அது பல்லுறுப்புக்கோவை-நேரக் குறைப்புகளின் கீழ் மூடப்பட்டுள்ளது. ஒரு மொழியிலிருந்து (L_1 ) இருந்து ஒரு மொழிக்கு ( L_2 ) பல்லுறுப்புக்கோவை நேரக் குறைப்பு என்பது ஒரு பல்லுறுப்புக்கோவை-நேரக் கணக்கிடக்கூடிய செயல்பாடு ( f ) அதாவது ( L_1 இல் x ) இருந்தால் மற்றும் இருந்தால் மட்டுமே ( L_2 இல் f(x) ). ( L_1 ) இலிருந்து ( L_2 ) க்கு பல்லுறுப்புக்கோவை நேரக் குறைப்பு இருந்தால் மற்றும் ( L_2 ) NP இல் இருந்தால், (L_1 ) NP யிலும் இருக்கும். NP இல் உள்ள "கடினமான" பிரச்சனைகளை அடையாளம் காட்டும் NP-முழுமை பற்றிய ஆய்வில் இந்த சொத்து கருவியாக உள்ளது. NP இல் இருந்தால் ஒரு சிக்கல் NP-நிறைவு மற்றும் NP இல் உள்ள ஒவ்வொரு பிரச்சனையும் பல்லுறுப்புக்கோவை நேரத்தில் குறைக்கப்படும். SAT பிரச்சனையானது NP-முழுமையானது என நிரூபிக்கப்பட்ட முதல் பிரச்சனையாகும், மேலும் இது மற்ற பிரச்சனைகளின் NP-முழுமையை நிரூபிக்கும் அடிப்படையாக செயல்படுகிறது.
பல்லுறுப்புக்கோவை-நேர சரிபார்ப்பு பற்றிய கருத்தை மேலும் விளக்க, "துணைத்தொகை" சிக்கலைக் கவனியுங்கள். இந்தச் சிக்கல், குறிப்பிட்ட இலக்கு மதிப்பின் கூட்டுத்தொகையில் கொடுக்கப்பட்ட முழு எண்களின் துணைக்குழு உள்ளதா என்று கேட்கிறது. துணைத்தொகை சிக்கல் NP இல் உள்ளது, ஏனெனில் முழு எண்களின் தொகுப்பு ( S ), இலக்கு மதிப்பு ( t ) மற்றும் ( S ) இன் துணைக்குழு ( S ' ) ஆகியவற்றைக் கொடுத்தால், ஒருவர் பல்லுறுப்புக் காலத்தில் உள்ள உறுப்புகளின் கூட்டுத்தொகையை சரிபார்க்க முடியும். (S') சமம் (t). இங்கே, நிகழ்வு ( x ) ஜோடி ( (S, t) ), மற்றும் சான்றிதழ் ( y ) துணைக்குழு ( S ' ) ஆகும். ( S ' ) இல் உள்ள உறுப்புகளின் கூட்டுத்தொகை ( t ) சமமாக உள்ளதா என்பதை சரிபார்ப்பு ( V ) சரிபார்க்கிறது, இது ( S ) அளவைப் பொறுத்து பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம்.
பல்லுறுப்புக்கோவை-நேர சரிபார்ப்பின் முக்கியத்துவம் கோட்பாட்டுப் பரிசீலனைகளுக்கு அப்பாற்பட்டது. நடைமுறை அடிப்படையில், NP இல் உள்ள சிக்கல்களுக்கு, முன்மொழியப்பட்ட தீர்வு (சான்றிதழ்) வழங்கப்பட்டால், அதை திறமையாக சரிபார்க்க முடியும். கிரிப்டோகிராஃபிக் நெறிமுறைகள், தேர்வுமுறைச் சிக்கல்கள் மற்றும் ஒரு தீர்வின் சரியான தன்மையைச் சரிபார்ப்பது முக்கியமான பல்வேறு துறைகளுக்கு இது குறிப்பிடத்தக்க தாக்கங்களைக் கொண்டுள்ளது.
சுருக்கமாக, NP வகுப்பானது முடிவெடுக்கும் சிக்கல்களை உள்ளடக்கியது, அதற்கான முன்மொழியப்பட்ட தீர்வை பல்லுறுப்புக்கோவை நேரத்தில் உறுதியான வழிமுறை மூலம் சரிபார்க்க முடியும். இந்தக் கருத்து கணக்கீட்டு சிக்கலான கோட்பாட்டில் அடித்தளமாக உள்ளது மற்றும் கணினி அறிவியலின் தத்துவார்த்த மற்றும் நடைமுறை அம்சங்களில் ஆழமான தாக்கங்களைக் கொண்டுள்ளது. NP, பல்லுறுப்புக்கோவை-நேரச் சரிபார்ப்பு மற்றும் NP-முழுமை போன்ற தொடர்புடைய கருத்துகளின் ஆய்வு, ஆராய்ச்சியின் துடிப்பான மற்றும் முக்கியமான பகுதியாகத் தொடர்கிறது.
தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் சிக்கலான:
- PSPACE வகுப்பு EXPSPACE வகுப்பிற்கு சமமாக இல்லையா?
- P சிக்கலான வகுப்பு என்பது PSPACE வகுப்பின் துணைக்குழுவா?
- ஒரு உறுதியான TM இல் எந்தவொரு NP முழுமையான பிரச்சனைக்கும் திறமையான பல்லுறுப்புக்கோவை தீர்வைக் கண்டுபிடிப்பதன் மூலம் Np மற்றும் P வகுப்பு ஒன்றுதான் என்பதை நிரூபிக்க முடியுமா?
- NP வகுப்பு EXPTIME வகுப்பிற்கு சமமாக இருக்க முடியுமா?
- அறியப்பட்ட NP அல்காரிதம் இல்லாத PSPACE இல் சிக்கல்கள் உள்ளதா?
- SAT பிரச்சனை ஒரு NP முழுமையான பிரச்சனையாக இருக்க முடியுமா?
- பல்நோக்கு நேரத்தில் அதைத் தீர்க்கும் நிர்ணயம் செய்யாத டூரிங் இயந்திரம் இருந்தால், NP சிக்கலான வகுப்பில் சிக்கல் இருக்க முடியுமா?
- P மற்றும் NP உண்மையில் ஒரே சிக்கலான வகுப்பா?
- பி சிக்கலான வகுப்பில் ஒவ்வொரு சூழலும் இலவச மொழியா?
- பல்லுறுப்புக்கோவை-நேரச் சரிபார்ப்பாளர்களுடனான முடிவெடுக்கும் சிக்கல்களின் வகுப்பாக NP இன் வரையறைக்கும், P வகுப்பில் உள்ள சிக்கல்களும் பல்லுறுப்புக்கோவை-நேர சரிபார்ப்பாளர்களைக் கொண்டிருப்பதற்கும் இடையே முரண்பாடு உள்ளதா?
சிக்கலில் மேலும் கேள்விகள் மற்றும் பதில்களைக் காண்க