# Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions

Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that are always satisfiable)

If I don't know whether f is satisfiable or not:

Can I find a function f' (in polynomial time), such that if f = 0 for all outputs, then f'= 0 for all outputs as well. But if f is satisfiable, then the ratio of 1s to 0s is increased (unless f is always satisfiable). In other words increase this ratio (total amount of 1s)/(total search space). Also, the increase in ratio should be in such a way that it can reach a ratio of 1/2 after a polynomial amount of iterations.

The reason I'm asking, is because if I can, then there is a significant speedup to solving 3sat on quantum computers (using deutsch-yoza).

• If that were true, wouldn't this immediately imply the existence of a polynomial-time randomized algorithm for 3-SAT? You could simply try two random variable assignments to get a probability of error bounded by $\frac{1}{4}$. Apr 22 at 19:31
• You got a point. I completely missed that. Apr 22 at 20:59