# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

517 questions
Filter by
Sorted by
Tagged with
40 views

### Question regarding definition of dIP

I was self-studying Interactive Protocols from Introduction to Computational Complexity by Arora, Barak. Initially, we define when we say a language $L \subset \{ 0,1 \}^*$ is a k round deterministic ...
23 views

### Do large integers increase the expressiveness of $\mathsf{SUBSET-SUM}$?

We can consider any set $A$ of integers as a nondeterministic "subset-sum circuit" for strings represented as numbers in some range $[-2^N, 2^N]$, accepting an integer $n$ within this range ...
75 views

### Why would the existence of a sufficiently strong PRNG prove P=BPP?

The $P$ vs $BPP$ question is often explained as such: if there exists a "strong enough" PRNG, we can use it to derandomize any randomized algorithm. However, I don't get how this, let's call ...
47 views

### Is $\text{BPP}$ the largest polynomial-time "tractable" complexity class?

An algorithm is in $\text{BPP}$ if it is a) guaranteed to halt in polynomial time, and b) gives the right answer with some probability $p > 0.5$ independent of the input. $\text{BPP}$ is ...
24 views

### 4COL problem with additional constraint on the size

The task is to prove that that 4-coloring of a graph with additional constraint about number of vertices is NP-complete. Constraint: Each color class should contain at least $\frac{1}{5}$ of total ...
• 51
1 vote
58 views

• 367
37 views

### Complexity class BPP, but with only expected polynomial running time

The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output. ZPP, on the other hand, guarantees correct output, but now only ...
339 views

18 views

• 243
1 vote
196 views

### Time complexity of GPU computing

The time complexity of the matrix product is $O(n^3)$ if calculated normally for each element. If computed on GPU, is it $O(n)$? What I thought: GPU can compute each element of the matrix product in ...
• 13
1 vote
113 views

1 vote
108 views

### NP-Complete Proof - Using CFLP

I have formulated the below optimization problem. \begin{align}\nonumber \hspace{-3mm}&\text{(P) minimize}\!\sum_{i}\!\alpha_{i}w_{i}\!+\!\sum_{i}\sum_{j}\!c_{ij} p_{ij}\!\\ \text{s.t.} & \...
• 15
79 views

### Complexity of this variant of #Positive 2-SAT #P-complete?

In this variant of #Positive-2-SAT ,we divide set of all possible clauses like this : A = [ab ,ac ,ad ,.... ] B =[bc ,bd ,be ,....] C=[cd ,de ,....] D=[de ,....] .... In this variant ,we are allowed ...
• 43
1 vote
129 views

### How is P not trivially equal to ZPP?

The definition of ZPP seems to be $$ZPP = RP \cap coRP.$$ I think ZPP should then be equivalent to P, because for any language L in ZPP, there is an algorithm A and B proving that it is in RP and coRP,...
• 179
510 views

### Complexity of a variant of #Positive-2-SAT

#Positive-2SAT is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable. The ...
• 43
1 vote
95 views

### Integrality gap and complexity classes

I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems? In particular, is there a class of problems for which their integrality ...
77 views

### Lower Bound on Parity of Boolean Functions

Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
• 23
1 vote
45 views

### Class of optimization problems whose decision versions are in P

NPO is defined to be the class of optimization problems whose decision versions are in NP. I would like to get the complexity class of optimization problems whose decision versions are in P. Is such ...