mak
  • Member for 8 years, 4 months
  • Last seen more than 1 year ago
2-NEXPTIME-complete problems
4 votes

The obvious N2Exp problem is of course the word acceptance problem for 2exp time bounded nondeterministic Turing machines. Using this might be as hard/easy as 2exp tiling, because the simulation of ...

View answer
What is First-Order Rewritable (and FO-Query)?
4 votes

Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem: ...

View answer
Recursively presenting or even enumerating all P-hard languages
Accepted answer
2 votes

After some further thought, partly triggered by writing a long question, it seems clear that the set of P-hard languages is not countable, and therefore not recursively presentable either. To see why,...

View answer