On Sat, Sep 27, 2014 at 5:31 PM, Jim Bromer via AGI <[email protected]> wrote: > > Does a polynomial time solution to 3-SAT mean that all Internet Encryption > would be easily broken? > > (1.) Could a One-Time Pad code be broken by 3-SAT P=NP.
No. Only encryption methods where the key is shorter than the message would be broken. That is everything except one time pad. > (2.) An Boolean algorithm does not necessarily flatten to a formal (or > equivalent) Boolean 3-SAT problem in polynomial time. Can an algorithm be > used to encode problems at a more complex level that might be solved in > polynomial time with the right combination of values? Yes it does. http://www-verimag.imag.fr/~duclos/teaching/inf242/SAT-3SAT-and-other-red.pdf > (3.) Can a 4-SAT problem be reduced to 3-SAT in polynomial time? Even if > there is a polynomial time solution to 3-SAT does that mean that higher order > SAT problems can be reduced to 3-SAT in polynomial time? Yes. 4-SAT to 3-SAT is just a special case of SAT to 3-SAT. > Can a SAT problem be encoded into a dynamic algorithm? Can a SAT problem be > encoded into a 4-SAT or higher problem in a way to make it extremely > difficult for a 3-SAT P=NP? All known SAT solvers have worst case exponential time complexity, just like all other NP-complete problems. > Is it possible that polynomial time solution to 3-SAT might not be obviously > feasible for 4-SAT. (This is not a case of proving that 4-SAT is np hard or > np complete.) > > I don't have the time or the ability to figure this out on my own. I am still > struggling with p=np? Maybe you could solve one of the hundreds of other NP-complete problems and then reduce SAT to it. http://en.wikipedia.org/wiki/List_of_NP-complete_problems -- -- Matt Mahoney, [email protected] ------------------------------------------- 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
