Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Naive question about P=NP and the future of mathematicians
Replies: 30   Last Post: Feb 15, 2002 4:44 PM

 Messages: [ Previous | Next ]
 m.a.jones01 Posts: 25 Registered: 12/13/04
Re: Naive question about P=NP and the future of mathematicians
Posted: Feb 7, 2002 6:46 PM

The P=NP problem is an open problem in the field of computational
complexity.
The class P of problems are those which have solutions computable in time
that is a polynomial function of their input size. In contrast, the class
NP
are those which have no known polynomial time solutions. Within NP
there are certain problems which are said to be "complete" in the sense
that all others in NP reduce, in polynomial time, to them. If P=NP
is proven true then it would mean that NP-complete problems
(and thus all other NP problems) would be solvable in polynomial time and
have faster solutions.

I think that you have confused "computable/non-computable" with
"tractable/intractable" where in the former a problem
cannot be solved by machine and in the latter it requires
inordinate resources to solve. If P=NP is proven true then it is
true that problems that required too many resources to solve
(i.e. time) would be feasible. But however, it does not alter
computability.

You also mention automated theorem proving and (gasp!) theorem creation.
Unfortunately theoretical computer scientists have already demonstrated
that it overwhelmes machines:-

-- First order logic, for example, is undecidable which means that the
perfect
theorem prover cannot exist.
-- Godel also proved that a system for answering YES/NO to any question also
cannot exist.

would be required to create new strategies for proving that their programs
are correct. This is because virtually all properties of programs are
undecidable and cannot be checked at compile time (recall that it isn't
even possible to write a program to check if another terminates!). So
I think mathematicians will be around for a long time yet.

"P M" <solace121@yahoo.com> wrote in message
> Hello, let me start by saying I am not a mathematician, but just a
> curious person. I have read a bit about the consequences if P=NP, but
> I would like to solicit some opinions. Specifically, what I would like
> to know is, how would the work of mathematicians change if P=NP? I
> have read that P=NP would allow a computer to solve most theorems in
> pure mathematics, and even create physical theorems. Is this true? How
> would the work that some mathematicians do become affected? Would some
> of their work become obsolete and be regulated to programming a
> computer? Would most mathematicians have to become applied
> mathematicians in order to avoid obsolescence?
>
> Just wondering...
>
>
> Pete

Date Subject Author
2/6/02 P M
2/6/02 Robin Chapman
2/6/02 D. J. Bernstein
2/7/02 Robin Chapman
2/6/02 Gus Gassmann
2/6/02 Carsten Friedrich
2/7/02 Alex Binca
2/8/02 David A Molnar
2/8/02 Jon and Mary Frances Miller
2/8/02 David A Molnar
2/8/02 Alex Binca
2/7/02 Dan Kotlow
2/7/02 m.a.jones01
2/7/02 maneesh
2/8/02 Christian Bau
2/8/02 m.a.jones01
2/8/02 don@cmtzone.net
2/11/02 don@cmtzone.net
2/8/02 P M
2/8/02 Jon and Mary Frances Miller
2/8/02 David A Molnar
2/8/02 M. Kirszbraun
2/11/02 Keith Ramsay
2/11/02 David Eppstein
2/11/02 denis feldmann
2/11/02 David Eppstein
2/12/02 Mike Oliver
2/15/02 Mike Mccarty Sr
2/12/02 Alex Binca
2/12/02 David Eppstein
2/12/02 Robert Israel