Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T02:09:25.404Z Has data issue: false hasContentIssue false

DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS

Published online by Cambridge University Press:  12 December 2014

MERLIJN SEVENSTER*
Affiliation:
PHILIPS RESEARCH NORTH AMERICA 345 SCARBOROUGH ROAD, BRIARCLIFF MANOR NY 10510, USAE-mail: merlijn.sevenster@philips.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2014