3 ms·
Just an addition to this comment: Point is that, according to Curry-Howard, validating a proof is equivalent to type checking the program, not actually running
by lostmsu 8y ago
Just an addition to this comment:
Point is that, according to Curry-Howard, validating a proof is equivalent to type checking the program, not actually running it to halting. Type checking (<-> validating a proof) is polynomial.