Tentai Show
டென்டாய் ஷோ (டென்டாய் ஷோ), டென்டைஷோ, விண்மீன் திரள்கள், சுழல் விண்மீன் திரள்கள் அல்லது சிம்-ஏ-பிக்ஸ் என்ற பெயர்களாலும் அழைக்கப்படுகிறது, இது நிக்கோலியால் வெளியிடப்பட்ட பைனரி-தீர்மானிக்கும் தர்க்க புதிர் ஆகும். விதிகள் டென்டாய் ஷோ சதுரங்களின் செவ்வக கட்டத்தில் விளையாடப்படுகிறது. மின்தொகுப்பில் நட்சத்திரங்களைக் குறிக்கும் புள்ளிகள் உள்ளன, அவை மின்தொகுப்பில் ஒரு கலத்தின் மையத்திலோ, விளிம்பிலோ அல்லது மூலையிலோ காணப்படுகின்றன. புதிரின் நோக்கம் கட்டத்தை விண்மீன் திரள்களைக் குறிக்கும் பகுதிகளாகப் பிரிக்க கோடு கோடுகள் வழியாக கோடுகளை வரைய வேண்டும். இதன் விளைவாக உருவாகும் கட்டத்தில், அனைத்து விண்மீன் திரள்களும் 180 டிகிரி சுழற்சி சமச்சீர்மையைக் கொண்டிருக்க வேண்டும் மற்றும் அதன் மையத்தில் சரியாக ஒரு புள்ளியைக் கொண்டிருக்க வேண்டும். புள்ளிகளின் நிறங்கள் புதிரின் தர்க்கத்தை பாதிக்காது மற்றும் தீர்க்கும் போது புறக்கணிக்கப்படலாம். பல வண்ண புள்ளிகளைக் கொண்ட புதிர்களில், ஒரு படத்தை வெளிப்படுத்த முடிக்கப்பட்ட கட்டத்தின் பகுதிகள் தொடர்புடைய புள்ளி வண்ணங்களுடன் வண்ணமயமாக்கப்படலாம். தீர்வு முறைகள் டென்டாய் ஷோ புதிர்கள் பின்வரும் படிகளைப் பயன்படுத்தி தீர்க்கப்படலாம். ஒரு புள்ளி அல்லது ஒரு புள்ளியின் ஒரு பகுதியைக் கொண்ட அருகிலுள்ள செல்களுக்கு இடையில் சுவர்களை வரையவும். இந்த செல்கள் வெவ்வேறு விண்மீன் திரள்களைச் சேர்ந்தவையாக இருக்க வேண்டும். சுழற்சி சமச்சீர் படி புள்ளியைச் சுற்றி சுவர்களை வரையவும். கட்டத்தின் எல்லைகளும் சுவர்களாக கணக்கிடப்படுகின்றன. ஒரு புள்ளியால் 'கைப்பற்றப்பட்ட' பகுதிகளில் உள்ள செல்களைக் கண்டறியவும். இவை வேறு எந்த புள்ளியாலும் அடைய முடியாத செல்கள். இந்த செல்கள் அந்த புள்ளிக்கு விண்மீன் மண்டலத்திற்கு மட்டுமே சொந்தமானவை. புதிர் தீர்க்கப்படும் வரை மேலே உள்ள படிகளை மீண்டும் செய்யலாம். மேலும் மேம்பட்ட புதிர்களில், சுழற்சி சமச்சீரின் உருவத்தைக் கருத்தில் கொள்வது அவசியமாக இருக்கலாம். அதன் சுழற்சி சமச்சீர் கலத்தைக் கருத்தில் கொள்ளும்போது ஒரு செல்லுபடியாகும் புள்ளியை மட்டுமே கொண்ட செல்களைக் கண்டறியவும். அதன் சமச்சீர் உயிரணுவும் அந்த விண்மீன் மண்டலத்தைச் சேர்ந்ததாக இருந்தால் ஒரு செல் ஒரு விண்மீன் மண்டலத்தைச் சேர்ந்ததாக இருக்கலாம். புதிர் பெயர், "டென்டாய் ஷோ", ஜப்பானிய மொழியில் விளக்கும்போது இரட்டை அர்த்தத்தைக் கொண்டுள்ளது. "பத்து" என்பது புள்ளியைக் குறிக்கிறது, அதே நேரத்தில் "தாய் ஷோ" என்பது சமச்சீர்மையைக் குறிக்கிறது. வானியல் பொருட்களைக் குறிக்க ஜப்பானிய வார்த்தையான "டென்டாய்" பயன்படுத்தப்படுகிறது. ஒன்றாக இணைந்து, "டென்டாய் ஷோ" என்பது சுழற்சி சமச்சீர் மற்றும் வானியல் காட்சி ஆகிய இரண்டையும் குறிக்கலாம். கணக்கீட்டு சிக்கலானது NP-முழுமை ஒரு டென்டாய் ஷோ புதிர் ஒரு தீர்வைக் கொண்டிருக்கிறதா என்பதை தீர்மானிப்பது NP-முழுமையானது என்று அறியப்படுகிறது. தன்னிச்சையான பூலியன் சுற்றுகளுக்கு சமமான புதிர்களை உருவாக்குவதன் மூலம் ஃப்ரீட்மேன் (2002) இதை நிரூபித்தார், இது பூலியன் திருப்திகரமான சிக்கலின் காரணமாக NP-முழுமையைக் காட்டுகிறது. ஃபெர்டின், ஜாம்ஷிடி மற்றும் கொமுசீவிக்ஸ் (2015) அனைத்து விண்மீன் திரள்களும் அதிகபட்சம் ஏழு அளவு கொண்டிருக்கும்போது புதிர் NP-முழுமையானது என்பதை நிரூபிப்பதன் மூலம் இந்த முடிவை வலுப்படுத்தினர். ஆதாரம் புதிரை பாசிட்டிவ் பிளானர் 1-இன்-3-SAT ஆகக் குறைக்கிறது, இது NP-முழுமையானது என்று அறியப்படுகிறது. அனைத்து விண்மீன் திரள்களும் 1 × 1,1 × 3 அல்லது 3 × 1 அளவிலான செவ்வகங்களாக மட்டுப்படுத்தப்பட்டிருந்தாலும், டெமைன், லோஃப்லர் மற்றும் ஷ்மிட் (2021) என்பி-முழுமையை நிரூபிப்பதன் மூலம் இதை மேலும் வலுப்படுத்தினர். கொடுக்கப்பட்ட வடிவத்தை சரியாக உள்ளடக்கிய குறைந்தபட்ச விண்மீன் திரள்களைக் கண்டுபிடிப்பது NP-முழுமையானது என்பதையும் அவர்கள் காட்டினர். தீர்வு வழிமுறைகள் டென்டாய் ஷோ புதிர்கள் கட்டத்தின் சாத்தியமான அனைத்து துண்டுகளையும் கடந்து சென்று அது ஒரு சரியான தீர்வாக இருக்கிறதா என்று சரிபார்ப்பதன் மூலம் அதிவேக நேரத்தில் தீர்க்கப்படலாம். ஃபெர்டின், ஜாம்ஷிடி மற்றும் கொமுசீவிக்ஸ் (2015) பல்வேறு நிகழ்வுகளுக்கான புதிரைத் தீர்க்கக்கூடிய ஒரு பல்லுறுப்புக்கோவை-நேர வழிமுறையைக் காட்டினர், அதாவதுஃ (அ) அனைத்து விண்மீன் திரள்களும் அதிகபட்சம் இரண்டு அளவைக் கொண்டிருக்கும்போது, (ஆ) அனைத்து விண்மீன் திரள்களும் சதுரங்களாக இருக்கும்போது, (இ) அனைத்து விண்மீன் திரள்களும் அற்பமாக இணைக்கப்படும்போது. மேலும் காண்கஃ நிக்கோலி புதிர் வகைகளின் பட்டியல் குறிப்புகள் லாஜிக் புதிர்கள் NP-முழுமையான சிக்கல்கள்