History

Please fill in your query. A complete syntax description you will find on the General Help page.
Henkin quantifiers and complete problems. (English)
Ann. Pure Appl. Logic 32, 1-16 (1986).
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 ${\cal N}{\cal P}$-complete properties of finite structures. However, Henkin quantifiers of one extremely restricted sort (narrow Henkin quantifiers) express exactly the co-${\cal N}{\cal P}$ properties of finite structures.
Reviewer: M.Tetruašvili