1
$\begingroup$

Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time.
Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of clauses in $\varphi$ that can be satisfied.

Thank you!

P.S.
You can assume that you have search and decision algorithms for 3SAT at polynomial time - so you can use them...

$\endgroup$
  • 2
    $\begingroup$ We can't help you, because you've not explained what you need help with. All we can do is solve your homework exercise for you, and that would be cheating. If you explain what it is that you don't understand that's stopping you from solving the problem yourself, then we can help you. By the way, the problem you're trying to solve is usually called MAX-SAT, which may help with your research. $\endgroup$ – David Richerby May 8 '18 at 13:06
  • $\begingroup$ @DavidRicherby, Yes, I understand - so any hint will help! because I don't have any Idea. The only thing I know is that I need to dived it for two parts... $\endgroup$ – Yoar May 8 '18 at 13:34
  • $\begingroup$ Knowing that P = NP wouldn't help you one bit finding an efficient or optimal algorithm for one of the problems that we call NP complete today. (Ok, they stay NP complete, but the problem of adding two integers would be NP complete if P = NP). $\endgroup$ – gnasher729 May 8 '18 at 13:57
  • 1
    $\begingroup$ You don’t. You know that a polynomial time solution exists. You don’t know if it is a solution that humans or gods are capable of finding. $\endgroup$ – gnasher729 May 9 '18 at 16:37
  • 1
    $\begingroup$ Tell me the (99!)!th decimal digit of pi. It exists. $\endgroup$ – gnasher729 May 9 '18 at 16:38
1
$\begingroup$

The following language is in NP (why?): $$ \{ (\phi,k) : \text{$\phi$ is a CNF and there is an assignment satisfying at least $k$ clauses of $\phi$} \}. $$ I’ll let you finish the proof.

$\endgroup$
  • $\begingroup$ Thank you Yuval!! I know that the language is NP because the Verifier ... But how does it help me? $\endgroup$ – Yoar May 8 '18 at 20:24
  • 1
    $\begingroup$ This hint will have to do. $\endgroup$ – Yuval Filmus May 8 '18 at 20:27
  • $\begingroup$ Oh, I think I got it! - I run a loop form 1 to n - and when I fount that $\phi$ is not satisfied I stop... After this I look for the $k$ clauses, this is the idea? $\endgroup$ – Yoar May 8 '18 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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