FKT algorithm
மைக்கேல் ஃபிஷர், பீட்டர் காஸ்டெலின் மற்றும் நெவில்லே டெம்பர்லி ஆகியோரின் பெயரால் பெயரிடப்பட்ட ஃபிஷர்-காஸ்டெலின்-டெம்பர்லி (எஃப். கே. டி) வழிமுறை, பல்லுறுப்புக்கோவை நேரத்தில் ஒரு பிளானர் வரைபடத்தில் சரியான பொருத்தங்களின் எண்ணிக்கையை கணக்கிடுகிறது. பொது வரைபடங்களுக்கு இதே பணி #P-முழுமையானது. சரியானதாக இருக்க வேண்டிய அவசியமில்லாத பொருத்தங்களுக்கு, அவற்றை எண்ணுவது பிளானர் வரைபடங்களுக்கு கூட #P-முழுமையானதாக இருக்கும். எஃப். கே. டி வழிமுறையின் முக்கிய யோசனை என்னவென்றால், சிக்கலை வரைபடத்தின் பிளானர் உட்பொதிப்பிலிருந்து பெறப்பட்ட வளைவு-சமச்சீர் மேட்ரிக்ஸின் ஃபாஃபியன் கணக்கீடாக மாற்றுவதாகும். இந்த மேட்ரிக்ஸின் ஃபாஃபியன் பின்னர் நிலையான தீர்மானிக்கும் வழிமுறைகளைப் பயன்படுத்தி திறம்பட கணக்கிடப்படுகிறது. பிளானர் சரியான பொருத்தங்களை எண்ணுவதில் உள்ள சிக்கல் புள்ளிவிவர இயக்கவியல் மற்றும் வேதியியலில் அதன் வேர்களைக் கொண்டுள்ளது, அங்கு அசல் கேள்விஃ இருமுனை மூலக்கூறுகள் ஒரு மேற்பரப்பில் உறிஞ்சப்பட்டு, ஒரு அடுக்கை உருவாக்கினால், அவற்றை எத்தனை வழிகளில் ஒழுங்கமைக்க முடியும்? பகிர்வு செயல்பாடு என்பது சமநிலையில் உள்ள ஒரு அமைப்பின் புள்ளிவிவர பண்புகளை குறியாக்கம் செய்யும் ஒரு முக்கியமான அளவு மற்றும் முந்தைய கேள்விக்கு பதிலளிக்க பயன்படுத்தப்படலாம். இருப்பினும், பகிர்வு செயல்பாட்டை அதன் வரையறையிலிருந்து கணக்கிட முயற்சிப்பது நடைமுறைக்குரியது அல்ல. எனவே ஒரு இயற்பியல் அமைப்பைத் துல்லியமாக தீர்ப்பது என்பது அந்த குறிப்பிட்ட இயற்பியல் அமைப்பிற்கான பகிர்வு செயல்பாட்டின் மாற்று வடிவத்தைக் கண்டுபிடிப்பதாகும், இது சரியாக கணக்கிட போதுமான எளிதானது. 1960 களின் முற்பகுதியில், சரியாக தீர்க்கக்கூடிய வரையறை கடுமையானதாக இல்லை. கணினி அறிவியல் பல்லுறுப்புக்கோவை நேரத்தின் அறிமுகத்துடன் ஒரு கடுமையான வரையறையை வழங்கியது, இது 1965 ஆம் ஆண்டைச் சேர்ந்தது. இதேபோல், இது போன்ற ஒரு எண்ணும் சிக்கலுக்கு சரியாக தீர்க்க முடியாத குறியீடு, 1979 இல் வரையறுக்கப்பட்ட #P-கடினத்தன்மைக்கு ஒத்திருக்க வேண்டும். கருத்தில் கொள்ள வேண்டிய மற்றொரு வகை இயற்பியல் அமைப்பு டைமர்களால் ஆனது, இது இரண்டு அணுக்களைக் கொண்ட பாலிமர் ஆகும். டைமர் மாதிரி ஒரு வரைபடத்தின் டைமர் உறைகளின் எண்ணிக்கையை கணக்கிடுகிறது. பரிசீலிக்க வேண்டிய மற்றொரு இயற்பியல் அமைப்பு பனி வடிவில் H2O மூலக்கூறுகளின் பிணைப்பு ஆகும். ஒவ்வொரு முனையிலும் உள்ள விளிம்புகளின் நோக்குநிலை ஒரே மாதிரியாக இருக்க முடியாத ஒரு திசை, 3-வழக்கமான வரைபடமாக இதை வடிவமைக்க முடியும். இந்த மாதிரியில் எத்தனை விளிம்பு நோக்குநிலைகள் உள்ளன? டைமர்கள் சம்பந்தப்பட்ட இயற்பியல் அமைப்புகளால் உந்தப்பட்டு, 1961 ஆம் ஆண்டில், பீட்டர் காஸ்டெலின் மற்றும் நெவில் டெம்பர்லி மற்றும் மைக்கேல் ஃபிஷர் ஆகியோர் சுயாதீனமாக m-by-n செவ்வகத்திற்கான டோமினோ சாய்வுகளின் எண்ணிக்கையைக் கண்டறிந்தனர். இது m-by-n லட்டிஸ் வரைபடத்திற்கான சரியான பொருத்தங்களின் எண்ணிக்கையை எண்ணுவதற்கு சமம். 1967 வாக்கில், காஸ்டெலின் இந்த முடிவை அனைத்து பிளானர் வரைபடங்களுக்கும் பொதுமைப்படுத்தினார். வழிமுறை விளக்கம் முக்கிய நுண்ணறிவு என்னவென்றால், G வரைபடத்தின் அருகிலுள்ள மேட்ரிக்ஸின் ஃபாஃபியனில் உள்ள பூஜ்ஜியமற்ற ஒவ்வொரு சொல்லும் ஒரு சரியான பொருத்தத்துடன் ஒத்திருக்கிறது. எனவே, ஃபாஃபியனில் உள்ள சொற்களின் அனைத்து அறிகுறிகளையும் சீரமைக்க G இன் நோக்குநிலையை ஒருவர் கண்டுபிடிக்க முடிந்தால் (+ அல்லது-இல்லை), பின்னர் ஃபாஃபியனின் முழுமையான மதிப்பு G இல் உள்ள சரியான பொருத்தங்களின் எண்ணிக்கையாகும். FKT வழிமுறை ஒரு பிளானர் கிராஃப் G க்கு அத்தகைய பணியைச் செய்கிறது. அது கண்டுபிடிக்கும் நோக்குநிலை ஒரு ஃபாஃபியன் நோக்குநிலை என்று அழைக்கப்படுகிறது. G = (V, E) அருகிலுள்ள மேட்ரிக்ஸ் A உடன் திசைதிருப்பப்படாத வரைபடமாக இருக்கட்டும். PM (n) ஐ n உறுப்புகளின் பகிர்வுகளின் தொகுப்பாக வரையறுக்கவும், பின்னர் G இல் சரியான பொருத்தங்களின் எண்ணிக்கை இதனுடன் நெருக்கமாக தொடர்புடையது, இது ஒரு n பை n மேட்ரிக்ஸ் A க்கான ஃபாஃபியன் ஆகும், அங்கு sgn (M) என்பது வரிசைமாற்றத்தின் அடையாளம் M. G இன் ஒரு ஃபாஃபியன் நோக்குநிலை என்பது pf (B) = PerfMatch (G) போன்ற அருகாமை மேட்ரிக்ஸ் B உடன் இயக்கப்படும் வரைபடம் H ஆகும். 1967 ஆம் ஆண்டில், பிளானர் வரைபடங்கள் திறம்பட கணக்கிடக்கூடிய ஃபாஃபியன் நோக்குநிலையைக் கொண்டுள்ளன என்பதை காஸ்டெலின் நிரூபித்தார். குறிப்பாக, ஒரு பிளானர் கிராஃப் G க்கு, H என்பது G இன் ஒரு இயக்க பதிப்பாக இருக்கட்டும், அங்கு G இன் பிளானர் உட்பொதிப்பில் ஒவ்வொரு முகத்திற்கும் ஒற்றைப்படை எண்ணிக்கையிலான விளிம்புகள் கடிகார திசையில் அமைந்துள்ளன. பின்னர் H என்பது G இன் ஃபாஃபியன் நோக்குநிலையாகும். இறுதியாக, எந்தவொரு வளைவு-சமச்சீர் மேட்ரிக்ஸ் A க்கும், டெட் (A) என்பது A இன் தீர்மானிப்பதாகும். இந்த முடிவு ஆர்தர் கெய்லியின் காரணமாகும். தீர்மானிப்பவர்கள் திறம்பட கணக்கிடக்கூடியவர்கள் என்பதால், பெர்ஃப்மேட்ச் (ஜி) ஆகும். உயர் மட்ட விளக்கம் ஜி-யின் பிளானர் உட்பொதிப்பைக் கணக்கிடுங்கள். உள்ளீட்டு வரைபடத்தின் டி 1 ஐக் கணக்கிடுங்கள். ஜி-இல் உள்ள ஒவ்வொரு விளிம்பிற்கும் டி 1 இல் உள்ள ஒரு தன்னிச்சையான நோக்குநிலையைக் கொடுங்கள். பிளானர் உட்பொதிப்பைப் பயன்படுத்தி G இன் இரட்டை வரைபடத்தைப் போலவே அதே உச்சியுடன் (திசைதிருப்பப்படாத) வரைபடம் T2 ஐ உருவாக்கவும். G இல் உள்ள அவற்றின் தொடர்புடைய முகங்கள் T1 இல் இல்லாத G இல் ஒரு விளிம்பைப் பகிர்ந்து கொண்டால் இரண்டு செங்குத்துகளுக்கு இடையில் T2 இல் ஒரு விளிம்பை உருவாக்கவும். (டி2 ஒரு மரம் என்பதைக் கவனியுங்கள்.) T2 இல் உள்ள ஒவ்வொரு இலைக்கும் (அது வேர் அல்ல): e என்பது இன்னும் ஒரு நோக்குநிலையைக் கொண்டிராத v உடன் தொடர்புடைய முகப்பில் G இன் தனி விளிம்பாக இருக்கட்டும். e க்கு ஒரு நோக்குநிலையைக் கொடுங்கள், அதாவது கடிகார வாரியாக நோக்கிய விளிம்புகளின் எண்ணிக்கை ஒற்றைப்படை. T2 இலிருந்து v ஐ அகற்றவும். G இன் அருகிலுள்ள மேட்ரிக்ஸின் ஃபாஃபியனின் முழுமையான மதிப்பைத் திருப்பித் தரவும், இது தீர்மானிப்பவரின் வர்க்கமூலமாகும். பொதுமைப்படுத்தல்கள் எடையுள்ள சரியான பொருத்தங்களின் கூட்டுத்தொகையை கடைசி கட்டத்தில் அருகிலுள்ள மேட்ரிக்ஸிற்கான டூட்டே மேட்ரிக்ஸைப் பயன்படுத்துவதன் மூலமும் கணக்கிடலாம். குரடோவ்ஸ்கியின் தேற்றம் ஒரு வரையறுக்கப்பட்ட வரைபடம் K5 (ஐந்து செங்குத்துகளில் முழுமையான வரைபடம்) அல்லது K3,3 (அளவு மூன்று கொண்ட இரண்டு பகிர்வுகளில் முழுமையான இருதரப்பு வரைபடம்) க்கு துணை வரைபட ஹோமியோமார்பிக் இல்லையென்றால் மட்டுமே அது சமதளமாக இருக்கும் என்று கூறுகிறது. விஜய் வஜிராணி FKT வழிமுறையை K3,3 க்கு ஒரு துணை கிராஃப் ஹோமியோமார்பிக் இல்லாத வரைபடங்களுக்கு பொதுமைப்படுத்தினார். ஒரு பொதுவான வரைபடத்தில் சரியான பொருத்தங்களின் எண்ணிக்கையை எண்ணுவது #P-முழுமையானது என்பதால், P இன் செயல்பாட்டு பதிப்பான FP, #P க்கு சமமாக இல்லாவிட்டால் உள்ளீட்டு வரைபடத்தில் சில கட்டுப்பாடுகள் தேவைப்படுகின்றன. ஹோசோயா குறியீடு என்று அழைக்கப்படும் எண்ணும் பொருத்தங்களும், பிளானர் வரைபடங்களுக்கு கூட #P-முழுமையானவை. பயன்பாடுகள் எஃப். கே. டி வழிமுறை மேட்ச்கேட்டுகள் வழியாக பிளானர் வரைபடங்களில் ஹாலோகிராஃபிக் வழிமுறைகளில் விரிவான பயன்பாட்டைக் கண்டுள்ளது. எடுத்துக்காட்டாக, மேலே குறிப்பிடப்பட்ட பனி மாதிரியின் பிளானர் பதிப்பைக் கவனியுங்கள், இது தொழில்நுட்பப் பெயரைக் கொண்டுள்ளது #PL-3-NAE-SAT (இங்கு NAE என்பது "அனைத்தும் சமமாக இல்லை" என்பதைக் குறிக்கிறது). வாலியன்ட் இந்த சிக்கலுக்கான ஒரு பல்லுறுப்புக்கோவை நேர வழிமுறையைக் கண்டறிந்தார், இது மேட்ச்கேட்டுகளைப் பயன்படுத்துகிறது. குறிப்புகள் வெளிப்புற இணைப்புகள் மேலும் வரலாறு, தகவல் மற்றும் எடுத்துக்காட்டுகளை டிமிட்ரி கமெனெட்ஸ்கியின் பிஎச்டி ஆய்வறிக்கை வரைபட வழிமுறைகள் பிளானர் வரைபடங்களின் அத்தியாயம் 2 மற்றும் பிரிவு 5.3 இல் காணலாம்.