Vi anser att två spelare partiell observation stokastiska spel på finit-state grafer där spelare 1 har partiell observation och spelare 2 har perfekt observation. Det vinnande villkoret som vi studerar är vanliga förhållanden specificerade som paritetsmål. Det kvalitativa analysproblemet med tanke på ett partiellt observationsstokastiskt spel och ett paritetsmål frågar om det finns en strategi för att säkerställa att målet är uppfyllt med sannolikhet 1 (sp. positiv sannolikhet). Dessa kvalitativa analysproblem är kända för att vara obeslutsamma. I många tillämpningar är den relevanta frågan emellertid förekomsten av finita-minnesstrategier, och de kvalitativa analysproblemen under finita-minnesstrategier visade sig nyligen vara decimerbara i 2EXPTIME. Vi förbättrar komplexiteten och visar att de kvalitativa analysproblemen för partiell-observation stokastiska paritetsspel under finita-minnesstrategier är EXPTIM-komplett; och också etablera optimala (exponentiella) minnesgränser för finita-minnesstrategier som krävs för kvalitativ analys.
Det visade sig dock att fastställandet av finita-minnesstrategier för det kvalitativa problemet med objektiv paritetstillfredsställelse var fullständigt i REF.
The Complexity of Partial-observation Stochastic Parity Games With Finite-memory Strategies
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}