5 votes

Classes between PH and PSPACE

Sure, versions of the polynomial hierarchy "with an unbounded number of alternations" can be found in the literature. One paper that stands out in my memory: https://lance.fortnow.com/papers/...
5 votes

Classes between PH and PSPACE

The paper Hyper-polynomial hierarchies and the polynomial jump by Fenner, Homer, Pruim, and Schaefer seems to be relevant.
4 votes
Accepted

Complexity of "discrete-time" SAT

Your problem is PSPACE-complete: Membership in PSPACE via a nondeterministic PSPACE algorithm: ...
  • 7,757
4 votes
Accepted

Is any computational complexity question solved by injury priority method except Post problem?

Priority method gets used a lot in computability theory - see some of the later chapters of Soare's book on computability. Buhrman and Torenvliet use a resource-bounded priority method to build an ...
3 votes

Examples of promise search problems that are easier than their non-promise variants?

Assuming that you can efficiently verify that any proposed solution is valid, no such problem exists. There's a trivial reduction. Suppose there was an algorithm $A$ that made use of the promise, ...
  • 10.5k
2 votes

Does the set $P$ contain only decision problems or also optimization problems?

SHORT ANSWER By definition, P and NP are (infinite) sets of decision problems (more exactly, Languages, but let's keep it simple). Studying the decision problem version of computational problem is ...
  • 2,590
1 vote
Accepted

On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)

So I put my afterthought that Emil refers to in his comment to the question in this answer in order to close this thread: Afterthoughts So I had the following idea of how to get around this problem: ...
  • 173
1 vote

Examples of promise search problems that are easier than their non-promise variants?

The search problem “given a Turing machine that terminates, compute its output” is computable, but it is not computable without the promise (it is as hard as the halting problem).
1 vote

Running time of SAT and other EXPTIME algorithms

$O(n^2 \cdot 2^s) = O(2^{\log_2(n^2)} \cdot 2^s) = O(2^{s+2log_2(n)})$, so your provided runtime is still in $EXPTIME$ as long as $n \in 2^{O(\text{poly}(s))}$. For your second question, I'm not ...
  • 792

Only top scored, non community-wiki answers of a minimum length are eligible