Majority problem
பெரும்பான்மை பிரச்சனை, அல்லது அடர்த்தி வகைப்பாட்டு பணி, பெரும்பான்மை வாக்களிப்பை துல்லியமாக செய்யும் ஒரு பரிமாண செல்லுலார் தானியங்கி விதிகளைக் கண்டுபிடிப்பதில் உள்ள சிக்கலாகும். உள்ளூர் மாற்ற விதிகளைப் பயன்படுத்தி, செல்கள் அமைப்பில் உள்ள அனைத்தின் மொத்த எண்ணிக்கையையும் அறிய முடியாது. ஒன்றின் எண்ணிக்கையை (அல்லது, சமச்சீர் மூலம், பூஜ்ஜியங்களின் எண்ணிக்கை) கணக்கிட, அமைப்புக்கு அமைப்பின் மொத்த அளவில் பிட்களின் மடக்கை எண் தேவைப்படுகிறது. கணினியின் அளவில் நேரியல் தூரத்தில் செய்திகளை அனுப்புவதற்கும், முறைசாரா மொழியை அடையாளம் காண்பதற்கும் அமைப்பு தேவைப்படுகிறது. எனவே, செல்லுலார் தானியங்கி அமைப்புகளின் கணக்கீட்டு சக்தியை அளவிடுவதில் இந்த சிக்கல் ஒரு முக்கியமான சோதனை வழக்கு. சிக்கல் அறிக்கை மொத்தம் i + j செல்கள் கொண்ட இரண்டு நிலை செல்லுலார் ஆட்டோமேட்டனின் உள்ளமைவைப் பொறுத்தவரை, அவற்றில் i பூஜ்ஜிய நிலையில் உள்ளது மற்றும் j ஒரே நிலையில் உள்ளது, வாக்களிக்கும் சிக்கலுக்கான சரியான தீர்வு இறுதியில் அனைத்து செல்களையும் பூஜ்ஜியமாக அமைக்க வேண்டும் i> j என்றால், இறுதியில் i <j என்றால் அனைத்து செல்களையும் ஒன்றாக அமைக்க வேண்டும். i = j என்றால் விரும்பிய இறுதி நிலை குறிப்பிடப்படவில்லை. பூஜ்ஜியங்கள் மற்றும் ஒன்றின் விகிதம் 50 சதவீதத்தைத் தவிர வேறு ஏதேனும் வரம்பிற்கு மேலே அல்லது கீழே உள்ளதா என்பதைச் சோதிப்பதற்கும் சிக்கலை பொதுமைப்படுத்தலாம். இந்த பொதுமைப்படுத்தலில், ஒருவருக்கு ஒரு வரம்பும் வழங்கப்படுகிறது; வாக்களிக்கும் பிரச்சினைக்கு ஒரு சரியான தீர்வு இறுதியில் அனைத்து செல்களையும் பூஜ்ஜியமாக அமைக்க வேண்டும் மற்றும் இறுதியில் அனைத்து செல்களையும் ஒன்றாக அமைக்க வேண்டும். விரும்பிய இறுதி நிலை குறிப்பிடப்படவில்லை என்றால். தோராயமான தீர்வுகள் காக்ஸ், குர்டியுமோவ் மற்றும் லெவின் ஒரு தானியங்கியைக் கண்டுபிடித்தனர், இது எப்போதும் பெரும்பான்மை சிக்கலை சரியாக தீர்க்கவில்லை என்றாலும், பல சந்தர்ப்பங்களில் அவ்வாறு செய்கிறது. சிக்கலுக்கான அவர்களின் அணுகுமுறையில், செல்லுலார் தானியங்கி விதியின் தரம் அது சரியாக வகைப்படுத்தும் சாத்தியமான தொடக்க உள்ளமைவுகளின் பகுதியால் அளவிடப்படுகிறது. கேக்ஸ், குர்டியுமோவ் மற்றும் லெவின் ஆகியோரால் முன்மொழியப்பட்ட விதி ஒவ்வொரு கலத்தின் நிலையையும் பின்வருமாறு அமைக்கிறது. ஒரு செல் 0 ஆக இருந்தால், அதன் அடுத்த நிலை அதன் மதிப்புகளில் பெரும்பான்மையாகவும், இடதுபுறத்தில் அதன் உடனடி அண்டை நாடாகவும், இடதுபுறத்தில் அதன் அண்டை மூன்று இடங்களாகவும் உருவாகிறது. மறுபுறம், ஒரு செல் 1 ஆக இருந்தால், அதன் அடுத்த நிலை சமச்சீராக உருவாகிறது, அதன் மதிப்புகளில் பெரும்பான்மையாக, வலதுபுறத்தில் அதன் உடனடி அண்டை, மற்றும் வலதுபுறத்தில் அதன் அண்டை மூன்று இடங்கள். சீரற்ற முறையில் உருவாக்கப்பட்ட நிகழ்வுகளில், இது பெரும்பான்மையை சரியாக தீர்மானிப்பதில் சுமார் 78 சதவீதம் துல்லியத்தை அடைகிறது. தாஸ், மிட்செல் மற்றும் க்ரட்ச்பீல்ட் ஆகியோர் மரபணு வழிமுறைகளைப் பயன்படுத்தி சிறந்த விதிகளை உருவாக்க முடியும் என்பதைக் காட்டினர். ஒரு சரியான வகைப்பாட்டின் சாத்தியமற்ற தன்மை 1995 ஆம் ஆண்டில், நிலமும் பெலூவும் ஆரம் r மற்றும் அடர்த்தி ρ கொண்ட இரு-நிலை விதி இல்லை என்பதைக் காட்டியது, செல்களின் எண்ணிக்கை போதுமான அளவு (சுமார் 4r/ρ ஐ விட பெரியது) இருக்கும்போது அனைத்து தொடக்க உள்ளமைவுகளிலும் வாக்களிக்கும் சிக்கலை சரியாக தீர்க்கிறது. அமைப்பு தீர்மானகரமானதாக இருப்பதால், பூஜ்ஜியங்கள் அல்லது ஒன்றுகளால் சூழப்பட்ட ஒவ்வொரு உயிரணுவும் பூஜ்ஜியமாக மாற வேண்டும் என்பதை அவர்களின் வாதம் காட்டுகிறது. அதேபோல், எந்தவொரு சரியான விதியும் ஒன்றின் விகிதம் கீழே இருந்தால் (அல்லது நேர்மாறாக) மேலே செல்ல முடியாது. எந்தவொரு கருதப்பட்ட சரியான விதியும் விகிதத்தை தள்ளிய தனிமைப்படுத்தப்பட்ட ஒன்றை ரத்து செய்ய வழிவகுக்கும் அல்லது, ஒன்றின் விகிதம் குறைவாக இருந்தால், தனிமைப்படுத்தப்பட்ட ஒன்று போலி ஒன்றை பூஜ்ஜியங்களின் தொகுதியாக அறிமுகப்படுத்த வழிவகுக்கும், இதனால் ஒருவரின் விகிதம் அதிகமாக மாறும். 2013 ஆம் ஆண்டில், புசிக், ஃபாடஸ், மார்கோவிச்சி மற்றும் மைரெஸ் ஆகியோர் ஒரு சரியான அடர்த்தி வகைப்பாட்டைக் கொண்டிருப்பது சாத்தியமற்றது என்பதற்கான எளிய ஆதாரத்தை வழங்கினர், இது தீர்மானகரமான மற்றும் சீரற்ற செல்லுலார் மற்றும் எந்த பரிமாணத்திற்கும் பொருந்தும். மாற்று பணிநீக்க நிபந்தனைகளுடன் சரியான தீர்வு கேப்காரெர், சிப்பர் மற்றும் டோமாஸினி ஆகியோர் கவனித்தபடி, தானியங்கி இயந்திரம் பெரும்பான்மையை அங்கீகரித்ததாகக் கூறப்படும் வரையறையை ஒருவர் தளர்த்தினால் பெரும்பான்மை சிக்கல் சரியாக தீர்க்கப்படலாம். குறிப்பாக, விதி 184 தானியங்கி இயந்திரத்தைப் பொறுத்தவரை, சுழற்சி எல்லை நிபந்தனைகளுடன் ஒரு வரையறுக்கப்பட்ட பிரபஞ்சத்தில் இயங்கும்போது, ஒவ்வொரு உயிரணுவும் எண்ணற்ற பெரும்பாலும் தொடர்ச்சியான இரண்டு படிகளுக்கு பெரும்பான்மை நிலையில் இருக்கும், அதே நேரத்தில் வரையறுக்கப்பட்ட பல முறை மட்டுமே தொடர்ச்சியாக இரண்டு படிகளுக்கு சிறுபான்மை நிலையில் இருக்கும். மாற்றாக, வரிசையின் அளவில் நேரியல் பல படிகளுக்கு விதி 184 ஐ இயக்கும் ஒரு கலப்பின தானியங்கி இயந்திரம், பின்னர் பெரும்பான்மை விதிக்கு மாறுகிறது (விதி 232), இது ஒவ்வொரு கலத்தையும் பெரும்பான்மைக்கும் அதன் அண்டை நாடுகளுக்கும் அமைக்கிறது, அனைத்து பூஜ்ஜியங்கள் அல்லது இறுதி நிலையில் உள்ள அனைவரின் நிலையான அங்கீகார அளவுகோலுடன் பெரும்பான்மை சிக்கலைத் தீர்க்கிறது. இருப்பினும், இந்த இயந்திரம் ஒரு செல்லுலார் தானியங்கி அல்ல. மேலும், ஃபுக்ஸின் கலப்பு விதி சத்தத்திற்கு மிகவும் உணர்திறன் கொண்டது என்றும், எந்த அளவிலான சத்தத்திற்கும் (எ. கா., சூழலில் இருந்து அல்லது மாறும் தவறுகளிலிருந்து) ஒரு அபூரண வகைப்பாட்டாளரான சத்தம் கொண்ட காஸ்-குர்டியுமோவ்-லெவின் ஆட்டோமேட்டனை விட சிறப்பாக செயல்பட முடியாது என்றும் காட்டப்பட்டுள்ளது. குறிப்புகள் செல்லுலார் தானியங்கி