# Questions tagged [complexity-classes]

Computational complexity classes and their relations

596 questions
Filter by
Sorted by
Tagged with
1answer
46 views

### KRW Conjecture: separation of NC' and P

more than a real question this is a recap of something i have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...
0answers
34 views

### Weak PRG to derandomize BPP into DTIME [closed]

Assuming there is a deterministic polynomial time TM M such that on every input 1^m, outputs a((log m)^2, m, 1/10)-PRG. Please show that BPP ⊆[c>1DTIME(2^((log n)^c)))
0answers
39 views

### Error reduction in BPP for other probabilities [closed]

Can someone please explain how the error reduction is done in BPP? Moreover, if • if x ∈ L, then Pr[M(x) = 1] ≥ 4/5; • if x 6∈ L (x does not belong to L) , then Pr[M(x) = 1] ≤ 3/5; How can I prove L ...
0answers
164 views

### anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
0answers
52 views

### Additive error approximations of GapP functions

Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that \begin{equation} \left|g(x) - \tilde g(x)\right| \leq \epsilon. \end{equation} Consider a ...
0answers
89 views

### Candidate one way functions and $NC$?

All the known candidate one-way functions are in $NC^1$ (integer multiplication, Iterated modular multiplication (where we are allowed to preprocess generators (of multiplicative group modulo $q$ ...
0answers
151 views

### IP, MIP and MIP* with super-polynomial verifier

Regarding each of the above classes, what are the currently known upper bounds when the verifier is given more than polynomial power? Specifically, when do we reach ALL in each of the above classes ...
0answers
121 views

### Complexity of real coefficients Linear Programs

I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients. I know that for linear programs with ...
0answers
71 views

### Improving the approximation in Stockmeyer's counting theorem

Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that \begin{equation} \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
0answers
73 views

0answers
70 views

1answer
81 views

### Can a NEXP machine simulate invalid queries to a promise problem oracle?

Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
0answers
64 views

### Reference to “compressibility” of logarithmic space [closed]

Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
1answer
84 views

### Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties: The size of $\psi$ is ...
0answers
94 views

### Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...
1answer
138 views

### Complexity of approximating a real function using queries

Consider the following computational problem, where $I$ is the real interval $[-1,1]$: There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
1answer
113 views

### Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
1answer
141 views

### Are all RegExp solvable in O(n)?

I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 ...
1answer
124 views

### Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
0answers
128 views

### Why can MIP be restricted to just two provers?

In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are ...
2answers
268 views

### Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ . Clearly, ...
1answer
174 views

### Complexity class of efficient streaming algorithms

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words: $L \in \mathsf{StreamL}$ if there ...
0answers
122 views

### Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
1answer
287 views

### The theoretical complexity of Go - The state of the art

What are the latest advances in theoretical complexity of Go? I know some early works about the complexity of Go: "Go is polynomial-space hard" proved that Go is PSPACE-hard. "Ladders are PSPACE-...
0answers
99 views

### Is PP invariant under changing its cut-off from 1/2 to another number?

Suppose I have a fixed family of quantum circuits $\{C_i\}$ for which determining whether the maximum output acceptance probabilities are $p\geq 1/2$ or $p< 1/2$ is PP-hard. Now suppose I have the ...
2answers
115 views

0answers
18 views

### Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
2answers
175 views

### Problem in deterministic time $n^p$ and not lower

I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable). ...
1answer
170 views

### Containment problem of an acyclic NFA in an NFA

Let $A$ and $B$ be NFAs, such that $A$ is acyclic. In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it ...