Berman–Hartmanis conjecture
கட்டமைப்பு சிக்கலான கோட்பாட்டில், பெர்மன்-ஹார்ட்மனிஸ் அனுமானம் என்பது லியோனார்ட் சி. பெர்மன் மற்றும் ஜூரிஸ் ஹார்ட்மனிஸ் ஆகியோரின் பெயரால் பெயரிடப்பட்ட ஒரு தீர்க்கப்படாத அனுமானமாகும், இது அனைத்து NP-முழுமையான மொழிகளும் ஒரே மாதிரியாக இருப்பதாகக் கூறுகிறது, அதாவது அவை பல்லுறுப்புக்கோவை நேர ஐசோமார்பிசம் மூலம் ஒருவருக்கொருவர் தொடர்புடையதாக இருக்கலாம். முறையான மொழிகளான L1 மற்றும் L2 க்கு இடையிலான ஒரு ஐசோமார்பிசம் என்பது L1 எழுத்துக்களில் உள்ள சரங்களிலிருந்து L2 எழுத்துக்களில் உள்ள சரங்கள் வரை ஒரு புறநிலை வரைபடமாகும், இதில் ஒரு சரம் x என்பது L1 க்கு சொந்தமானது, f (x) L2 க்கு சொந்தமானது என்றால் மட்டுமே. f மற்றும் அதன் தலைகீழ் செயல்பாடு இரண்டையும் அவற்றின் வாதங்களின் நீளங்களில் நேர பல்லுறுப்புக்கோவையில் கணக்கிட முடிந்தால் இது ஒரு பல்லுறுப்புக்கோவை நேர ஐசோமார்பிசம் (அல்லது சுருக்கமாக p-ஐசோமார்பிசம்) ஆகும். அந்த நேரத்தில் NP-முழுமையானதாக அறியப்பட்ட அனைத்து மொழிகளும் p-ஐசோமார்பிக் என்று கவனிக்கப்பட்டது. மேலும் வலுவாக, அப்போதைய அறியப்பட்ட அனைத்து NP-முழுமையான மொழிகளும் துடுப்பு போடக்கூடியவை என்பதை அவர்கள் கவனித்தனர், மேலும் அவை துடுப்பு போடக்கூடிய NP-முழுமையான மொழிகளின் அனைத்து ஜோடிகளும் p-ஐசோமார்பிக் என்பதை நிரூபித்தன (மைஹில் ஐசோமார்பிசம் தேற்றத்திற்கு ஒத்ததாக). ஒரு பல்லுறுப்புக்கோவை நேரச் செயல்பாடு f (x, y) ஒரு பல்லுறுப்புக்கோவை நேர தலைகீழாக இருந்தால் மற்றும் அனைத்து x மற்றும் y க்கும், x L க்கு சொந்தமானது மற்றும் f (x, y) L க்கு சொந்தமானது என்றால் மட்டுமேஃ அதாவது, உள்ளீடு x ஐ பொருத்தமற்ற தகவல்களுடன் y ஐ தலைகீழாக மாற்ற முடியும், மொழியில் அதன் உறுப்பினரை மாற்றாமல். இந்த முடிவுகளின் அடிப்படையில், பெர்மனும் ஹார்ட்மனிஸும் அனைத்து NP-முழுமையான மொழிகளும் p-ஐசோமார்பிக் என்று அனுமானித்தனர். p-ஐசோமார்பிசம் துடுப்பு போடும் திறனைப் பாதுகாப்பதால், துடுப்பு போடக்கூடிய NP-முழுமையான மொழிகள் இருப்பதால், பெர்மன்-ஹார்ட்மனிஸ் அனுமானத்தை குறிப்பிடுவதற்கான சமமான வழி என்னவென்றால், அனைத்து NP-முழுமையான மொழிகளும் துடுப்பு போடக்கூடியவை. பல்லுறுப்புக்கோவை நேர ஐசோமார்பிசம் என்பது ஒரு சமநிலை உறவாகும், மேலும் இது முறையான மொழிகளை சமநிலை வகுப்புகளாகப் பிரிக்கப் பயன்படுத்தப்படலாம், எனவே பெர்மன்-ஹார்ட்மனிஸ் அனுமானத்தைக் குறிப்பிடுவதற்கான மற்றொரு வழி என்னவென்றால், NP-முழுமையான மொழிகள் இந்த உறவுக்கு ஒற்றை சமநிலை வகுப்பை உருவாக்குகின்றன. தாக்கங்கள் பெர்மன்-ஹார்ட்மனியின் அனுமானம் உண்மையாக இருந்தால், குறுகிய NP-முழுமையான மொழிகள் இல்லாதது ஒரு உடனடி விளைவு, அதாவது n நீளத்தின் ஆம்-நிகழ்வுகளின் எண்ணிக்கை n இன் செயல்பாடாக பல்லுறுப்புக்கோவை ரீதியாக மட்டுமே வளரும் மொழிகள். அறியப்பட்ட NP-முழுமையான மொழிகள் அதிவேகமாக வளரும் பல ஆம்-நிகழ்வுகளைக் கொண்டுள்ளன, மேலும் L என்பது அதிவேகமாக பல ஆம்-நிகழ்வுகளைக் கொண்ட ஒரு மொழியாக இருந்தால், அது ஒரு சிறிய மொழிக்கு p-ஐசோமார்பிக் ஆக இருக்க முடியாது, ஏனெனில் அதன் ஆம்-நிகழ்வுகள் வரைபடம் ஒன்றுக்கு ஒன்று ஆக இருப்பதற்கு பல்லுறுப்புக்கோவை நீளத்தை விட அதிகமான சரங்களுக்கு வரைபடமாக்கப்பட வேண்டும். குறைவான NP-முழுமையான மொழிகள் இல்லாததால், P ≤ NP என்பதைக் குறிக்கிறது, ஏனெனில் P = NP என்றால், P இல் உள்ள ஒவ்வொரு அற்பமான மொழியும் (பைனரி சரங்களின் மொழி போன்ற சில அரிதானவை உட்பட, அவற்றின் பிட்கள் அனைத்தும் பூஜ்ஜியமாக இருக்கும்) NP-முழுமையானதாக இருக்கும். 1982 ஆம் ஆண்டில், ஸ்டீவ் மகனே தனது ஆதாரத்தை வெளியிட்டார், குறைவான NP-முழுமையான மொழிகள் இல்லாதது (பல-ஒரு குறைப்புகளைப் பயன்படுத்தி நிலையான வழியில் வரையறுக்கப்பட்ட NP-முழுமையுடன்) உண்மையில் P § NP என்ற கூற்றுக்கு சமம்; இது மகனேயின் தேற்றம். டூரிங் குறைப்புகளைப் பயன்படுத்தி NP-முழுமையின் ஒரு நிதானமான வரையறைக்கு கூட, ஒரு சிறிய NP-முழுமையான மொழி இருப்பது பல்லுறுப்புக்கோவை படிநிலையின் எதிர்பாராத சரிவைக் குறிக்கும். அனுமானத்திற்கு சான்றாக, ஒரு வரையறுக்கப்பட்ட வகை குறைப்புடன் கூடிய ஒத்த அனுமானம் உண்மை என்பதைக் காட்டுகிறதுஃ AC0 பல-ஒரு குறைப்புகளின் கீழ் NP க்கு முழுமையான ஒவ்வொரு இரண்டு மொழிகளும் AC0 ஐசோமார்பிசத்தைக் கொண்டுள்ளன. அனைத்து உள்ளீடுகளிலும் பல்லுறுப்புக்கோவை நேரத்தில் தலைகீழாக மாற்ற முடியாத ஒரு வழி செயல்பாடுகள் இருந்தால், ஆனால் அத்தகைய ஒவ்வொரு செயல்பாடும் பி/பாலியில் தலைகீழாக மாற்றக்கூடிய சிறிய ஆனால் அடர்த்தியான உள்ளீடுகளின் துணைக்குழுவைக் கொண்டிருந்தால் (இந்த வகையின் அறியப்பட்ட செயல்பாடுகளுக்கு உண்மை) பின்னர் ஒவ்வொரு இரண்டு என். பி-முழுமையான மொழிகளும் பி/பாலி ஐசோமார்பிசத்தைக் கொண்டுள்ளன. மேலும் ஒரு ஆரக்கிள் இயந்திர மாதிரியைக் கண்டறிந்தார், அதில் ஐசோமார்பிசம் யூகத்தின் ஒப்புமை உண்மை. அனுமானத்திற்கு எதிரான சான்றுகள் மற்றும் மூலம் வழங்கப்பட்டன. ஜோசப் மற்றும் யங் NP-முழுமையான சிக்கல்களின் ஒரு வகுப்பை அறிமுகப்படுத்தினர், K-கிரியேட்டிவ் செட், இதற்காக நிலையான NP-முழுமையான சிக்கல்களுக்கு p-ஐசோமார்பிசம் எதுவும் அறியப்படவில்லை. கர்ட்ஸ் மற்றும் பலர். ஒரு சீரற்ற ஆரக்கிள் அணுகல் கொடுக்கப்பட்ட ஆரக்கிள் இயந்திர மாதிரிகள், அனுமானம் ஒப்புமை உண்மை இல்லை என்று காட்டியதுஃ A ஒரு சீரற்ற ஆரக்கிள் என்றால், பின்னர் என். பி. ஏ முழு அனைத்து செட் PA இல் ஐசோமார்பிசம் இல்லை. சீரற்ற ஆரக்கிள் பொதுவாக கணிப்பு ரீதியாக சீரற்ற இருந்து பிரித்தறிய முடியாத என்று குறியாக்க ஹாஷ் செயல்பாடுகள் மாதிரி குறியாக்கவியல் கோட்பாட்டில் பயன்படுத்தப்படுகின்றன, மற்றும் கர்ட்ஸ் மற்றும் பலர் கட்டுமானம். ஆரக்கிளுக்கு பதிலாக அத்தகைய செயல்பாட்டை மேற்கொள்ளலாம். இந்த காரணத்திற்காக, மற்றவற்றுடன், பெர்மன்-ஹார்ட்மனிஸ் ஐசோமார்பிசம் அனுமானம் பல சிக்கலான கோட்பாட்டாளர்களால் தவறானது என்று நம்பப்படுகிறது. குறிப்புகள் கட்டமைப்பு சிக்கல் கோட்பாடு கணினி அறிவியலில் தீர்க்கப்படாத சிக்கல்களை கணிதத்தில் தீர்க்கப்படாத சிக்கல்களை ஊகிக்கிறது