[CST-2] advanced algorithms - probabilistic complexity classes
Matej Pfajfar
mp292@cam.ac.uk
Fri, 31 May 2002 17:08:40 +0100 (BST)
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.