Oracle that can only definitively say if an instance is unsatisfiable
Edit: I wrongly read the question, therefore the following answer is incorrect. It would be correct if the oracle worked as followed: &quot;if the instance is unsatisfiable, then the oracle always says it is unsatisfiable otherwise, there is a 57% chance the answer is that the instance is satisfiable, and a 43% chance that it is not&quot;.
The key here is to repeat the process of asking your oracle to improve the probability of getting the right answer. You know that the way it is constructed, if the oracle states that a formula is satisfiable, then IT IS satisfiable (since it never makes mistakes on non-satisfiable formulas).
For example, with your percentages, if you ask 6 times your oracle if a formula $\varphi$ is satisfiable, it will always give the right answer if $\varphi$ is not satisfiable, and there will be over 99% chance to say that $\varphi$ is satisfiable if $\varphi$ is satisfiable, because it has $0.43^6 &lt; 1\%$ chances to say that $\varphi$ is not satisfiable even if it is.
You will never be able to guarantee 100% in both cases, but you can be as close as you want by repeating the question to the oracle.