Proof complexity
The length and computational structure of mathematical proofs.
2 problemsLogic and computation
What can be decided, proved, or computed.
Also under Computer science
Explore Logic and computation
Collections
Browse collectionsDiophantine equations
Equations over integers and rational numbers, from elliptic curves to the limits of decision algorithms.
7 problemsProofs and certificates
Which statements have short proofs, and how do proof methods compare?
3 problemsLinear recurrences
Two different decisions about recurrence sequences: whether a zero occurs and whether all terms are nonnegative.
2 problemsA few problems to explore
13 totalSkolem problem
A sequence follows a fixed linear recurrence. Is there an algorithm that always decides whether any term of the sequence equals zero?
Hilbert’s tenth problem over the rationals
Can an algorithm always decide whether an equation with integer coefficients has a solution made of rational numbers?
Frege proof lower bounds
Can one exhibit propositional truths whose proofs must be superpolynomially long even in a flexible standard deductive system?
Fourier Entropy–Influence conjecture
Does a yes-or-no rule’s sensitivity to flipped inputs limit how widely its Fourier weight can spread?
NP versus coNP
Whenever yes answers have short efficiently checkable certificates, must no answers have them too?
Optimal propositional proof system
Can one efficiently checkable proof system match every other system’s proof lengths within a polynomial factor?