The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete

摘要

We investigate the complexity of the model checking problem for propositional intuitionistic logic. We show that the model checking problem for intuitionistic logic with one variable is complete for logspace-uniform AC^1, and for intuitionistic logic with