ஒரு பல்லுறுப்புக்கோவை நேரத்தை தீர்மானிக்காத டூரிங் இயந்திரத்திலிருந்து ஒரு பல்லுறுப்புக்கோவை நேர சரிபார்ப்பானைக் கட்டமைக்கும் செயல்முறையை விவரிக்கவும்.

/ / வெளியிடப்பட்ட சைபர், EITC/IS/CCTF கணக்கீட்டு சிக்கலான கோட்பாடு அடிப்படைகள், சிக்கலான, NP மற்றும் பல்லுறுப்புறுப்பு சரிபார்ப்பு வரையறை, தேர்வு ஆய்வு

ஒரு பல்லுறுப்புக்கோவை நேர சரிபார்ப்பானது ஒரு பல்லுறுப்புக்கோவை நேரத்தை நிர்ணயிக்காத டூரிங் இயந்திரத்திலிருந்து (NTM) ஒரு முறையான செயல்முறையைப் பின்பற்றுவதன் மூலம் உருவாக்க முடியும். இந்த செயல்முறையைப் புரிந்து கொள்ள, சிக்கலான கோட்பாட்டின் கருத்துக்கள், குறிப்பாக P மற்றும் NP வகுப்புகள் மற்றும் பல்லுறுப்புக்கோவை சரிபார்ப்பு பற்றிய கருத்துக்கள் பற்றிய தெளிவான புரிதல் அவசியம்.

கணக்கீட்டு சிக்கலான கோட்பாட்டில், P என்பது முடிவெடுக்கும் சிக்கல்களின் வகுப்பைக் குறிக்கிறது, இது பல்லுறுப்புக்கோவை நேரத்தில் ஒரு தீர்மானகரமான டூரிங் இயந்திரத்தால் தீர்க்கப்பட முடியும். மறுபுறம், NP என்பது முடிவெடுக்கும் சிக்கல்களின் வகுப்பைக் குறிக்கிறது, அதற்கான தீர்வை ஒரு தீர்க்கமான டூரிங் இயந்திரம் மூலம் பல்லுறுப்புக்கோவை நேரத்தில் சரிபார்க்க முடியும். இந்த இரண்டு வகுப்புகளுக்கிடையேயான முக்கிய வேறுபாடு என்னவென்றால், P என்பது திறமையாக தீர்க்கப்படக்கூடிய சிக்கல்களைக் குறிக்கிறது, அதே நேரத்தில் NP என்பது திறமையாக சரிபார்க்கக்கூடிய சிக்கல்களைக் குறிக்கிறது.

ஒரு பல்லுறுப்புக்கோவை நேர சரிபார்ப்பு என்பது ஒரு தீர்மானிக்கும் டூரிங் இயந்திரமாகும், இது பல்லுறுப்புக்கோவை நேரத்தில் NP பிரச்சனைக்கான தீர்வின் சரியான தன்மையை சரிபார்க்க முடியும். NTM இன் பல்லுறுப்புக்கோவை நேரத்திலிருந்து அத்தகைய சரிபார்ப்பானைக் கட்டமைக்கும் செயல்முறை பின்வரும் படிகளை உள்ளடக்கியது:

1. ஒரு NP சிக்கலைக் கருத்தில் கொண்டு, X பிரச்சனை என்று வைத்துக்கொள்வோம், X ஐ தீர்க்கக்கூடிய ஒரு பல்லுறுப்புக்கோவை நேர NTM M இருப்பதைக் கருதுகிறோம். இந்த NTM M ஆனது கணக்கீட்டின் பல கிளைகளைக் கொண்டுள்ளது, ஒவ்வொன்றும் வெவ்வேறு சாத்தியமான செயலாக்கப் பாதையைக் குறிக்கும்.

2. NTM M இன் நடத்தையை உருவகப்படுத்துவதன் மூலம் X பிரச்சனைக்கான பல்லுறுப்புக்கோவை நேர சரிபார்ப்பான V ஐ உருவாக்குகிறோம். சரிபார்ப்பான V ஆனது இரண்டு உள்ளீடுகளை எடுக்கும்: X பிரச்சனைக்கான தீர்வு மற்றும் சான்றிதழ். தீர்வு சரியானது என்பதற்கான சான்று சான்றிதழ்.

3. சான்றிதழில் சரியான வடிவம் உள்ளதா என்பதைச் சரிபார்ப்பாளர் V முதலில் சரிபார்க்கும். சான்றிதழின் எதிர்பார்க்கப்படும் கட்டமைப்பை சரிபார்ப்பவருக்குத் தெரியும் என்பதால் இந்தப் படியை பல்லுறுப்புக்கோவை நேரத்தில் செய்ய முடியும்.

4. அடுத்து, சரிபார்ப்பு V ஆனது கொடுக்கப்பட்ட தீர்வு மற்றும் சான்றிதழில் NTM M இன் நடத்தையை உருவகப்படுத்துகிறது. இது M இன் கணக்கீட்டின் சாத்தியமான அனைத்து கிளைகளையும் செயல்படுத்துகிறது, எந்த கிளையும் உள்ளீட்டை ஏற்றுக்கொள்கிறதா என்று சரிபார்க்கிறது. NTM M பல்லுறுப்புக்கோவை நேரத்தில் இயங்குவதால் இந்த உருவகப்படுத்துதலை பல்லுறுப்புக்கோவை நேரத்தில் செய்ய முடியும்.

5. சரிபார்ப்பாளர் V குறைந்தபட்சம் ஒரு ஏற்றுக்கொள்ளும் கணக்கீட்டைக் கண்டறிந்தால், அது உள்ளீட்டை ஏற்றுக்கொள்கிறது. இதன் பொருள் X பிரச்சனைக்கான தீர்வு சரியானதா என சரிபார்க்கப்பட்டது. இல்லையெனில், கிளைகள் எதுவும் ஏற்கவில்லை என்றால், சரிபார்ப்பவர் உள்ளீட்டை நிராகரிப்பார்.

பல்லுறுப்புக்கோவை நேர சரிபார்ப்பானைக் கட்டமைப்பதற்கான முக்கிய யோசனை என்னவென்றால், NTM M ஆனது பல்லுறுப்புக்கோவை நேரத்தில் சரியான சான்றிதழை யூகிக்க முடியும். M இன் நடத்தையை உருவகப்படுத்துவதன் மூலமும், சாத்தியமான அனைத்து கிளைகளையும் சரிபார்ப்பதன் மூலமும், சரிபார்ப்பாளர் V தீர்வின் சரியான தன்மையை திறம்பட சரிபார்க்க முடியும்.

இந்த செயல்முறையை விளக்குவதற்கு ஒரு உதாரணத்தை எடுத்துக் கொள்வோம். கொடுக்கப்பட்ட வரைபடத்தில் ஹாமில்டோனியன் சுழற்சி உள்ளதா என்பதை தீர்மானிப்பதில் உள்ள சிக்கலைக் கவனியுங்கள், இது ஒரு NP-முழுமையான சிக்கலாகும். இந்தச் சிக்கலைத் தீர்க்கக்கூடிய பல்லுறுப்புக்கோவை நேர NTM M இருப்பதை நாங்கள் கருதுகிறோம்.

இந்தச் சிக்கலுக்கான பல்லுறுப்புக்கோவை நேர சரிபார்ப்பான V ஐ உருவாக்க, கொடுக்கப்பட்ட வரைபடம் மற்றும் சான்றிதழில் M இன் நடத்தையை உருவகப்படுத்துகிறோம். சான்றிதழ் சரியான ஹாமில்டோனியன் சுழற்சியை பிரதிநிதித்துவப்படுத்துகிறதா என்பதை சரிபார்ப்பவர் சரிபார்க்கிறார், அது ஒவ்வொரு உச்சியையும் சரியாக ஒருமுறை சென்று ஒரு சுழற்சியை உருவாக்குகிறது.

M இன் கணக்கீட்டின் அனைத்து சாத்தியமான கிளைகளையும் முழுமையாக உருவகப்படுத்துவதன் மூலம், கொடுக்கப்பட்ட வரைபடத்தில் ஹாமில்டோனியன் சுழற்சி உள்ளதா என்பதை சரிபார்ப்பவர் திறமையாக தீர்மானிக்க முடியும். M இன் ஒரு கிளையாவது உள்ளீட்டை ஏற்றுக்கொண்டால், சரிபார்ப்பவர் உள்ளீட்டை சரியான ஹாமில்டோனியன் சுழற்சியாக ஏற்றுக்கொள்கிறார். இல்லையெனில், அது உள்ளீட்டை நிராகரிக்கிறது.

ஒரு பல்லுறுப்புக்கோவை நேர NTM இலிருந்து ஒரு பல்லுறுப்புக்கோவை நேர சரிபார்ப்பை உருவாக்குவது NTM இன் நடத்தையை உருவகப்படுத்துவது மற்றும் கணக்கீட்டின் அனைத்து சாத்தியமான கிளைகளையும் சரிபார்க்கிறது. NP பிரச்சனைகளுக்கான தீர்வுகளை திறம்பட சரிபார்க்க இந்த செயல்முறை அனுமதிக்கிறது. அத்தகைய சரிபார்ப்பாளர்களை உருவாக்குவதன் மூலம், பல்லுறுப்புக்கோவை நேரத்தில் அவற்றின் சரிபார்ப்பின் அடிப்படையில் சிக்கல்களை வகைப்படுத்தலாம்.

தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் சிக்கலான:

சிக்கலில் மேலும் கேள்விகள் மற்றும் பதில்களைக் காண்க

மேலும் கேள்விகள் மற்றும் பதில்கள்:

குறித்துள்ளார்: , , , , ,