Reference for problems without efficient algorithm (in polynomial time)

Question

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?

Answer 1

Some examples:

• You could start with any well-known NP-hard problem (that includes NP-complete problems too, as well as PSPACE-complete, etc.).
• Many equivalence-related algorithms for automatons and logic formulas, for example
  • equivalence for deterministic push-down automatons;
  • see also second-order logic;
  • logics like ATL, LTL or CTL, etc. have variants which are hard, try this search.
• Some type inference algorithms, e.g. for rank-2 types (ranks 3 or higher are undecidable) or for kind-2 types (kinds 3 or higher are also undecidable).
• Many games, like go, lead to hard problems, try this search.

I hope this helps $\ddot\smile$

Answer 2

Oh, there are plenty of famous and important NP-hard problems. Here's the first list from a Google search. IMO the most important ones in practical applications are Bin Packing, Travelling Salesman, and Integer Programming problems, although many other ones are important as well.

Answer 3

Sorting. Any sorting on a list of $n$ elements is a polynomial problem.