3

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness. If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is ...


Only top voted, non community-wiki answers of a minimum length are eligible