Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,709 questions
1 vote
1 answer
28 views
What's an example of a problem that is in Psearch, but not in NPsearch?
I was told during a lecture that there exist computational problems that are within $\text{P}_\text{search}$ but are not in $\text{NP}_\text{search}$ this seems impossible to me because I feel like a ...
- 11
0 votes
1 answer
67 views
Definition of search-NP and search-P
Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)\ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...
- 97
5 votes
2 answers
158 views
How is $\overline{SAT}$ not obviously in NP?
First of all, I do know that it is not known whether or not $\overline{SAT}$ is in NP. But to me, it clearly looks like it is in NP. Given a Boolean formula φ with n variables, we nondeterministically ...
- 91
1 vote
1 answer
184 views
Polynomial hierarchy, many-one reduction, but with co-NP subroutine
Let's say I have three problems, problem A is $\Sigma_{2}^{P}$-complete, problem B is co-NP-complete and problem C $\in \Sigma_{2}^{P}$. In a many-one reduction from A to C (i.e. showing hardness for ...
- 13
0 votes
1 answer
56 views
Repeating a PSPACE problem exponentially many times
I am trying to understand the complexity of a problem that involves solving some $\mathsf{PSPACE}$-complete problem exponentially many times. Namely, one can imagine $\Xi=\{\phi_1,\ldots,\phi_n\}$ to ...
0 votes
0 answers
30 views
What is the difference in number of bit operations in the given expressions using big O notation?
What is the difference in the number of bit operations in the given expressions using big O notation: $\sum_{i=1}^n i^2$ $\frac{n(n+1)(2n+1)}{6}$ For 1. there are $n$ additing bit operation and $n^2$...
- 1
2 votes
1 answer
78 views
What is the complexity class $NP^{P^{NP}}$?
I'm a bit confused about the PH. I know that the class $NP^{NP}$ is the class of problems that can be verified in polynomial time if we have access to an NP oracle. I'm wondering, what is the ...
- 23
1 vote
0 answers
22 views
Asymptotically optimal strategy for Las Vegas algorithms with unknown run time distribution if you can suspend and resume later
In the paper "Optimal Speedup of Las Vegas Algorithms" Luby, M., Sinclair, A. and Zuckerman, D. give an asymptotically optimal sequences for how many time to run an Las Vegas algorithm ...
- 225