As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [probabilistic-turing-machines]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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. ...
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 ...
1 vote