What problems are known to be require superpolynomial time or greater to solve?

Question

I'm having a hard time finding problems that known to require greater than polynomial time to solve (superpolynomial), particularly in graph theory.

So, what problems (or better yet, class of problems) have been proven to require superpolynomial time or more to reach a definite solution (especially graph theory)?

To clarify, I'm aiming for mathematically important problems, like the traveling salesman problem, graph isomorphism, counting problems, decision and satisfyability problems. There are many, many examples in P and NP, but exptime seems harder to turn up (it's possible I'm just bad at googling :-)).

Answer 1

Wiki gives an interesting example here

Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger.

And for EXPTIME, here:

In computability theory, one of the basic undecidable problems is the halting problem: deciding whether a deterministic Turing machine (DTM) halts. One of the most fundamental EXPTIME-complete problems is a simpler version of this, which asks if a DTM halts in at most k steps. It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more

For Graph Theory, this article rather recently proved EXPTIME-completeness:

We investigate the computational complexity of deciding whether k cops can capture a robber on a graph G. Goldstein and Reingold (1995) [8] conjectured that the problem is EXPTIME-complete when both G and k are part of the input; we prove this conjecture.

I'm not sure of your mathematical ability so I'll just leave the wiki article as to what cops and robbers are; sorry if this is patronising (this is new to me).