|
|
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.
In response to your last point about programming computers, mathematicians
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
news://66cc6eb0.0202060813.67521ec5@posting.google.com...
> 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
|
|
