1

These would be problems in EXPTIME that are technically exponential, but are still practical. For example an algorithm that can be computed and verified in $\mathcal O(1.00000001^{n})$ with $n$ growing slowly with the input.

I know that there are hard problems in P(ex AKS principality testing) due to the time hierarchy theorem, wouldn't that also imply the existence of "easy" problems in EXPTIME?

Colonizor48
  • 419
  • 1
    Unfortunately, the coefficient of the exponent in EXPTIME isn't invariant under padding, so it doesn't really make a lot of sense to consider it as a parameter. One might talk about problems with 'naturally' low exponent, but from a formal perspective they're all the same. – Steven Stadnicki Feb 14 '22 at 22:22
  • one i can think of would actually be an EXPTIME complete problems. Determining if a dtm halts in n steps with the number written in binary has a time complexity of O(2^n),(with n being the length of the input not the number that input represents). This growns exponentially due to the number being encoded's value growing exponentially, but modern computers could probably handle very large values for n, due to how easy it is for them to emulate a turing machine. Such a problem becomes P complete if the input is encoded in Unary. – Colonizor48 Mar 09 '22 at 21:12
  • Note, by the last part, I mean that if n is the length of the binary input, the problem is EXPTIME complete. However if n is the number that the input represents, the problem is P complete. I think. – Colonizor48 Mar 09 '22 at 21:24
  • That's true for the DTM problem, but not every problem in EXPTIME becomes P when the input is written in unary — indeed, sometimes the notion of writing the input in unary doesn't even make sense. (Generalized games are one good example, where we often have a parameter $n$ for e.g. board size, but we can also have $O(n)$ or even more pieces in the position, so that even if we write $n$ itself in binary, it still takes $\Omega(n)$ bits to represent the input.) – Steven Stadnicki Mar 09 '22 at 21:40

0 Answers0