# Tag Info

## Hot answers tagged cc.complexity-theory

### 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/...
• 26.6k

### Classes between PH and PSPACE

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

### Complexity of "discrete-time" SAT

Your problem is PSPACE-complete: Membership in PSPACE via a nondeterministic PSPACE algorithm: ...
• 7,757
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 ...
• 35.9k

### 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

### 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).
• 14.9k
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