# Questions tagged [complexity-classes]

Computational complexity classes and their relations

674 questions
Filter by
Sorted by
Tagged with
94 views

### Boolean vs algebraic circuits difference

Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized. What is the central reason such a ...
• 12.9k
120 views

• 49
145 views

### Question about BPP complexity class [closed]

Good morning everyone, I just started studying the BPP complexity class and the amplification lemma. There is one exercise about BPP that I don't understand, I hope that you can help me. Let $L$ be a ...
200 views

### Is there a precise definition for big O notation with 2 or more variables [closed]

Big O notation has a very precise definition for 1 variable. You can prove O(2x^2) = O(x^2) for example. There is never ambiguity. However, for 2 or more variables ...
• 111
260 views

• 1,138
135 views

### What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

It is known $AC^0[2]$ cannot get majority function. Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$? What is ...
• 12.9k
81 views

### On Determinant modulo $2^k$ complexity

Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$? How about if $k=o(n)$ where matrix is $n\times n$?
• 12.9k
176 views

### The graph of problem reductions

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
192 views

• 17.4k