P=NP?

[Мастер]

I learned about this problem at the uni in the 1980s. It remains unsolved today.

http://en.wikipedia.org/wiki/P_versus_NP_problem

The characterisation of the question is a little different than what I am used to.

So, does P=NP? Or not? Which is it?

[Lance]

No, it does not.

[tubeswell]

Would it not depend on what algorithm, processor etc was used in either instance in order to provide the answer?

[MM_Dandy]

I say 'no' as well.

[TechnicRogue]

I'm no computer scientist, but doesn't verifying a problem consist of solving it?

[Мастер]

I'm no computer scientist, but doesn't verifying a problem consist of solving it?

As I understand it, when they talk about verification in the article, they mean that the solution is given to you, and you have to confirm that it is the solution.

For example, what are the solutions to this equation?

(x^3)-7*(x^2)+2*x+40=0

Even if someone doesn't know how to solve it, they could verify that x=5 is a solution by plugging it into the left-hand side. (The other solutions are x=4 and x=-2.)

So the second sentence in the article asks, loosely speaking, whether there exist problems for which verification is easy, but solution is hard. If so, then P does not equal NP.

[Lance]

If so, then P does not equal NP.

Which is what I said several posts back.

[Мастер]

If so, then P does not equal NP.

Which is what I said several posts back.

Do you have a proof?

[Enzo]

WOuld we then say that P=.9999...NP?

[tubeswell]

WOuld we then say that P=.9999...NP?

if NP = near P

[Мастер]

WOuld we then say that P=.9999...NP?

I'd have to know what operation is meant by a number juxtaposed with a set to answer that one.

But, since you brought up 0.999..., do you know tommac at BAUT? He has his own forum, http://www.spacetimeandtheuniverse.com. It's pretty much dead now, having been brought down by a) making mugaliens a moderator, and b) letting a well-known maths crank (who is convinced he is the greatest genius to walk the earth in the last 2,000 years - seriously, he actually says things like that) run roughshod over the place. If many find the BAUT model a bit stifling, tommac's forum is a warning about what can go wrong at the other end of the spectrum.

[tubeswell]

Quite happily I know nothing much about either of those forums.

[Lance]

If so, then P does not equal NP.

Which is what I said several posts back.

Do you have a proof?

Yes.

The phrase "it's easy once you know the answer" would not exist if P=NP.

Can I have my $1,000,000 now? Please?

[Мастер]

Yes.

The phrase "it's easy once you know the answer" would not exist if P=NP.

Can I have my $1,000,000 now? Please?

You can submit that one, but my forecast is that it's not going to do real well . . .

[Lance]

Yes.

The phrase "it's easy once you know the answer" would not exist if P=NP.

Can I have my $1,000,000 now? Please?

You can submit that one, but my forecast is that it's not going to do real well . . .

But even just the idea that understanding an answer once determined is far easier than determining an unknown answer is a universal truth. Why is it even a question?

[Мастер]

But even just the idea that understanding an answer once determined is far easier than determining an unknown answer is a universal truth.

The definition of "easier" which is appropriate in the article is "takes an amount of time which is a polynomial function of the size of the problem", vs. "takes an amount of time which grows faster than any polynomial as the size of the problem increases".

Why is it even a question?

It's a question because, despite many decades of attempts by many people, no one has been able to prove it one way or the other.

Unless you are asking specifically why I posted the question here. I have my own ulterior motives for that.