# Questions tagged [probabilistic-complexity]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
315 views

### Is $PSPACE$ believed to be different than $PP$?

From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$. Is it currently believed that $PP\neq PSPACE$? What would be the ...
144 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 ...
492 views

### Where is $MA$ more relevant than $\exists BPP$?

NP can be defined as the class of languages which admit sets of certificates which are in P. The definition could be as follows. A language $L$ is in $NP$ iff there is a set $C=\left\{ x,c\right\}$ ...
147 views

### Is the transducer version of BPP closed under complement?

Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this ...
219 views

### Descriptive Complexity characterzation of BPP

We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any ...
167 views

### Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that: 1) It is hard ...
2k views

### Status of PP-completeness of MAJ3SAT

SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions? LONGER VERSION: It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence ...
426 views

### When does BPP with a biased coin equal standard BPP?

Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a ...
Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$. Are there any known connections between the problems: P vs L, UP vs UL, NP ...