That's funny -- I just spent 5 days on holiday with my old friend Neil
Immerman, who won the Godel Prize in 1995 for proving NL = co-NL,. I
don't think that he mentioned the P=NP thing once. And then I get
back online and find that sage-devel is buzzing with it!
John
On Aug 11, 3:10 am, Bill Ha
On 10 Aug, 19:12, Nils Bruin wrote:
> On Aug 10, 10:29 am, Bill Hart wrote:
>
> > Just in case this is being missed here, a problem is by definition in
> > NP only if it has been shown equivalent to one of the other NP-
> > complete problems.
>
> I assume that with "equivalent" you mean "polyno
On Aug 10, 10:29 am, Bill Hart wrote:
> Just in case this is being missed here, a problem is by definition in
> NP only if it has been shown equivalent to one of the other NP-
> complete problems.
I assume that with "equivalent" you mean "polynomially equivalent".
With your definition, P subset N
Just in case this is being missed here, a problem is by definition in
NP only if it has been shown equivalent to one of the other NP-
complete problems. Thus a deterministic polynomial time algorithm for
one of them implies one for all of them.
It's difficult to see how you could prove NP=P withou
Nathann,
Indeed n^9 would do us no good. My guess is if there ever was a
proof of P=NP it would include a way of constructing a polynomial time
algorithm for one of the many NP-complete problems. Since most of the
well known NP-complete problems have been reduced to one another, it
would simpl
> Is it actually true that if NP-complete problems could be solved in
> deterministic polynomial time that Sage would be faster?
No. Because knowing they are equal does not mean we can write faster
algorithms. I would be amazing if the proof of P=NP contained a way to
optimize at once all the algo
Is it actually true that if NP-complete problems could be solved in
deterministic polynomial time that Sage would be faster?
Bill.
On 10 Aug, 16:23, Ben Edwards wrote:
> How much faster all of sage could be!
>
> On Aug 9, 9:45 pm, Nathann Cohen wrote:
>
>
>
> > -1
>
> > I am hoping the two of t
How much faster all of sage could be!
On Aug 9, 9:45 pm, Nathann Cohen wrote:
> -1
>
> I am hoping the two of them are equal :-D
>
> Nathann
>
> On Aug 10, 10:55 am, Ben Edwards wrote:
>
>
>
> > Just because there are a number of mathematicians on the list there is
> > a potential proof of P!=NP
-1
I am hoping the two of them are equal :-D
Nathann
On Aug 10, 10:55 am, Ben Edwards wrote:
> Just because there are a number of mathematicians on the list there is
> a potential proof of P!=NP out there that is being taken fairly
> seriously.
>
> http://rjlipton.wordpress.com/2010/08/08/a-pro
