2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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