Proof complexity - an introduction - Avi Wigderson

Computer Science/Discrete Mathematics Seminar II
Topic: Proof complexity - an introduction
Speaker: Avi Wigderson
Date: Tuesday, March 15
Proof systems pervade all areas of mathematics (often in disguise: e.g. Reidemeister moves is a sound and complete proof system for proving the equivalence of knots given by their diagrams). Proof complexity seeks to to understand the minimal length of proofs relative to the length of theorem proved, mainly for propositional proof systems. In this talk I plan to survey some of the main motivations and goals, results and challenges of proof complexity, as well as its connections with circuit complexity. I will then discuss in more detail the Resolution proof system (the most basic nontrivial proof system, prevalent in automated theorem provers and in hardware verification systems), and show exponential lower bounds on proof-length in this system. No special knowledge in this area will be assumed.
For more videos, visit video.ias.edu

[@matanshtepel1230]

fascinating! thanks!

[@TheKivifreak]

I'm mesmerized by his t-shirt pattern.

[@davidwilkie9551]

In the Mining industry, searching for a patch of ore, the meaning of complexity has many shades of significance, and the approach to finding a "solution" to the daily task, is shared by University trained Geologists who have up to date knowledge of mineral occurrence and research techniques, and Prospectors who are basically a kind of local Historian who knows what works by experience.
Mathematicians also come in both flavours and combinations of general vs local concentration on various techniques.
So a holistic approach is the natural requirement that the basic principles of math-reciprocals functions as they occur "in nature", which is this time duration timing modulation interference format, the original Geometer's navigational positioning Image condensation to symbology, and general Math-Phys-Chem QM congruence of cognition, coherence-cohesion objectives in pulsed resonances, ..of local density-intensity orthogonality integration.., can never provide full proofs for continuous creation connection Principle-> phenomena of probabilities, but techniques can be made more effective and efficient algorithms. Ie it's the obvious mission of the Institute.?
(And that is about all I'm qualified to commit to comment)