A theory of local negation: the model and some applications.
A weak form of the constructively important notion of locatedness is lifted from the context of a metric space to that of a uniform space. Certain fundamental results about almost located and totally bounded sets are then proved.
We define a recursive theory which axiomatizes a class of models of IΔ₀ + Ω ₃ + ¬ exp all of which share two features: firstly, the set of Δ₀ definable elements of the model is majorized by the set of elements definable by Δ₀ formulae of fixed complexity; secondly, Σ₁ truth about the model is recursively reducible to the set of true Σ₁ formulae of fixed complexity.
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 .