Poset game
ஒருங்கிணைந்த விளையாட்டு கோட்பாட்டில், பொசெட் விளையாட்டுகள் மூலோபாயத்தின் கணித விளையாட்டுகளாகும், இது நிம் மற்றும் சோம்ப் போன்ற பல நன்கு அறியப்பட்ட விளையாட்டுகளை பொதுமைப்படுத்துகிறது. இத்தகைய விளையாட்டுகளில், இரண்டு வீரர்கள் ஒரு பொசெட்டுடன் (ஓரளவு வரிசைப்படுத்தப்பட்ட செட்) தொடங்கி, மாறி மாறி ஒரு புள்ளியைத் தேர்ந்தெடுத்து, அதை அகற்றி, மேலும் அதிக புள்ளிகள் அனைத்தையும் தேர்வு செய்கிறார்கள். தேர்வு செய்ய எந்த புள்ளியும் இல்லாத வீரர், இழக்கிறார். வழக்கமாக ஆலிஸ் மற்றும் பாப் என்று பெயரிடப்பட்ட இரண்டு வீரர்களிடையே விளையாடப்படும் பி-யில் ஒரு பொசெட் கேம், பின்வருமாறுஃ ஆலிஸ் ஒரு புள்ளி x Π ஐத் தேர்வு செய்கிறார், இதனால் பி-க்கு பதிலாக பிஎக்ஸ்-ஐ மாற்றுகிறார், பின்னர் பிஎக்ஸில் விளையாடும் பாபிடம் திருப்பத்தை அனுப்புகிறார், மேலும் ஆலிஸிடம் திருப்பத்தை அனுப்புகிறார். ஒரு வீரர் தனது முறை என்றால் இழக்கிறார் மற்றும் தேர்வு செய்ய புள்ளிகள் இல்லை. எடுத்துக்காட்டுகள் P என்பது ஒரு வரையறுக்கப்பட்ட முற்றிலும் வரிசைப்படுத்தப்பட்ட தொகுப்பாக இருந்தால், P இல் கேம் பிளே என்பது |P | அளவு குவியலுடன் நிம் விளையாட்டில் கேம் பிளே போலவே இருக்கும். ஏனெனில், இரண்டு விளையாட்டுகளிலும், |P | ஐ விட எந்த எண்ணும் சிறியதாக இருக்கும் அதே வகை விளையாட்டுக்கு வழிவகுக்கும் ஒரு நகர்வை தேர்வு செய்ய முடியும். அதே வழியில், மொத்த ஆர்டர்களின் வேறுபட்ட ஒன்றிணைப்பைக் கொண்ட ஒரு பொசெட் கேம், பொசெட்டில் உள்ள சங்கிலிகளுக்கு சமமான அளவுகளைக் கொண்ட பல குவியல்களைக் கொண்ட நிம் விளையாட்டுக்கு சமம். ஹேக்கன்பஷின் ஒரு சிறப்பு வழக்கு, இதில் அனைத்து விளிம்புகளும் பச்சை நிறத்தில் உள்ளன (எந்த வீரரும் வெட்ட முடியும்) மற்றும் ஒவ்வொரு உள்ளமைவும் ஒரு காட்டின் வடிவத்தை எடுக்கிறது, இதேபோல் வெளிப்படுத்தப்படலாம், ஒரு போசெட்டில் ஒரு பொசெட் விளையாட்டாக, இதில் ஒவ்வொரு உறுப்புக்கும் x, அதிகபட்சம் ஒரு உறுப்பு y உள்ளது, இதற்கு x y ஐ உள்ளடக்கியது. x என்பது y ஐ உள்ளடக்கியிருந்தால், y என்பது விளையாட்டு விளையாடப்படும் காட்டில் x இன் பெற்றோர். சம்ப் இதேபோல் வெளிப்படுத்தப்படலாம், மொத்த ஆர்டர்களின் உற்பத்தியின் மீது ஒரு பொசெட் விளையாட்டாக, அதில் இருந்து அதிகபட்சம் அகற்றப்பட்டுள்ளது. கிரண்டி மதிப்பு போஸட் விளையாட்டுகள் பக்கச்சார்பற்ற விளையாட்டுகளாகும், அதாவது ஆலிஸ் செல்ல அனுமதிக்கப்பட்டால் ஆலிஸுக்கு கிடைக்கும் ஒவ்வொரு நகர்வும் பாபுக்கும் கிடைக்கும், மேலும் நேர்மாறாகவும் இருக்கும். எனவே, ஸ்ப்ரேக்-கிரண்டி தேற்றத்தின் படி, ஒரு பொசெட் விளையாட்டில் உள்ள ஒவ்வொரு நிலையும் ஒரு கிரண்டி மதிப்பைக் கொண்டுள்ளது, இது நிம் விளையாட்டில் சமமான நிலையை விவரிக்கும் எண். ஒரு பொசெட்டின் கிரண்டி மதிப்பை குறைந்தபட்ச இயற்கை எண்ணாக கணக்கிடலாம், இது எந்த Px, x Π இன் கிரண்டி மதிப்பு அல்ல. அதாவது, இந்த எண் ஒரு பொசெட் விளையாட்டில் உகந்த விளையாட்டு விளையாட்டை விவரிக்க பயன்படுத்தப்படலாம். குறிப்பாக, கிரண்டி மதிப்பு பூஜ்ஜியமற்றது, எந்த வீரரின் முறை அது ஒரு வெற்றி மூலோபாயத்தைக் கொண்டிருக்கும் போது, தற்போதைய வீரர் தனது எதிரியிடமிருந்து உகந்த விளையாட்டுக்கு எதிராக வெற்றி பெற முடியாதபோது பூஜ்ஜியம். விளையாட்டில் ஒரு வெற்றி மூலோபாயம் என்பது கிரண்டி மதிப்பு பூஜ்ஜியமாக இருக்கும் நிலைக்கு மாறுவதைக் கொண்டுள்ளது, இது சாத்தியமான போதெல்லாம். மூலோபாயம் திருடுதல் ஒரு மூலோபாயம் திருடும் வாதம் ஒரு மேலாதிக்கத்தைக் கொண்ட ஒவ்வொரு நிலைக்கும் கிரண்டி மதிப்பு பூஜ்ஜியமற்றது என்பதைக் காட்டுகிறது. ஏனெனில், x என்பது ஒரு ஓரளவு வரிசைப்படுத்தப்பட்ட தொகுப்பு P இன் மேலாதிக்கமாக இருக்கட்டும். Px க்கு கிரண்டி மதிப்பு பூஜ்ஜியமாக இருந்தால், மேலே உள்ள சூத்திரத்தின் படி P க்கு ஒரு பூஜ்ஜியமற்ற மதிப்பு உள்ளது. இந்த விஷயத்தில், x என்பது P இல் ஒரு வெற்றி நகர்வாகும். மறுபுறம், Px க்கு பூஜ்ஜியமற்ற கிரண்டி மதிப்பு இருந்தால், Px இல் ஒரு வெற்றி நகர்வு y இருக்க வேண்டும், அதாவது (Px) y இன் கிரண்டி மதிப்பு பூஜ்ஜியமாகும். ஆனால் x என்பது ஒரு மேல்நிலை, x> y மற்றும் (Px) y = பை என்ற அனுமானத்தின் மூலம், வெற்றி நகர்வு y என்பது P இல் கிடைக்கிறது, மீண்டும் P ஒரு பூஜ்ஜியமற்ற கிரண்டி மதிப்பைக் கொண்டிருக்க வேண்டும். மிகவும் அற்பமான காரணங்களுக்காக, முடிவிலியைக் கொண்ட ஒரு நிலை பூஜ்ஜியமற்ற கிரண்டி மதிப்பைக் கொண்டுள்ளதுஃ முடிவிலிக்கு நகர்வது எப்போதும் ஒரு வெற்றிகரமான நடவடிக்கையாகும். சிக்கலானது ஒரு தன்னிச்சையான வரையறுக்கப்பட்ட நிலை விளையாட்டின் வெற்றியாளரை தீர்மானிப்பது பி. எஸ். பி. ஏ. சி. இ-முழுமையானது. இதன் பொருள் என்னவென்றால், P = PSPACE இல்லையென்றால், ஒரு தன்னிச்சையான நிலை விளையாட்டின் கிரண்டி மதிப்பை கணக்கிடுவது கணக்கீட்டு ரீதியாக கடினம். குறிப்புகள் ஒருங்கிணைந்த விளையாட்டு கோட்பாடு கணித விளையாட்டுகள்