Does any efficient algorithm satisfy all three of the linearity, respect for proofs, and 0-1 boundedness? Unfortunately, the answer is no (under standard assumptions from complexity theory).
I don’t remember the exact proof but shouldn’t be efficient algorithm to be an equivalent to solution of complete problem in #P/PP classes?
I don’t remember the exact proof but shouldn’t be efficient algorithm to be an equivalent to solution of complete problem in #P/PP classes?
Indeed! This is Theorem 9.4.2.