3 ms·
> If you do specify a number of steps in advance, I don't think the problem is solvable faster than brute force in general, but all individual instances can be
by eru 3y ago
> If you do specify a number of steps in advance, I don't think the problem is solvable faster than brute force in general, but all individual instances can be decided at least by brute force.
For systems where you can check a given proof in polynomial time, this problem becomes 'merely' NP-complete. (Technically, the maximum size of the proof you are willing to accept needs to be a polynomial in the length of the statement you are trying to prove.)
- schoen 3y agoHmmm, isn't the number of proofs to check normally exponential in the length of the proof? E.g. if there are n proofs with length k (characters, applications of rules of inference, intermediate steps), shouldn't there be n² proofs with length 2k? (In some systems you can prune some, but the extent to which you can do that would depend on the representation of the proof and the allowable inferences.)
- eru 3y agoDetails depend on the proof system. But yes, in general you expect that the number of possible proofs goes up exponentially with their length. But any single given proof can be checked in polynomial time. That's almost the definition of NP: NP stands for 'nondeterministic polynomial time'. Which means if you can nondeterministically 'guess' a solution (or someone hands it to you etc), you can verify it in polynomial time.
- schoen 3y agoOh right, that makes perfect sense. Thanks.