The problem with NP

This is a discussion on The problem with NP within the General Discussions forums, part of the Community Boards category; One of the things that we understand about P vs NP is that it may take us 2,000 years to ...

1. The problem with NP

One of the things that we understand about P vs NP is that it may take us 2,000 years to finally solve it. But I recently finished reading Gregory Chaitin's The Limits of Mathematics: A Course on Information Theory and the Limits of Formal Reasoning and I'm more skeptical than even that.

Irrational and Transcendental numbers sets are larger than the Reals set. We know this from Cantor. But we know next to nothing about transcendental and irrational numbers. In fact, our understanding of numbers is, to put it lightly, only in its infancy. With the work of Leibniz and Liouville we even learned of numbers and entire functions that can't be used or calculated through algebra. Chaitin goes one step further and shows us there are numbers that can't even be described or conceptualized in any way. We simply lack the formal reasoning to understand these numbers.

P vs NP is deeply integrated into our understanding of mathematics. Even if we pretend to have solved it for our present knowledge, we can't claim it. We know the problem is still unsolved. P vs NP domain is the entire domain of problem solving techniques, including those we don't know about yet or those we haven't invented yet.

We are in a constant search for new and better mathematics. But heck, in order to finally put P vs NP to rest we need to reach a plateau of mathematical understanding in which we just know there is nothing new to invent in this area. Highly unlikely.

As we have been shown since as far back as ancient times, algebra isn't enough to deal with the largest sets of numbers. Although it has been refined and expanded through the ages, it also helped expose an hidden mathematical universe we have yet to tap into. We will eventually develop new axioms. New fields of mathematics will eventually one day be able to explore everything, from irrationals and hyperreals to transcendentals, in more formal ways. But what new unreachable secrets will they reveal?

Seems likely we will always think we live in a NP universe with P always tagging behind as we progress and evolve. If and when we reach the answer one day, our intellects may be too evolved to even consider P vs NP more than an ancient curiosity of our more single minded ancestors. Also, we may forget to adjust the 1 million dollar prize to inflation.

2. Lol is math even relevant before physics?

And I think I figured it out. Superposition is the phenomena that allows entropic evolution to occur. If a superposed wave function collapses under quantum 'measurements' then it a safe assumption that in-between Planck time intervals, superposition occurs which allows for entropy, the measurement of the number of states of a system.

Take that universe, I figured you out! The heck is all this made up math stuff?

3. Originally Posted by Mario F.
P vs NP is deeply integrated into our understanding of mathematics. Even if we pretend to have solved it for our present knowledge, we can't claim it. We know the problem is still unsolved. P vs NP domain is the entire domain of problem solving techniques, including those we don't know about yet or those we haven't invented yet.

We are in a constant search for new and better mathematics. But heck, in order to finally put P vs NP to rest we need to reach a plateau of mathematical understanding in which we just know there is nothing new to invent in this area. Highly unlikely.

As we have been shown since as far back as ancient times, algebra isn't enough to deal with the largest sets of numbers. Although it has been refined and expanded through the ages, it also helped expose an hidden mathematical universe we have yet to tap into. We will eventually develop new axioms. New fields of mathematics will eventually one day be able to explore everything, from irrationals and hyperreals to transcendentals, in more formal ways. But what new unreachable secrets will they reveal?

Seems likely we will always think we live in a NP universe with P always tagging behind as we progress and evolve. If and when we reach the answer one day, our intellects may be too evolved to even consider P vs NP more than an ancient curiosity of our more single minded ancestors.
I never understood the point of the question to begin with, personally. And how could one possibly prove or disprove such a thing anyway? Just seems impossible, pointless.

Originally Posted by Mario F.
Irrational and Transcendental numbers sets are larger than the Reals set. We know this from Cantor. But we know next to nothing about transcendental and irrational numbers. In fact, our understanding of numbers is, to put it lightly, only in its infancy. With the work of Leibniz and Liouville we even learned of numbers and entire functions that can't be used or calculated through algebra. Chaitin goes one step further and shows us there are numbers that can't even be described or conceptualized in any way. We simply lack the formal reasoning to understand these numbers.
I'm pretty sure that modern mathematics has nailed those down. Rationals are simply ratios of integers (or some some recursive definition thereof, like ratios of ratios of integers or what have you) and trancendentals just an infinite series of rationals. No?

Originally Posted by MutantJohn
And I think I figured it out. Superposition is the phenomena that allows entropic evolution to occur. If a superposed wave function collapses under quantum 'measurements' then it a safe assumption that in-between Planck time intervals, superposition occurs which allows for entropy, the measurement of the number of states of a system.
Nah. Superposition, entanglement, and collapsing wave-functions are just fictions of the Copenhagen interpretation. Ever wonder why you've never seen a "true" quantum computer in action?

4. Originally Posted by Sebastiani
I never understood the point of the question to begin with, personally. And how could one possibly prove or disprove such a thing anyway? Just seems impossible, pointless.
I'm not sure about a proof that P is a proper subset of NP, but a proof that P is equal to NP is certainly not hard to imagine, if it were possible: for an NP complete problem, show an algorithm to solve it that is in P. Such a proof may prove useful since the algorithm could be adapted to solve other real world NP complete problems in P. A proof that P is a proper subset of NP is also useful -- though much less so -- in that it means we would know for sure that we should only focus on getting better at probabilistic or approximation algorithms for NP complete problems instead of looking for algorithms in P.

5. Originally Posted by MutantJohn
Lol is math even relevant before physics?
Rene Descartes would like a word with you: he believed that the real world could be totally described through mathematics.

6. Can someone explain this to me?
Originally Posted by Mario F.
Irrational and Transcendental numbers sets are larger than the Reals set.
I have studied a little bit of mathematical analysis in college, and did not see this statement anywhere.

7. To clarify, Sebastiani, keep in mind that NP complete problems are essentially all the same problem. It has been demonstrated that all NP complete problems are a variation of the initial Satisfiability problem. Find a solution to one of the known 3,000 NP problems and you found a solution to them all. This does mean that, assuming we find a solution, and assuming the above is true, P = NP in set theory. And this is why laserlight says we could adapt a solution to find the solutions to the other NP complete problems.

But here is the problem: We need new proof techniques to be able to put this problem to rest. Our current ones simply don't work. They are insufficient to handle P vs NP. The trouble is that we don't even know exactly how to prove it, much less how to devise a new proof technique that can prove or disprove it. We sit on the edge of our knowledge most likely because our computer architectures and our programming languages are insufficient. And yet they are the foremost expression of our mathematical knowledge.

P vs NP is most probably a non algebraic problem.

We need new math. And with it we need new computer architectures. But NP is loosely defined and makes it possible for new math formal systems to expand the NP set into areas beyond our knowledge at that time. Just like we are experiencing right now.

8. Originally Posted by manasij7479
I have studied a little bit of mathematical analysis in college, and did not see this statement anywhere.
I should have written that differently. The irrational and transcendental sets are larger than the algebraic numbers. Not the real set.

Start with set theory, particularly Cantor's Diagonalization. It demonstrated that there are at least two sizes for infinity. I know, it's something you don't hear everyday. In any case he proved that we can't established a one to one mapping between the set of natural numbers and the set of real numbers without missing some of the reals. Both sets are infinite, so this means there are different sizes to infinity. This is what put Set Theory on the map.

But if you think this is non intuitive, think for a moment about the naturals and integers sets. They are both infinite, right? And we can establish a one to one mapping between their elements. Which means they have the same cardinality (same size). But the former is a proper subset of the latter... that's infinity for you. Full of strangeness.

Following on Cantor's work it became fairly easy to later demonstrate that the irrational and transcendental sets are larger than the algebraic numbers. An example of the implications of not being algebraic is this: An addition operation is very well understood (*). We know that pi and e are transcendentals (not algebraic). Consequently we don't know what pi + e is. We can'y even say if it is irrational.

---
(*) In fact that may be one of the limitations of algebra. All known algebraic elementary operations are not elementary in fact, with the exception of addition. Multiplication, Division and Subtraction can all be reduced to just a sequence of additions. In algebra we really only know how to add. Perhaps -- and i'm fantasizing here -- we need more elementary operations. A new way to combine numbers into more meaningful results that can handle the numbers we don't understand.

9. Originally Posted by Mario F.
All known algebraic elementary operations are not elementary in fact, with the exception of addition. Multiplication, Division and Subtraction can all be reduced to just a sequence of additions. In algebra we really only know how to add. Perhaps -- and i'm fantasizing here -- we need more elementary operations. A new way to combine numbers into more meaningful results that can handle the numbers we don't understand.
My ignorance: how can subtraction be expressed as an addition? (Or are we talking about more than natural numbers when asking this?) I agree with the rest of your comments

10. Originally Posted by Hodor
My ignorance: how can subtraction be expressed as an addition? (Or are we talking about more than natural numbers when asking this?) I agree with the rest of your comments

And see what adding two such numbers will do.

11. Originally Posted by vart

And see what adding two such numbers will do.
I guess. Maybe I meant in a more general sense but I'm not sure. Looking at natural numbers I just can't visualise a system of mathematics that doesn't have subtraction. I mean, sure, 10 + -4 = 6 but the problem there is -4 is not a natural number. So how can you do 10 - 4 without subtraction?

12. I don't think anyone really sees the problem that you do. I can tell you that removing negatives from consideration is not going to get anywhere. Should 11 - 12 have a sensible answer? Why not?

13. And it is or this reason that subtraction isn't defined by Peano's axioms that describe the natural numbers and their arithmetic properties. It's just that subtraction (and division) aren't consistent with the set of natural numbers. In particular subtraction breaks the induction rule for natural numbers. The induction rule, in simple words, says that what is true for a natural numbers must be true for any other natural number. As whiteflags illustrates above, this isn't the case for subtraction.

As you know Hodor, mathematics is a precise language. An axiomatic definition of a set of numbers must be complete and consistent. Finding an inconsistency means either the axioms aren't good, or the set of numbers being described isn't consistent and, consequently, not good. Peano's axioms aren't inconsistent and thus help describe the set of natural numbers. But what they expose is the need for another set of numbers in which subtraction can be axiomatically defined. Welcome to the integers.

14. Originally Posted by whiteflags
I don't think anyone really sees the problem that you do. I can tell you that removing negatives from consideration is not going to get anywhere. Should 11 - 12 have a sensible answer? Why not?
I'm not trying to be difficult and I apologise if I came across that way. I really want to know if subtraction can be expressed as an addition using only natural numbers. If there is then I'll learn something valuable.

Edit: Mario F posted a great explanation while I was writing my reply. Thanks.

15. Originally Posted by Mario F.
It's just that subtraction (and division) aren't consistent with the set of natural numbers. In particular subtraction breaks the induction rule for natural numbers. The induction rule, in simple words, says that what is true for a natural numbers must be true for any other natural number.
The way I understand this is that the set of natural numbers is not closed under subtraction (and division): it is possible to subtract (or divide) one natural number from (by) another and get a result that is not a natural number.

Page 1 of 2 12 Last