| ||||
| ||||
![]() Title:Descriptive Complexity and Inexpressibly Proofs Authors:Ronald Fagin Conference:VardiFest22 Tags:descriptive complexity, monadic NP and ximplified proofs Abstract: I will discuss ways to simplify inexpressibility proofs. In particular, I will discuss an approach by Fagin, Stockmeyer and Vardi that greatly simplifies my earlier proof (from my Ph.D. thesis) that monadic NP is not closed under complement, where monadic NP consists of properties defined by existential second-order sentences, where the existential second-order quantifiers range only over subsets of the domain. Descriptive Complexity and Inexpressibly Proofs ![]() Descriptive Complexity and Inexpressibly Proofs | ||||
Copyright © 2002 – 2025 EasyChair |