# Questions tagged [probabilistic-turing-machines]

The tag has no usage guidance.

12 questions
Filter by
Sorted by
Tagged with
363 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 ...
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 ...
• 243
751 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 ...
52 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 ...
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
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 ...
1 vote
82 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 ...
• 137
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
27 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 ...
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. ...