5 ms·
Care to explain? E.g. https://mathoverflow.net/questions/226966/algorithmic-complexity-of-formal-proof-verification https://mathoverflow.net/questions/226966/a
by boyka 2y ago
Care to explain?
E.g. https://mathoverflow.net/questions/226966/algorithmic-complexity-of-formal-proof-verification https://mathoverflow.net/questions/226966/algorithmic-comple...
- markisus 2y agoA proof is basically a directed graph where nodes are propositions, and edges are deductive rules. One only needs to check that the starting nodes are axioms and that each edge is one of a finite set of deduction rules in the system. So the time to check a proof is linear in the number of edges.
- deleted 2y ago[deleted]