Randomness-Optimal Characterization of Two NP Proof Systems