Since there are only exponentially many circuits, having the time-complexity of the verifier grow only linearly with O(log1/ε) would mean that you could get a verifier that never makes mistakes. So (if I’m not mistaken) if you’re right about that, then the stronger version of reduction-regularity would imply that our conjecture is equivalent to NP = coNP.
I haven’t thought enough about the reduction-regularity assumption to have a take on its plausibility, but based on my intuition about our no-coincidence principle, I think it’s pretty unlikely to be equivalent to NP = coNP in a way that’s easy-ish to show.
For the time-complexity of the verifier to grow only linearly with O(log1/ε), we need also to assume the complexity of the reduction fm is O(|C|γ) for a fixed γ, regardless of m, which I admit is quite optimistic. If the time-complexity of the reduction fm is doubly exponential in m, the (upper bound of the) time-complexity of the verifier will be exponential in 1/ε, even with the stronger version of Reduction-Regularity.
Echoing Jacob, yeah, thanks for writing this!
Since there are only exponentially many circuits, having the time-complexity of the verifier grow only linearly with O(log1/ε) would mean that you could get a verifier that never makes mistakes. So (if I’m not mistaken) if you’re right about that, then the stronger version of reduction-regularity would imply that our conjecture is equivalent to NP = coNP.
I haven’t thought enough about the reduction-regularity assumption to have a take on its plausibility, but based on my intuition about our no-coincidence principle, I think it’s pretty unlikely to be equivalent to NP = coNP in a way that’s easy-ish to show.
For the time-complexity of the verifier to grow only linearly with O(log1/ε), we need also to assume the complexity of the reduction fm is O(|C|γ) for a fixed γ, regardless of m, which I admit is quite optimistic. If the time-complexity of the reduction fm is doubly exponential in m, the (upper bound of the) time-complexity of the verifier will be exponential in 1/ε, even with the stronger version of Reduction-Regularity.
Correcting myself: “doubly” just added above.