1
$\begingroup$

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).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Steven
    Apr 22 at 19:31
  • $\begingroup$ You got a point. I completely missed that. $\endgroup$
    – Benedict Bien
    Apr 22 at 20:59

1 Answer 1

Reset to default
2
$\begingroup$

The answer is probably no. Because if this were the case we would have a polynomial time randomized solution to 3-sat (as mentioned by steven in the comments), and we haven't found that yet.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.