Like Tree9Likes

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. #1
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,535

    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,238
    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. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Mario F. View Post
    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.

    Quote Originally Posted by Mario F. View Post
    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?

    Quote Originally Posted by MutantJohn View Post
    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?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    Quote 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.
    Sebastiani likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    Quote Originally Posted by MutantJohn View Post
    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.
    Sebastiani and Epy like this.

  6. #6
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,509
    Can someone explain this to me?
    Quote 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.
    Mario F. likes this.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,535
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,535
    Quote Originally Posted by manasij7479 View Post
    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.
    Last edited by Mario F.; 11-15-2013 at 03:54 AM.
    Hodor likes this.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #9
    Registered User Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    650
    Quote Originally Posted by Mario F. View Post
    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. #10
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Quote Originally Posted by Hodor View Post
    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
    Read about Signed number representations - Wikipedia, the free encyclopedia

    And see what adding two such numbers will do.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  11. #11
    Registered User Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    650
    Quote Originally Posted by vart View Post
    Read about Signed number representations - Wikipedia, the free encyclopedia

    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. #12
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    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. #13
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,535
    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.
    Hodor likes this.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  14. #14
    Registered User Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    650
    Quote Originally Posted by whiteflags View Post
    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. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem passing argument into function, basic problem
    By tsdad in forum C++ Programming
    Replies: 7
    Last Post: 05-22-2013, 01:09 PM
  2. Replies: 2
    Last Post: 01-06-2013, 07:49 AM
  3. Replies: 1
    Last Post: 12-07-2012, 10:00 AM
  4. Replies: 4
    Last Post: 10-16-2008, 08:30 PM
  5. syntax linked list problem & struct problem
    By beely in forum C Programming
    Replies: 5
    Last Post: 11-11-2002, 09:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21