Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sipser's Introduction to the Theory of Computation defines $P$ complexity class as decided by a deterministic TM in polynomial time, and $NP$ as decided by nondeterministic TM in polynomial time. However:

DEFINITION 10.10:

$RP$ is the class of languages that are recognized by probabilistic polynomial time Turing machines ...

Can someone explain this asymmetry in definition?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

The asymmetry comes from probabilistic TMs as opposed to non/deterministic ones.

Sipser defines what it means for TM/NTM to recognize a language. He also defines what it means for a TM/NTM to decide a language. But for probabilistic TMs, he only defines what it means to recognize a language.

I think this is mainly a matter of style. "Deciding" a language seems to imply that we take in an input and return a definitive yes/no answer. Thus the softer term "recognize" feels more appropriate for probabilistic TMs.

I think it would be good to view the choice of terminology -- "decides" versus "recognize" as merely guiding intuition, but to be certain to look at the technical definition to really understand what's going on. The definition of "recognize" for a TM, for instance, is different than for an NTM (since they are different models of computation), and similarly for probabilistic TM. The use of the same terminology gives an idea of what's going on, but we really need the technical definitions in each case.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.