0

#P is the complexity class concerned with counting the number of accepting paths of a non-deterministic Turing machine in polynomial time.

Is there a deterministic equivalent to this complexity class?

Ben Crossley
  • 2,544
  • 1
    So, for you a "halting state" of a non-deterministic Turing machine is an accepting path for this machine, right? – Olivier Roche Nov 28 '19 at 07:57
  • 1
    No, I think you should check a rigorous definition of #P. I'll give one in an answer below for the record since I couldn't find a link in English. – Olivier Roche Nov 28 '19 at 08:23
  • A function $f : \mathbb{N} \mapsto \mathbb{N}$ is #P if there is a polynomial time non-deterministic machine $M$ such that for all $x$, $f(x)$ is the number of accepting paths for the machine $M$ with input $x$. – Olivier Roche Nov 28 '19 at 08:44

0 Answers0