99% of random[3] reversible circuits C, no such π exists.
Do you mean 99% of circuits that don’t satisfy P? Because there probably are distributions of random reversible circuits that satisfy P exactly 1% of the time, and that would make V’s job as hard as NP = coNP.
We are interested in natural distributions over reversible circuits (see e.g. footnote 3), where we believe that circuits that satisfy P are exceptionally rare (probably exponentially rare).
Do you mean 99% of circuits that don’t satisfy P? Because there probably are distributions of random reversible circuits that satisfy P exactly 1% of the time, and that would make V’s job as hard as NP = coNP.
We are interested in natural distributions over reversible circuits (see e.g. footnote 3), where we believe that circuits that satisfy P are exceptionally rare (probably exponentially rare).