Space proof complexity for random $3$-CNFs via a $(2-ε)$-Hall's Theorem.

Ilario Bonacina Nicola Galesi Tony Huynh Paul Wollan

Published in: CoRR (2014)

Keyphrases

interactive theorem proving
space requirements
space time
theorem prover
search space
low dimensional
vector space
randomly generated
space complexity
von neumann