Page "Automated theorem proving" Paragraph 8

Depending on the underlying logic, the problem of deciding the validity of a formula varies from trivial to impossible.

For the frequent case of propositional logic, the problem is decidable but Co-NP-complete, and hence only exponential-time algorithms are believed to exist for general proof tasks.

For a first order predicate calculus, with no (" proper ") axioms, Gödel's completeness theorem states that the theorems ( provable statements ) are exactly the logically valid well-formed formulas, so identifying valid formulas is recursively enumerable: given unbounded resources, any valid formula can eventually be proven.