The validity problem of propositional logic (dual problem of the satisfiability problem, i.e., given a formula φ, is φ true for all valuations) is coNP-hard

coNP upper bound corresponds to a NP upper bound for the dual problem: guessing a graph with at most N vertices which is recognizes by A but in which φ does not hold