3 ms·
Proof verification is traditionally considered an automated theorem proving task. In short, being able to automatically decide the validity of a proof is almost
by YeGoblynQueenne 6y ago
Proof verification is traditionally considered an automated theorem proving task. In short, being able to automatically decide the validity of a proof is almost as useful as being able to generate a valid proof automatically.
A lot of work has gone into automated theorem proving since the early 20th century. The wikipedia page is a place to start if you are interested in more details:
https://en.wikipedia.org/wiki/Automated_theorem_proving https://en.wikipedia.org/wiki/Automated_theorem_proving
This work includes proof checkers, for which wikipedia also has a page, though it doesn't have a lot of meat on its bones and you'll have to follow the links to the systems listed yourself:
https://en.wikipedia.org/wiki/Proof_assistant https://en.wikipedia.org/wiki/Proof_assistant
I'm not an expert on proof checkers, but I hear a lot about Coq and Lean, lately, so you might want to start there.
Traditional approaches to automated theorem proving, in the sense of generating new proofs (rather than checking the validity of proofs) include, for example, Robinson's resolution algorithm that is at the heart of the logic programming language Prolog. Such traditional approaches are "better than DL" in the sense that they are provably sound (they only return correct results) and complete (they return all correct results) under certain assumptions.
Given the impossibility of empirically checking the proof of every possible theorem, e.g. in first order logic, given finite resources, such system are typically evaluated theoretically, i.e. by proofs of their properties. So for instance, there are proofs of the soundness and completeness of resolution for the purpose of deciding entailment between FOL theories given as sets of Horn clauses. I keep returning to resolution because I happen to be familiar with it, but there are other approaches, of course, though I believe many use some kind of inference rule (e.g. Modus Ponens) and a search procedure usually assisted by some heuristics to find the best next step in a proof.
- lostmsu 6y ago> In short, being able to automatically decide the validity of a proof is almost as useful as being able to generate a valid proof automatically. This statement is not known to be true, and is definitely false in practice at the moment. Validating proofs is a P complexity task, so generating proofs is by definition NP, very likely NP-complete.
- YeGoblynQueenne 6y agoI'm sorry, but what is "practice at the moment"? I'm not any expert on interactive theorem provers.
- lostmsu 6y agoIt means there's no known polynomial algorithm.
- YeGoblynQueenne 6y agoHow does this have to do with "practice at the moment"? Don't you mean "practice" as in what people actually do, in practice? I don't understand where complexity comes in to that. From what I can tell, work in generating new proofs, in the style of Logic Theorist, has dried up and interactive theorem provers are very popular, even among some mathematicians, so they clearly are useful. Anycase, far be it from me to discourage opportunistic nitpicking or pedantry, my favourite sports, but, amicably, I don't understand what you are trying to tell me. I'm curious and I'd like to know. If you have the time and patience, please clarify.
- lostmsu 6y agoGenerating proof validity is a trivial task. Generating new proofs is not.
- YeGoblynQueenne 6y agoTrivial? I don't think so. I mean, the article above describes a new state of the art established by a large language model trained with much expense and effort that achieved a measly 50% ish score. But in any case, I think you are trying to say that if something has polynomial time complexity then it's not useful, compared to a problem for which we don't know a polynomial time algorithm. I don't think that works out like that. For example, we have sorting algorithms with polynomial time complexity and I don't think anyone would say they're not useful.