I will discuss two notions of semantic complexity for fragments of natural language: (a) complexity of reasoning (b) complexity of verification. Both notions try to capture the semantic complexity in a way independent from particular implementations/theories. I will show that such abstract notions, formulated in terms of computational complexity, can not only predict aspects of cognitive processing but also linguistic distributions in large-scale corpora: the more complex constructions occur significantly less frequent. Finally, I will discuss how the semantic complexity approach may be used to delimit the boundaries of natural language and descriptive power of linguistic theories.