  DPLL and resolution are two popular methods for solving the problem of
propositional satisfiability. Rather than algorithms, they are families of
algorithms, as their behavior depend on some choices they face during
execution: DPLL depends on the choice of the literal to branch on; resolution
depends on the choice of the pair of clauses to resolve at each step. The
complexity of making the optimal choice is analyzed in this paper. Extending
previous results, we prove that choosing the optimal literal to branch on in
DPLL is Delta[log]^2-hard, and becomes NP^PP-hard if branching is only allowed
on a subset of variables. Optimal choice in regular resolution is both NP-hard
and CoNP-hard. The problem of determining the size of the optimal proofs is
also analyzed: it is CoNP-hard for DPLL, and Delta[log]^2-hard if a conjecture
we make is true. This problem is CoNP-hard for regular resolution.
