Re: Probabilistic Turing Machines

Article View: comp.theory

Article #1926

#1926

From: Paul Crowley
Date: Sat, 09 Jan 1993 00:53

16 lines
1176 bytes

Quoting fischer-michael@cs.yale.edu (Michael Fischer) in article <1993Jan6.033354.4587@cs.yale.edu>:
>
>: 3) Assuming (2), are there any deterministic problems that have a lower
>: complexity for probabilistic Turing machines than deterministic ones?
>
>: 4) Is is known that there are no such problems?

>If I understand your questions, the answers to (2) and (4) are both
>trivially "no".

What happens if we ask only that the probability that the program fails
to complete within the lower time bound tends to zero as the size of the
problem tends to infinity?
  __                                _____
\/ o\ Paul Crowley pdc@dcs.ed.ac.uk \\ //
/\__/ "I'm the boy without a soul."  \X/

Technical Details

Message-ID: <C0KAGr.GDu@dcs.ed.ac.uk>

Path: arc1-ca.pugleaf.net!sparky!uunet!pipex!ibmpcug!exnet!dcs.ed.ac.uk!pdc

References: <1993Jan5.191925.27528@infodev.cam.ac.uk> <1993Jan6.033354.4587@cs.yale.edu>

Show Full Headers

Complete Article Headers

Newsgroups: comp.theory
Path: arc1-ca.pugleaf.net!sparky!uunet!pipex!ibmpcug!exnet!dcs.ed.ac.uk!pdc
From: pdc@dcs.ed.ac.uk (Paul Crowley)
Subject: Re: Probabilistic Turing Machines
Message-ID: <C0KAGr.GDu@dcs.ed.ac.uk>
Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
Organization: Edinburgh University
References: <1993Jan5.191925.27528@infodev.cam.ac.uk> <1993Jan6.033354.4587@cs.yale.edu>
Date: Sat, 9 Jan 1993 00:53:14 GMT
Lines: 16

Reply to Parent Message