Questions tagged [probabilistic-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
1 answer

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 ...
M A's user avatar
  • 215
0 votes
1 answer

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 ...
John Mayer's user avatar
6 votes
1 answer

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\}$ ...
J.Ask's user avatar
  • 101
2 votes
3 answers

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 ...
botsina's user avatar
  • 101
11 votes
0 answers

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 ...
user3483902's user avatar
  • 1,181
5 votes
1 answer

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 ...
Areaperson's user avatar
  • 1,439
13 votes
2 answers

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 ...
Fabio Cozman's user avatar
10 votes
1 answer

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 ...
Daniil Musatov's user avatar
4 votes
1 answer

#P- vs PP-Completeness

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 ...
Oliver Witt's user avatar
5 votes
0 answers

Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

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 ...
Michael Wehar's user avatar