We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

In a seminal paper from 1985, Sistla and Clarke showed
that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete
or PSPACE-complete, depending on the set of temporal operators used.
If, in contrast, the set of propositional operators is restricted, the complexity may decrease.
... more >>>

The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets:

1. E = UE if, and only ... more >>>