# Assuming that P=NP - Finding an optimal algorithm for 3SAT

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

• 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. – David Richerby May 8 '18 at 13:06
• @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... – Yoar May 8 '18 at 13:34
• 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). – gnasher729 May 8 '18 at 13:57
• 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. – gnasher729 May 9 '18 at 16:37
• Tell me the (99!)!th decimal digit of pi. It exists. – gnasher729 May 9 '18 at 16:38

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.
• 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? – Yoar May 8 '18 at 20:32