Computational complexity of the semantics of some natural language constructions Original Research Article

We consider an example of a sentence which according to Hintikkaʹs claim essentially requires for its logical form a Henkin quantifier. We show that if Hintikka is right then recognizing the truth value of the sentence in finite models is an NP-complete problem. We discuss also possible conclusions from this observation.