I guess it is well known that the transition from 2-SAT to 3-SAT is the gap between P and NP.
The transition from 3-SAT to 4-SAT must be polynomial, because 4-SAT is obviously within SAT and thus is NP-complete. You only need poly time to translate from within NP-complete. So the answer to (3) is yes. The gap lies between 2-SAT and 3-SAT. My impression is that 2-SAT can be easily solved with convex optimization but not for 3-SAT, where *convexity* is lost. Think, intuitively: a quadratic equation defines a parabola, that has only at most 1 extremum. Whereas, a cubic equation can be like a sideways "S" shape, that has 2 points where the derivative is 0, but they are not global extrema. Thus, the area under the cubic curve is not *convex*, and the usual (fast) method of convex optimization cannot apply. The loss of convexity when going from degree 2 to 3 is precisely where P becomes NP. (But this is just my crude impression, I may have gotten some details wrong, which I am currently studying...) ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
