3 Dec
2016
3 Dec
'16
7:36 p.m.
At 06:28 AM 12/3/2016, Henry Baker wrote:
1. Is there an easy way to enumerate/generate (all and only) *tautologies* in more-or-less increasing complexity fashion? By complexity, I mean more-or-less increasing fashion wrt the number of distinct variables and the size of the expression.
I thought about this during a long drive today and realized that there *can't* be an "efficient" (P) algorithm to enumerate all and only tautologies, else that algorithm would itself be useful to solve tautologies, and hence P=NP. So Rich's idea of generating formulae and then doing tautology-testing may well be nearly optimal.