2

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 :-)).

Tyler Spaeth
  • 153
  • How about 'Print a list of all the binary numbers with $n$ digits.' – Joe Jan 06 '21 at 18:17
  • Breaking an unknown password of $n$ binary digits. – Joshua Wang Jan 06 '21 at 18:20
  • @Joe I appreciate the thought, but I'm not sure that's quite was I trying to get at :-) I'll update the question. – Tyler Spaeth Jan 06 '21 at 18:45
  • 2
    Maybe you are looking for problems which are EXPTIME-complete, which are known not to be in P by the time hierarchy theorem: https://en.wikipedia.org/wiki/EXPTIME – Qiaochu Yuan Jan 06 '21 at 18:47
  • @QiaochuYuan Yup. I think you're right. I should have used that terminology. – Tyler Spaeth Jan 06 '21 at 18:49
  • @QiaochuYuan I kinda mean superpolynomial, since I'm not familiar with all the time complexity classes. – Tyler Spaeth Jan 06 '21 at 18:50
  • Traveling salesman problem (which is a graph theory problem). – David G. Stork Jan 06 '21 at 18:51
  • 3
    @David: traveling salesman is NP-complete! That means it's an open problem whether it requires more than polynomial time to solve. – Qiaochu Yuan Jan 06 '21 at 19:11
  • @Tyler: a problem which is EXPTIME-complete is guaranteed to require more than polynomial time to solve, again by the time hierarchy theorem. I don't know whether an easier argument is possible. There are silly examples like problems where the input requires exponential time to read. – Qiaochu Yuan Jan 06 '21 at 19:12
  • By the way, there is a tremendous gap between "polynomial" and "exponential," so if you mean "superpolynomial" it would be better to say that. On a log scale polynomial corresponds to $e^{O(\log n)}$ and exponential corresponds to $e^{O(n)}$ and there are many many intermediate growth rates in between, e.g. $e^{(\log n)^2}$ or $e^{\sqrt{n}}$. – Qiaochu Yuan Jan 06 '21 at 19:19
  • @QiaochuYuan I've updated the question to use superpolynomial time. – Tyler Spaeth Jan 06 '21 at 19:33

1 Answers1

0

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).

yolo
  • 509
  • Thanks for pointing these out. I'm only interested in problems that are already proved to be super polynomial, but I'm a sucker for any interesting math problem ;-) I only made it through early college math (most of basic calculus). – Tyler Spaeth Jan 06 '21 at 20:31
  • Sorry this isn't my field; isn't any EXPTIME problem superpolynomial? – yolo Jan 06 '21 at 20:47
  • I think it exptime is always superpolynomial but the reverse is not true? – Tyler Spaeth Jan 06 '21 at 21:40