Complexity of checking if a proposition is an intuitionistic tautology given that it is classical.

What is known about the complexity of the problem of the promise "to determine whether a propositional formula is a tautology in intuitionist logic, given that it is a tautology in classical logic"?

Does it matter if you have access to a proof that the proposition you must validate is a classic tautology?


I think that the most efficient algorithms known to determine if a formula in the classical propositional calculation is a tautology are exponential in the size of the formula (measured in the number of connective). I do not know the best known upper limits, but here is a brief summary of the exponential time algorithms for classical and intuitionist logic.

$ A a (B lor A) $ It is a tautology. This can be done considering all the subsets of the variables, so that $ varepsilon, A, B, AB $, and see if the formula is true in each of the worlds described by the subsets. I think this establishes an upper limit of "exponential in the number of connectives".

To determine if a formula is an intuitionistic tautology, we can use the refinement logic algorithm described here.

A subset of the rules concerned $ land $ Y $ lor $ They are reproduced below. The inference line separates the previous state of the test algorithm from the new state.

Left and

$$ frac {H, A land B, H & # 39; vdash G} { triangleright ; ; ; H, A, B, H & # 39; vdash G} $$

Right and

$$ frac {H vdash A land B} { triangleright ; ; ; ; H vdash A text {y} H vdash B} $$

Left or

$$ frac {H, A lor B, H & # 39; vdash G} { triangleright ; ; ; H, A, H & # 39; vdash G text {y} H, B, H & # 39; vdash g} $$

Right or

$$ frac {H vdash A lor B} { triangleright ; ; ; ; H vdash A text {o} H vdash B} $$

This gives us an exponential time algorithm to verify if a propositional formula is a tautology in intuitionist logic, since all the rules of inference are completely directed to the syntax and some of the rules produce 2 branches that must be checked. You can think that the rules go through a formula by matching patterns in connective and recurring.

It is not obvious to me in one way or another if the fact that something is a classical tautology could be used to "eliminate" possible options by making a division … or to write more aggressive decomposition rules that involve multiple connective, but that It is the motivation behind the question.