Henkin quantifiers and complete problems (Q1088983): Difference between revisions

The authors analyze computational aspects of partially ordered quantification (introduced by Henkin) in first-order logic. They show that formulas obtained from first-order ones by applications of Henkin qantifiers are able to express \({\mathcal N}{\mathcal P}\)-complete properties of finite structures. However, Henkin quantifiers of one extremely restricted sort (narrow Henkin quantifiers) express exactly the co-\({\mathcal N}{\mathcal P}\) properties of finite structures.