Questions tagged [probabilistic-turing-machines]

Filter by
Sorted by
Tagged with
1
vote
1answer
30 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
0answers
55 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
votes
1answer
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. ...
4
votes
1answer
268 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
0answers
40 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 ...
2
votes
1answer
391 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 ...