Re: Richard J. Lipton • Logical Complexity Of Proofs

Happy Peirce’s Birthday, Everyone ❢

We’ve been discussing aspects of proof style arising in connection with the complexity of proofs.  In previous posts we took up (1) the aspect of formal duality, reflecting in passing on the prospect of higher symmetries, and (2) the spectrum ranging from information-reducing to information-preserving inference rules.  Here’s a quick recap —

• Animated Logical Graphs • (35) • (36) • (37) • (38)

A third aspect of proof style arising in this connection is the degree of insight demanded and demonstrated in the performance of a proof.  Generally speaking, the same endpoint can be reached in many different ways from given starting points, by paths ranging from those exhibiting appreciable insight to those exercising little more than persistence in sticking to a set routine.

A modicum of insight suffices to suggest the quality of “insight” resists pinning down in a succinct definition but we do tend to recognize it when we see it, so let me inch forward by highlighting its salient features in a graded series of examples.

To be continued …

Resources

• Logic Syllabus
• Logical Graphs
• Cactus Language
• Futures Of Logical Graphs
• Minimal Negation Operators
• Survey of Theme One Program
• Survey of Animated Logical Graphs
• Propositional Equation Reasoning Systems

Applications

• Applications of a Propositional Calculator • Constraint Satisfaction Problems
• Exploratory Qualitative Analysis of Sequential Observation Data

cc: Cybernetics • Ontolog • Peirce (1) (2) (3) (4) (5) (6) • Structural Modeling • Systems