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