Questions tagged [probabilistic-turing-machines]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
18 views

If $NP \subseteq BPP$ then $NP = RP$. Confusion on the probability that M gives at least one wrong answer in BPP in n invocations

I was looking at the proof of if $NP \subseteq BPP$ then $NP = RP$ here. At the end of the proof the author states: "Note that if $M$ always gives correct answers on calls to $M$, then when $\phi$...
93 views

Is NP=RP(2^-n)?

I believe its true but struggle to prove. I know NP=union over positive c's of RP(2^-(n^c)) and from here to prove that RP(1/2^n) contained in NP is immediate. the other side is the problem. I've ...
20 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 ...
• 23
45 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 ...
44 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 ...
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 ...
• 213
1 vote
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
70 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 ...
63 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,439
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. ...
360 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 ...
1 vote