DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS

Autor:	Merlijn Sevenster
Rok vydání:	2014
Předmět:	Combinatorics Prefix Philosophy Independence-friendly logic Logic Quantifier (linguistics) Independence (mathematical logic) Descriptive complexity theory Expressive power Mathematics Decidability
Zdroj:	The Journal of Symbolic Logic. 79:1224-1246
ISSN:	1943-5886 0022-4812
Popis:	We study the expressive power of independence-friendly quantifier prefixes composed of universal$\left( {\forall x/X} \right)$, existential$\left( {\exists x/X} \right)$, and majority quantifiers$\left( {Mx/X} \right)$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of$\forall x$,$\exists x$, and Mx. In unison, our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1e8b17f675ff16616ed14b24283a6eee https://doi.org/10.1017/jsl.2013.30 Zobrazit plný text záznamu