[CST-2] advanced algorithms - probabilistic complexity classes

[Matej Pfajfar]

The class R is defined as the set of those problems solvable with a NDTM
where all computations are finite and same length and the choices are
binary and where either there is no accepting computations or >= 1/2 of
the computations are accepting.

ANd this give you either a definite yes or a no with chance of error <=
1/2. IS this right?



--
Matej Pfajfar
St John's College, University of Cambridge, UK

GPG Public Keys @ http://matejpfajfar.co.uk/keys
WARNING: THIS E-MAIL ACCOUNT WILL BE DELETED ON
         15/07/2002. PLEASE USE mp@cantab.net.