Skolem problem
A sequence follows a fixed linear recurrence. Is there an algorithm that always decides whether any term of the sequence equals zero?
Logic and computation
Within Logic and computation · Search all subjects
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?
Polynomial-time parity-game solving
Can the winner of every finite parity game be determined in polynomial time?
Vaught’s conjecture
Can a complete countable theory have an intermediate number of countable models?
Bag containment of conjunctive queries
Can an algorithm decide whether one database query always produces each answer no more often than another?
Positivity problem for linear recurrences
Can an algorithm decide whether an integer sequence defined by a linear recurrence never becomes negative?
Pure subtype system type safety
A type system can let programs and their types share the same language. Can the remaining proof show that the proposed pure-subtype rules stay valid as a program evaluates?
Rabin–Mostowski index problem
A finite automaton can check an infinite branching tree using a hierarchy of recurring priorities. Can an algorithm tell whether the same trees can be recognized with a smaller priority hierarchy?
Cherlin–Zilber algebraicity conjecture
Must every infinite simple group with finite logical dimension come from algebraic geometry?