Good question! We also think that NP ≠ co-NP. The difference between 99% (our conjecture) and 100% (NP = co-NP) is quite important, essentially because 99% of random objects “look random”, but not 100%. For example, consider a uniformly random string x∈{0,1}n for some large n. We can quite confidently say things like: the number of 0s in x is between 0.499n and 0.501n; there is no streak of ⌊√n⌋ alternating 0s and 1s; etc. But these only hold with 99% confidence (more precisely, with probability tending to 1), not 100%.
Going back to the conjecture statement, the job of the verification algorithm V is much harder for 100% than 99%. For 100%, V has to definitively tell (with the help of a certificate) whether a circuit has property P. Whereas for 99%, it simply has to spot (again with the help of a “certificate” of sorts) any structure at all that reveals the circuit to be non-random in a way that could cause it to have property P. For example, V could start by checking the proportions of different types of gates, and if these differed too much from a random circuit, immediately reject the circuit out-of-hand for being “possibly structured”. Footnote 6 has another example of structure that could cause a circuit to have property P, which seems much harder for a 100%-V to deal with.
Your comment seems to imply that the conjecture’s “99%” is about circuits C for which P(C) is false. Otherwise, it would be impossible for a V to miss 100% of random reversible circuits without missing the circuits C for which P(C) is true. In the conjecture, should “random reversible circuits C” be read as “random reversible circuits C for which P(C) is false”? It does not change much indeed, but I might have to correct my presentation of the conjecture here.
The statements are equivalent if only a tiny fraction (tending to 0) of random reversible circuits satisfy P(C). We think this is very likely to be true, since it is a very weak consequence of the conjecture that random (depth-~O(n)) reversible circuits are pseudorandom permutations. If it turned out to not be true, it would no longer make sense to think of P(C) as an “outrageous coincidence” and so I think we would have to abandon the conjecture. So in short we are happy to consider either version (though I agree that “for which P(C) is false” is a bit more natural).
Good question! We also think that NP ≠ co-NP. The difference between 99% (our conjecture) and 100% (NP = co-NP) is quite important, essentially because 99% of random objects “look random”, but not 100%. For example, consider a uniformly random string x∈{0,1}n for some large n. We can quite confidently say things like: the number of 0s in x is between 0.499n and 0.501n; there is no streak of ⌊√n⌋ alternating 0s and 1s; etc. But these only hold with 99% confidence (more precisely, with probability tending to 1), not 100%.
Going back to the conjecture statement, the job of the verification algorithm V is much harder for 100% than 99%. For 100%, V has to definitively tell (with the help of a certificate) whether a circuit has property P. Whereas for 99%, it simply has to spot (again with the help of a “certificate” of sorts) any structure at all that reveals the circuit to be non-random in a way that could cause it to have property P. For example, V could start by checking the proportions of different types of gates, and if these differed too much from a random circuit, immediately reject the circuit out-of-hand for being “possibly structured”. Footnote 6 has another example of structure that could cause a circuit to have property P, which seems much harder for a 100%-V to deal with.
Your comment seems to imply that the conjecture’s “99%” is about circuits C for which P(C) is false. Otherwise, it would be impossible for a V to miss 100% of random reversible circuits without missing the circuits C for which P(C) is true. In the conjecture, should “random reversible circuits C” be read as “random reversible circuits C for which P(C) is false”? It does not change much indeed, but I might have to correct my presentation of the conjecture here.
The statements are equivalent if only a tiny fraction (tending to 0) of random reversible circuits satisfy P(C). We think this is very likely to be true, since it is a very weak consequence of the conjecture that random (depth-~O(n)) reversible circuits are pseudorandom permutations. If it turned out to not be true, it would no longer make sense to think of P(C) as an “outrageous coincidence” and so I think we would have to abandon the conjecture. So in short we are happy to consider either version (though I agree that “for which P(C) is false” is a bit more natural).