Questions tagged [probabilistic-complexity]
The probabilistic-complexity tag has no usage guidance.
10
questions
7
votes
1
answer
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 ...
- 215
0
votes
1
answer
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 ...
- 13
6
votes
1
answer
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\}$ ...
- 101
2
votes
3
answers
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 ...
- 101
11
votes
0
answers
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 ...
- 1,181
5
votes
1
answer
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 ...
- 1,439
13
votes
2
answers
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 ...
- 139
10
votes
1
answer
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 ...
- 546
4
votes
1
answer
607
views
#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 ...
- 439
5
votes
0
answers
1k
views
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 ...
- 5,127