1

Given a SAT instance. If one knows that there are exponentially many solutions to that SAT instance, then can one find even one solution in polynomial time?

Turbo
  • 6,221
  • Could you elaborate on what you mean by "exponentially many solutions"? – MJD Feb 01 '13 at 22:48
  • possible assignments that satisfy the SAT instance – Turbo Feb 01 '13 at 22:53
  • The problem is that "exponentially" is poorly defined, not the number of solutions, as is the question itself. Finding a solution to a sat problem is a constant time problem or an exponential problem depending on how you define it... it's constant time with respect to the individual SAT instance (though possibly a large constant) and exponential with respect to the size of the sentence. Questions loosely about intractability and computational complexity are related but not automatically identical. – dezakin May 01 '14 at 23:59

1 Answers1

0

No, unless P = NP.

Let F an arbitrary SAT instance, we are searching for one of its model. Let f be the number of variables in F. Follow this method:

  1. Generate a formula E with an algorithm whose inputs are an integer n (minimum number of variables) and an integer m; and output is a formula whose size is at least kn + m where k is a constant (set m to f).

  2. Create formula G by joining E and F (we assume that variable set of E and variable set of F are disjoint).

If your conjecture were true, then we could find a model for G in polynomial time and this model whould contain a model E too. So we could generate a model for an arbitrary formula in polynomial time.

Dávid Horváth
  • 93