The study of the power of nondeterminism is central to complexity theory. However, it remains unclear how nondeterminism can be used to characterize computational optimization problems. In this dissertation, a "Guess-then- ...