Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RES(CP):
Reports tagged with Res(CP):
TR24-072 | 11th April 2024
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Tropical proof systems

Revisions: 1

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>




ISSN 1433-8092 | Imprint