🚀 go-pugleaf

In article <722273103@pike.cs.duke.edu>, srt@duke.cs.duke.edu (Stephen R. Tate) writes:
|> In article <BxzD1t.3xA.2@cs.cmu.edu> sgall+@CS.CMU.EDU (Jiri Sgall) writes:
|> >So if you know that P=NP, you also have a polynomial algorithm for SAT that 
|> >either answers NO or gives you an satisfying assignment. You can do the same 
|> >for anything in NP.
|> 
|> No, this is not true.   There are two *different* problems here:  knowing
|> that P=NP, and having an algorithm for SAT (or any previously proved 
|> NP-complete problem, for that matter).   Don't forget the perfectly valid 
|> possibility that someone comes up with a non-constructive proof of P=NP --- 
|> this would be amazingly frustrating though.  Imagine knowing that P=NP, so you
|> know that polynomial time algorithms exist for all problems in NP,
|> but you don't know a polynomial time algorithm for any problem previously
|> shown to be NP-complete!  I think that's what the original poster probably
|> meant.

And I was exactly arguing that it cannot get so bad. The first sentence was 
supposed to read "you also know that there exists" instead of "you also have",
sorry for the confusion. The rest of the argument is valid.

My claims are:

1. I have an explicit algorithm for factoring which is polynomial if P=NP. 
(No matter if you prove that nonconstructively.)

2. I have an explicit algorithm that finds a satisfying assignement of a 
satisfiable formula (but may run forever on an unsatisfiable one) if P=NP.

These claims are proved theorems (not by me), well known in the complexity
community. They more or less say that ANY proof of P=NP has some strong
consequences about concrete algorithms.

OK?

-- Jiri Sgall