Questions tagged [probabilistic-turing-machines]
The probabilistic-turing-machines tag has no usage guidance.
11
questions
0
votes
0
answers
13
views
Relativizations/Oracles for the BPP and RP complexity classes
If we consider the complexity classes RP and BPP, then to show RPBPP = BPPRP my first thought is we need to use some kind of majority voting to amplify our success probabilities. The issue is I don't ...
- 13
1
vote
1
answer
29
views
is $IP=BPP^{NP}$
In the class $IP$ we have a probabilistic polytime verifier which interacts with a nondeterministic prover polynomial times and all the messages are of length polynomial of the input. We can think of ...
- 123
0
votes
0
answers
27
views
If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$
I have the problem
If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$
To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
- 123
4
votes
0
answers
49
views
Are there any probabilistic models of computation that can strongly simulate themselves?
I was reading this question over on the quantum computation stackexchange, and the top answer stated that you can't (strongly) simulate even a probabilistic turing machine, on itself. I was just ...
- 193
1
vote
0
answers
25
views
RP with very small error = P
I was asked to show the equality $ RP(1 − 2^{-2^{n}}) = P $, which seems wrong to me (?).
The $ \supseteq $ direction is obvious, and I want to show the other direction.
My first intuition was to run ...
- 161
1
vote
1
answer
54
views
Probabilistic Turing Machine Transition Relation vs Transition Function
In wiki, PTM are defined with two transition functions and a fair coin toss which determines which one is used at each step. One can also define them, much like NDTM, using a transition relation where ...
2
votes
0
answers
61
views
A synctactic property of the complexity class P
In these lecture notes the authors mentions that P is a syntactic complexity class, as we can find a decidable set of encodings for all polynomial time Turing machines. Of course, given a ...
- 1,429
-1
votes
1
answer
26
views
Probabilistic Turing machine - Probability that the head has moved k steps to the right on the work tape
I have a PTM with following transition:
$\delta(Z_0, \square , 0) = \delta(Z_0, \square , L, R)$,
$\delta(Z_0, \square , 1) = \delta(Z_0, \square , R, R)$
Suppose that this PTM executes n steps. ...
- 99
4
votes
1
answer
337
views
why does $ A≤_p \#SAT$ if $A \in BPP$
hello and thank you for helping me understand the following:
I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$?
language A is in BPP class, if for a probabilistic turing ...
- 73
1
vote
1
answer
69
views
Spaced-bounded Probabilistic Turing Machine Always Halts
For example, in the definition of BPL, we require that the probabilistic Turing machine has to halt for every input and every randomness. What is the reason for us to define them this way? What would ...
- 127
3
votes
1
answer
587
views
Probabilistic halting problem
I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing ...
