[30] A problem is in #P if there is a nondeterministic Turing machine such that for each input, the number of distinct accepting paths of the Turing machine is precisely the number of solutions for the problem for this input. #P-complete problems are defined (analogously to NP-complete problems) as follows: The problem is in #P, and every

#P problem can be reduced to it by a polynomial-time deterministic Turing machine computation. As an example, counting the number of satisfying truth assignments for SAT is #P-complete. Let C be a class of languages. Say C is P-rankable if for all L ∈ C, the ranking function rL is polynomial-time computable. Prove:

(a) P is P-rankable iff NP is P-rankable.

(b) P is P-rankable iff P = P#P.

(c) PSPACE is P-rankable iff P = PSPACE.

(d) P/poly is not P-rankable, where the class P/poly is defined in Exercise 7.2.6.

(e) Languages accepted by two-way deterministic pushdown automata are P-rankable iff P = #P.

(f) Languages accepted by one-way multihead DFAs are P-rankable iff P = #P.

(g) Languages accepted by one-way log-space-bounded nondeterministic Turing machines are P-rankable iff P = #P.

Comments. Source: Items (a)–

(d) are from [L. Hemachandra and S.
Rudich, J. Comput. System Sci., 41:2(1990), 251–271]. Items (e)–(g) are from [D.T. Huynh, Math. Systems Theory, 23(1990), 1–19]. The #P class was introduced by L. Valiant [Theoret. Comput. Sci., 8(1979), 189–201].