2020/11/29 by Inga Lev, Lev, Inga
Computer Science · #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Advanced Algebra and Logic
paper · pdf · doi:10.48550/arxiv.2011.14415
In this paper, we show that the derivability problem for the primal propositional logic remains solvable in polynomial time upon adding a certain form of the principle of equivalent form substitution; and that, upon adding another form of this principle, it becomes co-NP-hard.