#algorithms #mathematics #philosophy
epoch: 1281613513
Recently a new attempt to proof P =/= NP gains a lot of attention. The paper is still under review and only the future will show if it is correct.This is one of the Millennium Problems and with no doubt, reviews will inspect every detail of the claimed proof over and over again. Let’s now suppose it is correct. What are the consequences?
First, some disappointment. Many important problems will never be solved efficiently and correctly by machines as known today. Despite of common misconception, even the awaited quantum computer will not change this situation. Some people believe non-deterministic machines could solve NP-complete problems, but quantum computer is not non-deterministic. Anyway, the “correctly” is an important ingredient here since we can solve a lot of NP problems approximately or - not to say - correctly enough. So, if practical problems have practical solutions with a feasible size of error our life might be still full of happiness.
The astounding fact behind all this is that even if computers cannot solve NP-complete problems efficiently, human brain does! Otherwise a lot of mathematical proofs would never have been found. If not art, the mere existence of mathematics itself shows the superpower of the human mind. Not a surprise if we accept that mathematics reveals us nothing else but the very form of what human mind can exists in and exists with or, how some people say, the structure of being, or, how others say, the form of what ever could be said (and remember, even contradiction or worse the tertium datur is a part of mathematics).
Sure, we may think of new types of machines not as limited as what we can build today. But, don’t we build such machines now and then already? Just think of your children… The essence of P =/= NP is not a disappointment but a promise. It’s the promise that we will never loose against the computers, that we will retain our domains of intuition and that the struggle for happiness will never totally disappear - easy to verify but hard to find.
Reference:
Vinay Deolalikar, P =/= NP [http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf]
Powered by Tumblr; designed by Adam Lloyd and Ingo Schramm.
