I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have:
-Boolean satisfiability problem
-decision problem that asks whether a certain string s belongs to the language of a certain context-sensitive grammar G (its PSPACE-complete)
-problem whether a regular expression with exponentiation denotes all strings over its alphabet (exponential time)
Are there any other more or less famous problems that I could put in paper and write about?