A note on bounded arithmetic
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in -CNF on variables and clauses is .
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is .