[FOM] Complexity of intuitionistic propositional calculus

Harvey Friedman friedman at math.ohio-state.edu
Sat Dec 4 14:33:57 EST 2004

Previous message: [FOM] More on first-order logic with operation constants
Next message: [FOM] 237:More Neatening Pi01 Affine Independence
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

The set of provable formulas of intuitionistic propositional calculus is
PSPACE complete:

R. Statman. Intuitionistic propositional logic is polynomial-space complete.
Theoretical Computer Science, 9:67-72, 1979.

Previous message: [FOM] More on first-order logic with operation constants
Next message: [FOM] 237:More Neatening Pi01 Affine Independence
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the FOM mailing list