4 ms·

You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'ans

You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'answers' a special case of this: If by vanishingly small you mean polynomial size, and you also assume Alice has an algorithm that can distinguish the two subclasses of graph isomorphism, then P=NP if Alice has these facts. By 'distinguish', I specifically mean that Alice has a polynomial time algorithm that will tell you, for an input of graph isomorphism, is it part of a subclass of graph isomorphism which is NP-complete, and which has polynomial size.

bmc7505 5y ago
This is useful information, thank you for sharing this theorem! I am still skeptical about the soundness of the verifier's challenge generating mechanism. Assuming P!=NP and the challenge is drawn uniformly from the full space, I am still not convinced that the prover does not have access to a backdoor which makes the challenge "easier" on average than the challenger realizes. Even if challenge instances are superpolynomial in the worst case, empirically, we know from SAT solving competitions that a very small fraction of randomly sampled k-SAT instances are truly hard and most are in P. It is nontrivial to design a challenge whose average case is superpolynomial, and there are many open questions in the field of average-case complexity [1]. I would be very skeptical that the challenge generator is not somehow poisoned. Even if the prover did not collude with the protocol designer to poison it directly, if she can infer any information about the internal state of the verifier from the instances he proposes, she may be able to solve future challenges much more easily than would be possible by random chance. [1]: https://arxiv.org/pdf/cs/0606037.pdf https://arxiv.org/pdf/cs/0606037.pdf

bmc7505 5y ago

This is useful information, thank you for sharing this theorem! I am still skeptical about the soundness of the verifier's challenge generating mechanism. Assuming P!=NP and the challenge is drawn uniformly from the full space, I am still not convinced that the prover does not have access to a backdoor which makes the challenge "easier" on average than the challenger realizes. Even if challenge instances are superpolynomial in the worst case, empirically, we know from SAT solving competitions that a very small fraction of randomly sampled k-SAT instances are truly hard and most are in P. It is nontrivial to design a challenge whose average case is superpolynomial, and there are many open questions in the field of average-case complexity [1]. I would be very skeptical that the challenge generator is not somehow poisoned. Even if the prover did not collude with the protocol designer to poison it directly, if she can infer any information about the internal state of the verifier from the instances he proposes, she may be able to solve future challenges much more easily than would be possible by random chance. [1]: https://arxiv.org/pdf/cs/0606037.pdf https://arxiv.org/pdf/cs/0606037.pdf