Notices
Page 1 of 2 12 LastLast
Results 1 to 100 of 164
Like Tree9Likes

Thread: P = NP, subset sum problem solved.

  1. #1 P = NP, subset sum problem solved. 
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    This is what i have seen "P appears to be equal to NP". To view the computer program (subset sum problem) and the publication please go to website: fofallthings. Open with internet explorer.

    Given a set of integers. For instance, {-2, -3, 15, 14, 7, -10} does some nonempty subset of them sum to 0? The computer program gives answer: "yes, because {-2, -3, -10, 15} adds up to zero"

    (BTW, edited) P appears to be equal to NP before the complexity of the problem grows.

    However, it was later proven that P ≠ NP.


    Last edited by lebrat; August 13th, 2014 at 03:54 AM.
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Congratulations, I'm sure your $1m check is now in the mail.


    Trivium and lebrat like this.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  4. #3  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Do you have an actual link to the site? I suppose they would have had to say that iff a polynomial is infinite in scope and polynomials are not infinite then you could use the infinity symbol and have an non-infinite polynomial infinite. ie x->infinity x=even. whole number. All you need to do is your actual defined job as a computer scientist and make a system that work well.
    Last edited by fiveworlds; December 5th, 2013 at 05:48 AM.
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Just in case anyone's wondering, the problem isn't solving the subset sum problem, it's solving it quickly (in a technical sense).
    Brett likes this.
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    The site: www.fofallthings.com

    The question is: Is there anyone again apart from the one at fofallthings.com ?

    That is the only correct solution so far. Modularity means you can define an interface (a computer program) and as long as you know what the interface does, you don’t need to know how it does it. In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

    I believe the computer program for subset sum problem P=NP at fofallthings.com is solving it quickly (in a technical sense).
    Last edited by lebrat; December 6th, 2013 at 04:13 AM.
    Reply With Quote  
     

  7. #6  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    Most of that website refuses to display because I do not have a PC running Windows. So much for modern standards. Welcome to the 1990s.

    The small amount that does display is, as far as I can tell, gibberish. Meaningless collections of symbols with no explanation of what they are supposed to mean. If this guy has a proof, why hasn't it been published in a proper peer-reviewed mathematical journal? Has he applied for the million dollar prize? Or is is he just using that to try and show how "clever" he is.

    I believe the computer program for subset sum problem P=NP at fofallthings.com is solving it quickly (in a technical sense).
    Believing it is of no value. It needs to be proved.
    Last edited by Strange; December 6th, 2013 at 06:58 AM.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  8. #7  
    Moderator Moderator Cogito Ergo Sum's Avatar
    Join Date
    Jun 2013
    Location
    Belgium
    Posts
    2,507
    Quote Originally Posted by MagiMaster View Post
    Just in case anyone's wondering, the problem isn't solving the subset sum problem, it's solving it quickly (in a technical sense).

    What is the P = NP subset sum problem?
    I failed to grasp the Wikipedia page about that subject.
    "The only safe rule is to dispute only with those of your acquaintance of whom you know that they possess sufficient intelligence and self-respect not to advance absurdities; to appeal to reason and not to authority, and to listen to reason and yield to it; and, finally, to be willing to accept reason even from an opponent, and to be just enough to bear being proved to be in the wrong."

    ~ Arthur Schopenhauer, The Art of Being Right: 38 Ways to Win an Argument (1831), Stratagem XXXVIII.
    Reply With Quote  
     

  9. #8  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    A P problem is one that can be solved in polynomial time (i.e. the time taken scales by the size of the problem to some power - which might be 1, or less). This means that the time (or resources) to solve a problem scale in a reasonable way, making these problems "easy".

    There are other problem where the solution scales exponentially with the size of the problem. Such problems rapidly become hard or even unsolvable for large (real world) problems.

    However, many of these hard problems are NP. This means that a solution can be checked in polynomial time.

    For example, finding the prime factors of a (large) integer is hard; there is no polynomial time algorithm. But checking whether two numbers are factors of a larger integer is easy: just multiply them. This scales by less than n^2 (for an integer of n bits).

    The challenge is to prove whether all problems in NP can be solved in polynomial time or not. The general assumption is that the answer is "no" (i.e. there is no way to factor a number as quickly as checking factors). But no one has been able to prove this.

    I have just found this article, which looks quite readable: What Does 'P vs. NP' Mean for the Rest of Us? | MIT Technology Review
    Cogito Ergo Sum likes this.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  10. #9  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    Most of that website refuses to display because I do not have a PC running Windows. So much for modern standards. Welcome to the 1990s.

    The small amount that does display is, as far as I can tell, gibberish. Meaningless collections of symbols with no explanation of what they are supposed to mean. If this guy has a proof, why hasn't it been published in a proper peer-reviewed mathematical journal? Has he applied for the million dollar prize? Or is is he just using that to try and show how "clever" he is.

    I believe the computer program for subset sum problem P=NP at fofallthings.com is solving it quickly (in a technical sense).
    Believing it is of no value. It needs to be proved.


    You have to use internet explorer to open the site and view the computer program

    The guy will published it soon it is only the source code that isn’t there unless you want the guy to release his source code.

    Believing it or not the program is working.

    Computer is garbage in, garbage out there is no short cut to it unless if computer has now turn to unrealistic being, computer does not lie. For a computer program to have done that it must have followed a certain algorithm which makes it work!

    There might be no other genuine proof other than that unless you want him to give you the source code, may be that must have been the reason why he mentioned modularity. So believing it or not the program is working.


    // Algorithm that accepts the NP-complete language SUBSET-SUM.
    //
    // this is a polynomial-time algorithm if and only if P = NP.
    //
    // "Polynomial-time" means it returns "yes" in polynomial time when
    // the answer should be "yes", and runs forever when it is "no".
    //
    // Input: S = a finite set of integers
    // Output: "yes" if any subset of S adds up to 0.
    // Runs forever with no output otherwise.

    FOR N = 1...∞
    FOR P = 1...N
    Run program number P for N steps with input S
    IF the program outputs a list of distinct integers
    AND the integers are all in S
    AND the integers sum to 0 THEN
    OUTPUT "yes" and HALT

    If, and only if, P = NP, then this is a polynomial-time algorithm accepting an NP-complete language. "Accepting" means it gives "yes" answers in polynomial time, but is allowed to run forever when the answer is "no"

    There is at least one input for which most algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all but that is not the case this time around.


    From fofallthings.com:
    Try and input the set {−2, −3, 15, 14, 7, −10} into the computer program at fofallthings.com
    The computer program will return "yes, because {−2, −3, −10, 15} adds up to zero"

    The computer program at fofallthings.com outputs a list of distinct integers and the integers are all in S and the integers sum to 0.
    Therefore, P = NP.
    Last edited by lebrat; June 19th, 2014 at 12:43 PM.
    Reply With Quote  
     

  11. #10  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    You have to use internet explorer to open the site and view the computer program via "P=NP and X ± Y = B?"
    Well, that is a stupid and unnecessary restriction. Why would anyone do that?

    The guy published it in an international journal
    Is that peer reviewed?

    Believing it or not the program is working.
    As I said, "belief" or "source code" are inadequate. A proof is required.

    // "Polynomial-time" means it returns "yes" in polynomial time when
    // the answer should be "yes", and runs forever when it is "no".
    I don't think so. That means it can take an infinite time before you get an answer. That is not a polynomial-time algorithm.

    Also, his code appears to check a solution; this is known to be possible in polynomial time. So there is nothing clever there. And what is the point of wrapping it in an infinite loop?

    The problem is to generate a solution in polynomial time. Actually, the problem is to prove (mathematically) that this can be done. He has not done this.

    Also, where is the proof that his code runs in polynomial time at all? All I see is a claim that it is so.

    Finally, are you "Martins Kolawole Alabi"?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  12. #11  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    It works on the computer and that is all.


    1. From Wikipedia: … Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} adds up to zero" can be quickly verified with three additions. However, there is no known algorithm to find such a subset in polynomial time.

    Check this: “However, there is no known algorithm to find such a subset in polynomial time.”

    Therefore, direct me to a computer program that checks a solution like the one given above?
    1. No. The computer program at fofallthings.com does not take an infinite time to get an answer.

    From Wikipedia: “No algorithm for any NP-complete problem is known to run in polynomial time. However, there are algorithms for NP-complete problems with the property that if P = NP, then the algorithm runs in polynomial time (although with enormous constants, making the algorithm impractical). The following algorithm, due to Levin (without any citation), is such an example below. It correctly accepts the NP-complete language SUBSET-SUM. It runs in polynomial time if and only if P = NP:”

    Precise, it is just an illustration.
    1. The proof is the computer program.


    1. What does "Martins Kolawole Alabi"?
    Last edited by lebrat; June 19th, 2014 at 12:24 PM.
    Reply With Quote  
     

  13. #12  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by lebrat
    // "Polynomial-time" means it returns "yes" in polynomial time when
    // the answer should be "yes", and runs forever when it is "no".


    Actually, this is wrong. A polynomial time algorithm must terminate in polynomial time on any input.

    Also, source code would be proof, if it actually worked, which is probably why it's not available. (I should add that an actual mathematical proof of how the source code works would be easier to publish.)

    BTW, the published paper mentioned seems to have almost nothing to do with P=NP or the subset sum problem. It's something to do with quantum spins. (If anyone's interested, quantum computers may be able to solve NP problems in P time, maybe, but the P=NP problem is about classical computers.)
    Last edited by MagiMaster; December 6th, 2013 at 11:40 AM.
    lebrat likes this.
    Reply With Quote  
     

  14. #13  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    Quote Originally Posted by lebrat
    // "Polynomial-time" means it returns "yes" in polynomial time when
    // the answer should be "yes", and runs forever when it is "no".


    Actually, this is wrong. A polynomial time algorithm must terminate in polynomial time on any input.

    Also, source code would be proof, if it actually worked, which is probably why it's not available. (I should add that an actual mathematical proof of how the source code works would be easier to publish.)

    BTW, the published paper mentioned seems to have almost nothing to do with P=NP or the subset sum problem. It's something to do with quantum spins. (If anyone's interested, quantum computers may be able to solve NP problems in P time, maybe, but the P=NP problem is about classical computers.)

    From the column titled: “Publication” at fofallthings.com



    The P = NP problem might be about classical computers. Also, the computer program at fofallthings.com is running on a classical computer now; it could be the best known quantum algorithm for this problem.
    Last edited by lebrat; June 19th, 2014 at 12:34 PM.
    Reply With Quote  
     

  15. #14  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    If you want any actual feedback, just publish your source code. Then we can point out more specifically where you've gone wrong (or on the off chance your program does what you say it does, we can recommend some journals to send it to).
    Reply With Quote  
     

  16. #15  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    May be we should tell him to publish his source code. I only brought the news and I wonder if there is ever any other computer program to have done what he says it does! Though, he might not need to re-publish it in a way since he had already published the algorithm that directly gave birth to the computer program in an international journal. In as much his computer program gives the exact answers that they said it would give just like the subset sum problem example at the Wikipedia. It is left for the owners of the question -Clay Mathematical Instutes (CMI) and everyone to decide if the answer they've got now is right or not.
    Last edited by lebrat; December 6th, 2013 at 04:45 PM.
    Reply With Quote  
     

  17. #16  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    1. Check the journal at the column “publication” it is very well peer reviewed.
    Doesn't look like it to me. It looks like one of those "web journals" which will publish anything for a fee.

    1. It works on the computer and that is all.
    Anyone can write a program that "works"; i means nothing. What is required is a general proof.

    Therefore, direct me to a computer program that checks a solution like the one given above?
    Checking a solution is trivial. And is known to be doable in polynomial time.

    1. No. The computer program at fofallthings.com does not take an infinite time to get an answer.
    Of course it does. It may not terminate. Which means that the maximum time is unbounded and therefore not polynomial. If you are not the author, you appear to be almost as ignorant as him.

    It runs in polynomial time if and only if P = NP:”
    Where is the proof of that?

    1. The proof is the computer program.
    A computer program is not a proof. If you are not the author, you appear to be almost as ignorant as him.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  18. #17  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    From the column titled: “Publication” at fofallthings.com

    The Proof for x ± y = b is the premise that was used to solve the subset sum problem, P = NP.

    The Proof for x ± y = b could be found in the published paper. See. No.9, page 26 of the publication “Shifting of Quantum Numbers”
    Are you sure you are not the author of this idiotic web site?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  19. #18  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Okay, those publishing in your desire web journals are the people that have the standard and they got a proof that P=NP. Before now, have you ever seen an actual proof that P=NP, solving the subset sum problem in your life time? For example, from Wikipedia:...Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {-2, -3, 15, 14, 7, -10} add up to 0? The answer "yes, because -{2, -3, -10, 15} adds up to zero" can be quickly verified with three additions. However, there is no known algorithm to find such a subset in polynomial time. Have you ever seen a proof that P=NP? So, don't talk more than what you can chew.
    Reply With Quote  
     

  20. #19  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    However, there is no known algorithm to find such a subset in polynomial time.
    Exactly. Therefore, it is not proof that P=NP.

    Have you ever seen a proof that P=NP?
    No. If the author of that website had such a proof then there would he would be able to provide an algorithm to find such a subset in polynomial time.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  21. #20  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    However, there is no known algorithm to find such a subset in polynomial time.
    Exactly. Therefore, it is not proof that P=NP.
    Have you ever seen a proof that P=NP?
    No. If the author of that website had such a proof then there would he would be able to provide an algorithm to find such a subset in polynomial time.
    And now, From fofallthings.com:If you input the set {−2, −3, 15, 14, 7, −10} into the computer program at fofallthings.com The computer program at fofallthings.com will return "yes, {−2, −3, −10, 15} adds up to zero" The computer program at fofallthings.com outputs a list of distinct integers and the integer sum to zero. So, there is now a known algorithm to find such a subset in polynomial time.Therefore, P=NP.
    Reply With Quote  
     

  22. #21  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Try inputting a couple hundred large random numbers. If you get an answer within a few minutes, then I'll be curious. Again, the challenge is to solve it quickly, and not just for 6 element sets.
    Reply With Quote  
     

  23. #22  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    Try inputting a couple hundred large random numbers. If you get an answer within a few minutes, then I'll be curious. Again, the challenge is to solve it quickly, and not just for 6 element sets.
    Thank you MagiMaster, I will contact the author if he can do that even though that would be a stress on him. If you check the last computer program which is the second program, third click on that same page column "P=NP" he has the one of 11 element sets. So, he should be able to implement that.
    Reply With Quote  
     

  24. #23  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Sorry, I'm not opening a page that requires Internet Explorer. I tried opening it with Chrome faking IE and it wouldn't let me. The only reason I can think of to force you to use IE is if the page is attempting some unsafe operations that it can get past IEs security (which basically amounts to malware). So get that fixed if you want anyone to actually look at the page. Or just post the source code.

    BTW, the number of subsets of a set is 2^n - 1 (as we ignore the empty set). So there are 63 subsets to check for the six element sets, 2043 for the 11 element sets, and about 16070000000000000000000000000000000000000000000000 00000000000 in the 200 element set. 2043 sets shouldn't take more than a second to check. 1.607 * 10^60 should. (Modern computers do billions of operations per second, so it should only take 10^33 universe lifetimes or so.)

    Edit again: What's with the random space in the long number? It's not in the editor.
    Reply With Quote  
     

  25. #24  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    The computer program at fofallthings.com outputs a list of distinct integers and the integer sum to zero. So, there is now a known algorithm to find such a subset in polynomial time.
    Simply writing a program and showing the results for one case is not a proof. Where is the mathematical proof that your algorithm runs in polynomial time?

    At the very least, you could show the run time for a number of different size problems. For example, 10, 100, 1000 to show that the relationship is polynomial rather than exponential.

    I will contact the author if he can do that even though that would be a stress on him.
    Why would it be a stress on him to just use a larger data set?

    If that is a big problem then it sounds like he is cheating.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  26. #25  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    Sorry, I'm not opening a page that requires Internet Explorer. I tried opening it with Chrome faking IE and it wouldn't let me. The only reason I can think of to force you to use IE is if the page is attempting some unsafe operations that it can get past IEs security (which basically amounts to malware). So get that fixed if you want anyone to actually look at the page. Or just post the source code.

    BTW, the number of subsets of a set is 2^n - 1 (as we ignore the empty set). So there are 63 subsets to check for the six element sets, 2043 for the 11 element sets, and about 16070000000000000000000000000000000000000000000000 00000000000 in the 200 element set. 2043 sets shouldn't take more than a second to check. 1.607 * 10^60 should. (Modern computers do billions of operations per second, so it should only take 10^33 universe lifetimes or so.)

    Edit again: What's with the random space in the long number? It's not in the editor.
    Sorry, he’s very busy now. The reason why he’s using IE is because is the only browser that could run jnlp webstart successfully. Search the internet to look for browser compatibility to jnlp. It is only IE that is best to run jnlp webstart.

    Polynomial time means that as the complexity of the problem grows, the difficulty in solving it doesn’t grow too fast. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).

    The author said you can evaluate the time it takes to solve the 6 element sets, with the time it takes to solve the 11 element sets. Find the difference and compare if it is the same.

    More so, he added “that was the reason why I have made specifically the two versions, 6 element sets and 11 element sets”

    Don’t worry you will soon be able to input thousands of input if you like. The most important thing is that he has answered the question, solving the example given at the Wikipedia (6 element sets) and more so he has made another 11 element sets.
    Reply With Quote  
     

  27. #26  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    The computer program at fofallthings.com outputs a list of distinct integers and the integer sum to zero. So, there is now a known algorithm to find such a subset in polynomial time.
    Simply writing a program and showing the results for one case is not a proof. Where is the mathematical proof that your algorithm runs in polynomial time?

    At the very least, you could show the run time for a number of different size problems. For example, 10, 100, 1000 to show that the relationship is polynomial rather than exponential.

    I will contact the author if he can do that even though that would be a stress on him.
    Why would it be a stress on him to just use a larger data set?

    If that is a big problem then it sounds like he is cheating.
    Do you have Microsoft source code? Go and tell Microsoft that what they must be cheating. Think? If the Clay Mathematics Institute (CMI) requested for the source code i'm sure the author will give them if it is applicable.

    Any computer program that can solve the question is in polynomial time and if you’re not convinced, try and come up with your own solution that thus solves the subset sum problem quickly.

    What the computer program at fofallthings.com proved is that every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer. There is now a known algorithm to find such a subset in polynomial time.Therefore, P = NP.
    Reply With Quote  
     

  28. #27  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    Do you have Microsoft source code?
    What has that got to do with it? Microsoft are not claiming to have ground-breaking mathematical proof.

    Also, I am not asking about "his" (your) source code. I am asking where is your proof. Do you know what a proof is? It is not one trivial example.

    Any computer program that can solve the question is in polynomial time
    Where is your proof of that statement?

    The Wikipedia description of the problem, that you linked to earlier, says: "The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. " Therefore, it caanot be true that "Any computer program that can solve the question is in polynomial time".

    What the computer program at fofallthings.com proved is that every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.
    Where is the mathematical proof of this claim?

    There is now a known algorithm to find such a subset in polynomial time.Therefore, P = NP.
    Where is the mathematical proof of this claim?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  29. #28  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    Do you have Microsoft source code?
    What has that got to do with it? Microsoft are not claiming to have ground-breaking mathematical proof.Also, I am not asking about "his" (your) source code. I am asking where is your proof. Do you know what a proof is? It is not one trivial example.
    Any computer program that can solve the question is in polynomial time
    Where is your proof of that statement?The Wikipedia description of the problem, that you linked to earlier, says: "The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. " Therefore, it caanot be true that "Any computer program that can solve the question is in polynomial time".
    What the computer program at fofallthings.com proved is that every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.
    Where is the mathematical proof of this claim?
    There is now a known algorithm to find such a subset in polynomial time.Therefore, P = NP.
    Where is the mathematical proof of this claim?
    Exponential time is not versatile. Why is it that P is not NP?Once the computer program solves the problem successfully it shows that the mathematical proof that describes it is valid. Then we can go for the mathematical proof on paper.
    Reply With Quote  
     

  30. #29  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    Exponential time is not versatile.
    What does that mean?

    Why is it that P is not NP?
    We don't know if it is or not. And your program does nothing to answer this.

    Once the computer program solves the problem successfully it shows that the mathematical proof that describes it is valid.
    Only if there is a proof that the run time of the algorithm is polynomial.

    What is the time complexity of the program? O(n)? O(n log(n))? O(n2)? Or ... ?

    Then we can go for the mathematical proof on paper.
    It might be wise to do that before boasting about your result.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  31. #30  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    Exponential time is not versatile.
    What does that mean?
    Why is it that P is not NP?
    We don't know if it is or not. And your program does nothing to answer this.
    Once the computer program solves the problem successfully it shows that the mathematical proof that describes it is valid.
    Only if there is a proof that the run time of the algorithm is polynomial. What is the time complexity of the program? O(n)? O(n log(n))? O(n2)? Or ... ?
    Then we can go for the mathematical proof on paper.
    It might be wise to do that before boasting about your result.
    Okay sir, the mathematical proof in this case is the source code and it would only be released to Clay Mathematical Institutes. In as much the computer program is solving the subset sum problem and we can see. So, therefore, the author have solved the subset sum problem and P=NP. More so, if you don't believe come up with your own proof.
    Reply With Quote  
     

  32. #31  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    Okay sir, the mathematical proof in this case is the source code and it would only be released to Clay Mathematical Institutes.
    A computer program is not a proof. (It may be an implementation of the algorithm that the proof refers to, but by itself it will not win you a cent.)

    In as much the computer program is solving the subset sum problem and we can see. So, therefore, the author have solved the subset sum problem and P=NP.
    You need to do more than solve the subset sum problem. Anyone can do that. You need to prove that your algorithm runs in polynomial time. Why can you not do that? You know the details of your algorithm. If you are unable to calculate the run time of your algorithm, how can you assert it is polynomial with such confidence?

    You need a PROOF to win the prize.

    Do you expect someone to reverse engineer your algorithm from your source code and then develop a proof for you? They might do that if you let them have the million dollars for doing your job for you.

    More so, if you don't believe come up with your own proof.
    Why do so many cranks resort to this "I'm more imaginative than you"; as if being creative is more important than being right.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  33. #32  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    I'm sure the author has all the capacity it takes.
    Reply With Quote  
     

  34. #33  
    Bullshit Intolerant PhDemon's Avatar
    Join Date
    Feb 2013
    Location
    Newcastle-upon-Tyne, UK
    Posts
    4,436
    It seems this voluminous capacity is full of shit though...
    Reply With Quote  
     

  35. #34  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    I'm sure the author has all the capacity it takes.
    Why are you so sure? As he has provided no evidence of a general proof, there is no reason to take his claim seriously.

    I assume the only reason you say this is because you are the author.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  36. #35  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by lebrat
    Any computer program that can solve the question is in polynomial time


    Actually, I can write a program that solves the problem in about 2 lines of code in some languages but that solution will not be polynomial time. I have no idea why you would think that everything computers do they do in polynomial time.

    Here's a C++ snippet to solve it (though in more than just 2 lines):
    Code:
    void solve(vector<int> nums) {
      if(nums.size() == 0)
        return;
    
      int sum = 0;
      for(int i = 0; i < nums.size(); ++i)
        sum += nums[i];
    
      if(sum == 0) {
        for(int i = 0; i < nums.size(); ++i)
          cout << nums[i] << " ";
        cout << endl;
      }
    
      int last = nums.back();
      nums.pop_back();
    
      for(int i = nums.size() - 1; i >= 0; --i) {
        solve(nums);
        int temp = nums[i];
        nums[i] = last;
        last = temp;
      }
    }
    It runs just fine even if it's not particularly efficient. (It'll output the answer to your example 6 element set twice.)

    And yeah, either quit pretending to not be the author or get the actual author over here.
    Reply With Quote  
     

  37. #36  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    This requires a deeper thought... I was trying to say that if you use the right code computer can run in polynomial time. Polynomial time means that as the complexity of the problem grows, the difficulty in solving it doesn't grow too fast.We are going to creates different element sets as possible for example, 4, 5, 6, 7, 8, 9, 10,11,12... Different element sets and if the difficulty in solving them doesn't grow too fast or the difficulty doesn't grow at all it shows its polynomial time. The mathematical proof shall then be revealed to Clay Mathematical Institutes CMI.MagiMaster, the criteria are that: The program must outputs a list of distinct integers once and only once and not twice.
    Reply With Quote  
     

  38. #37  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I'm pretty sure the Clay Institute would not care if your program duplicated outputs if it actually did what you imply it does. BTW, if you only want a yes/no output, it's a pretty trivial change to the above program. (And as all P and NP problems are formulated as decision problems...)

    Actually, it's fairly simple to check if it's polynomial unless you have huge powers (which is rare). Just plug in a large random set. 70^8 steps is about 160 hours at 1 GHz. 2^70 is about 37436 years at that speed. (8 is a relatively high power for most algorithms, but maybe your algorithm uses a higher exponent. In that case, try timing random small sets versus the brute force approach. 4^20 is about 18 minutes while 2^4 is only a fraction of a second.)

    Anyway, if you've actually got anything, go ahead and send it in, but just posting "I have a solution" without posting the solution is useless. And no, your website doesn't cut it.

    Also, I run JNLP for the TopCoder app from Chrome. I just have to download the JNLP file to my computer first, but no big deal. Take out the pointless browser restriction if you want anyone to pay it any attention.

    Edit: I should probably say that if you want your million dollars, you are going to need more than just my quick test.
    Reply With Quote  
     

  39. #38  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    I'm pretty sure the Clay Institute would not care if your program duplicated outputs if it actually did what you imply it does. BTW, if you only want a yes/no output, it's a pretty trivial change to the above program. (And as all P and NP problems are formulated as decision problems...)Actually, it's fairly simple to check if it's polynomial unless you have huge powers (which is rare). Just plug in a large random set. 70^8 steps is about 160 hours at 1 GHz. 2^70 is about 37436 years at that speed. (8 is a relatively high power for most algorithms, but maybe your algorithm uses a higher exponent. In that case, try timing random small sets versus the brute force approach. 4^20 is about 18 minutes while 2^4 is only a fraction of a second.)Anyway, if you've actually got anything, go ahead and send it in, but just posting "I have a solution" without posting the solution is useless. And no, your website doesn't cut it.Also, I run JNLP for the TopCoder app from Chrome. I just have to download the JNLP file to my computer first, but no big deal. Take out the pointless browser restriction if you want anyone to pay it any attention.Edit: I should probably say that if you want your million dollars, you are going to need more than just my quick test.
    That is where the problem lies, the program should not duplicate outputs. We would here from the Clay Mathematics Institute.
    Reply With Quote  
     

  40. #39  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,137
    Quote Originally Posted by lebrat View Post
    Quote Originally Posted by MagiMaster View Post
    I'm pretty sure the Clay Institute would not care if your program duplicated outputs if it actually did what you imply it does. BTW, if you only want a yes/no output, it's a pretty trivial change to the above program. (And as all P and NP problems are formulated as decision problems...)Actually, it's fairly simple to check if it's polynomial unless you have huge powers (which is rare). Just plug in a large random set. 70^8 steps is about 160 hours at 1 GHz. 2^70 is about 37436 years at that speed. (8 is a relatively high power for most algorithms, but maybe your algorithm uses a higher exponent. In that case, try timing random small sets versus the brute force approach. 4^20 is about 18 minutes while 2^4 is only a fraction of a second.)Anyway, if you've actually got anything, go ahead and send it in, but just posting "I have a solution" without posting the solution is useless. And no, your website doesn't cut it.Also, I run JNLP for the TopCoder app from Chrome. I just have to download the JNLP file to my computer first, but no big deal. Take out the pointless browser restriction if you want anyone to pay it any attention.Edit: I should probably say that if you want your million dollars, you are going to need more than just my quick test.
    That is where the problem lies, the program should not duplicate outputs. We would here from the Clay Mathematics Institute.
    Actually the problem lies in how you establish that particular subsets do or do not sum to zero without explicitly testing them. If you are indeed explicitly testing each subset, then your routine will run in exponential time and fail the requirements. Simply looking at run-times doesn't cut it. You have to establish that there is a shortcut to the brute force approach. For example, if you are given a four-element set: , then how do you fully check this without checking all 15 non-empty subsets?
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  41. #40  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by KJW View Post
    Quote Originally Posted by lebrat View Post
    Quote Originally Posted by MagiMaster View Post
    I'm pretty sure the Clay Institute would not care if your program duplicated outputs if it actually did what you imply it does. BTW, if you only want a yes/no output, it's a pretty trivial change to the above program. (And as all P and NP problems are formulated as decision problems...)Actually, it's fairly simple to check if it's polynomial unless you have huge powers (which is rare). Just plug in a large random set. 70^8 steps is about 160 hours at 1 GHz. 2^70 is about 37436 years at that speed. (8 is a relatively high power for most algorithms, but maybe your algorithm uses a higher exponent. In that case, try timing random small sets versus the brute force approach. 4^20 is about 18 minutes while 2^4 is only a fraction of a second.)Anyway, if you've actually got anything, go ahead and send it in, but just posting "I have a solution" without posting the solution is useless. And no, your website doesn't cut it.Also, I run JNLP for the TopCoder app from Chrome. I just have to download the JNLP file to my computer first, but no big deal. Take out the pointless browser restriction if you want anyone to pay it any attention.Edit: I should probably say that if you want your million dollars, you are going to need more than just my quick test.
    That is where the problem lies, the program should not duplicate outputs. We would here from the Clay Mathematics Institute.
    Actually the problem lies in how you establish that particular subsets do or do not sum to zero without explicitly testing them. If you are indeed explicitly testing each subset, then your routine will run in exponential time and fail the requirements. Simply looking at run-times doesn't cut it. You have to establish that there is a shortcut to the brute force approach. For example, if you are given a four-element set: , then how do you fully check this without checking all 15 non-empty subsets?
    Exactly... you are going to its knowledge base I think I get your point. Is there a program that will not duplicate outputs? If yes, direct me to any.
    Reply With Quote  
     

  42. #41  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Really? You can't figure out how to fix my simple program to not duplicate outputs? Fine. Since the problem only asks whether or not such a subset exists, here's a version that outputs the first such set.

    Code:
    #include <iostream>
    #include <vector>
    using namespace std;
    
    
    bool solve(vector<int> nums) {
      if(nums.size() == 0)
        return false;
    
    
      int sum = 0;
      for(int i = 0; i < nums.size(); ++i)
        sum += nums[i];
    
    
      if(sum == 0) {
        for(int i = 0; i < nums.size(); ++i)
          cout << nums[i] << " ";
        cout << endl;
        return true;
      }
    
    
      int last = nums.back();
      nums.pop_back();
    
    
      for(int i = nums.size() - 1; i >= 0; --i) {
        bool b = solve(nums);
        if(b)
          return true;
          
        int temp = nums[i];
        nums[i] = last;
        last = temp;
      }
      
      return false;
    }
    
    
    int main() {
      vector<int> nums = {-2, -3, 15, 14, 7, -10};
      if(!solve(nums))
        cout << "No solutions." << endl;
    
    
      return 0;
    }
    Reply With Quote  
     

  43. #42  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    The computer program takes large input now. 202 element sets will give you 31 milliseconds (ms) www.fofallthings.com
    It is possible to eliminate many possible routes through this programming.
    Reply With Quote  
     

  44. #43  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Fix the stupid IE only thing or no one is going to pay your site any attention. Seriously.

    BTW, try this set: {-1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,1 6384,32768,65536,-131072,262144,-524288,1048576,2097152,4194304,-8388608,16777216,33554432,67108864,134217728,-268435456,-536870912,1073741824}. It's only 30 elements, so if should be fairly fast, right? What output do you get?
    Reply With Quote  
     

  45. #44  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Tell me if P is the set of a problems that are solvable in polynomial time and NP is the set of problems verifiable in polynomial time. Now not all P polynomials are verifiable ie the complexity of the problem exceeds the limits of Physics known. Also there is a set of problems only verifiable in polynomial time therefore you draw two intersecting circles call one P and the other NP and it is neither equal or not because an intersection exists because you cannot defy the laws of physics. For example if I had the equation for all the even numbers it is easily P and Np however if I increase the complexity of P beyond reasonable parameters ie greater than the size of the universe because the only limit on P is time whereas Np is upperlimited by the numbers of available atoms. Conversely if I wrote an Np of such complexity as to make it impossible to write an equation in P to solve then there would be no possible P for that Np. Ie an upper fundimental maximum exists in physics which acts as a limiting factor to the upper complexity of P or Np.
    Last edited by fiveworlds; December 19th, 2013 at 04:41 AM.
    Reply With Quote  
     

  46. #45  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    Fix the stupid IE only thing or no one is going to pay your site any attention. Seriously.

    BTW, try this set: {-1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,1 6384,32768,65536,-131072,262144,-524288,1048576,2097152,4194304,-8388608,16777216,33554432,67108864,134217728,-268435456,-536870912,1073741824}. It's only 30 elements, so if should be fairly fast, right? What output do you get?
    The above requested size exceeds VM limit and out of memory error java heap size. If you reach the limit of your java compiler you will get no result. It is possible to eliminate many possible routes through this programming and that is the most important thing we have done through algebraic geometric techniques.
    Reply With Quote  
     

  47. #46  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    The above requested size exceeds VM limit and out of memory error java heap size.
    I wonder if that is because the required resources are increasing exponentially rather than polynomially ... thus invalidating your claim to have a polynomial solution (it is, in general, possible to trade-off time for resources but the exponential will get you in the end).

    BTW, are you willing to admit that it is your website / code yet?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  48. #47  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Sure you can trade time for resources but can you verify that time is an infinite resource? I doubt time is because if the universe is finite then so surely is time. Time is always in finite supply you cannot solve a polynomial that takes longer time to implement than is reasonable. Time is always finite you cannot create more. You cannot solve an equation that exceeds the time limit even if it is finite. Now some people will remember the practically zero setup costs ads by google which was a lie there is always a cost on anything you do time. Now if you could work for a year and earn say $45000 for that year and instead you learn android then your setup costs are at least $45000. Now that doesnt include the cost of the heat, the electricity etc that may come as a perk of your job. Neither does it include the cost of the loss of files in time when foreign spies play god with peoples livlihoods and delete your files etc. Nor do they accept responsibility when their tampering results in the loss of jobs or closure of companies. Which is really bad when small towns depend on a perticular computer company because they are out of work overnight and no jobs replace them. Or if these superstores open in small towns and charge tiny money for veg etc and the local farmers cant compete. Now put the two together. How exactly do you just happen to bankrupt an entire city anyway? In principle a city manages and exports the primary production of its villages and town. It should also handle processing of the materials. The few exceptions to this are cities like Hong Kong which are dependant on imports because of their over expansion in their area which is a problem because the planet cannot sustain cities of that size. Overproduce gases like carbon dioxide into the environment. Increased levels of smog etc which lower life expectancies and cause damage to the localised environment. Lastly theres london which is in the process of over expanding ie they will outgrow the amount of food they can produce with increasing population. These problems are not any one persons blame but they are easily verified can they be easily solved??
    Last edited by fiveworlds; December 19th, 2013 at 06:14 PM.
    Reply With Quote  
     

  49. #48  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    @fiveworlds, P is a subset of NP. That is, all P problems are automatically NP (you can just re-solve the P problems to verify them). The question is whether there are any NP problems that are not P problems. Also, the even numbers are not P, but the question "Is n an even number?" is. All P and NP problems are decision problems. That is, they ask a yes/no question and you must get the right answer back in the specified time limit no matter which answer that is.

    @lebrat, If your program can't handle 30 inputs, then it can't handle 202. Maybe it can handle a few special cases, but not any random 202 element set.
    Reply With Quote  
     

  50. #49  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    True i agree thing is how do I verify a solved problem if there is insufficient paper to write the Np set. So how can all P automatically be Np? Also if it takes me over half the time left in the universe to run P once. Then it would be impossible to run the algorithm again because there wouldnt be time so therefore i couldnt verify it.
    Reply With Quote  
     

  51. #50  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,137
    Maybe you can describe to us how the algorithm works with a four-element set, one for which there is no subset that sums to zero. With only 15 non-empty subsets to test, that should be quite easy to do. Then we can see if it truly does operate in polynomial time.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  52. #51  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    it doesnt matter since all P equations will wind up that way eventually as time decreases since its finite if any P equation takes too long to run then it cannot be verified and this limit changes constantly. Now you could use another theory other than big bang theory but itd need to have a continuous universe. If you use big bang theory then you are always counting down to the next big bang. All you have to do to prove me wrong is prove that the big bang theory is incorrect and that the universe is infinite thats all. You know just before the next big bang youd have no time to run any algorithms in P or Np so they would both be empty sets.
    Last edited by fiveworlds; December 19th, 2013 at 07:31 PM.
    Reply With Quote  
     

  53. #52  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    P and NP are about how the time to run grows as the size of the input grows. No P problem (or any computational problem for that matter) will be too slow to run for every input. (Even the halting problem can be practically solved for some small enough inputs.)

    P is defined as those decision problems that given an input of size n can be solved in time t(n), where ln(t(n)) is less than some constant for all n (roughly). NP problems are those that given a solution, can be verified in a similar amount of time. It's pretty trivial to see that if you're given a P problem and a solution to it, you can just solve the problem and see if you get the same answer. Therefore all P problems are NP. The same doesn't work in reverse as far as anyone's been able to prove.

    I should mention that it also doesn't whether a problem would take too long to run or not. This is a theoretical computer science question (with lots of practical importance). We can work out how long a program would take to run without having to actually run it.

    Also, you can't write out the NP set. Or the P set. Both are infinite. They're sets of decision problems. Do you think you could ever write out every yes/no question?
    Reply With Quote  
     

  54. #53  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    The subject of matter; the fact remain the same, this is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    Last edited by lebrat; June 19th, 2014 at 12:48 PM.
    Reply With Quote  
     

  55. #54  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    The subject of matter; the fact remain the same, this is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    I don't believe you. For the simple cases you have solved so far, it works. For the more challenging case you have been given, it fails. Therefore you do not have a general solution and therefore it cannot be the basis of a proof of P=NP. Sorry, sounds like you are not going to get the million dollars after all.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  56. #55  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    The subject of matter; the fact remain the same, this is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    I don't believe you. For the simple cases you have solved so far, it works. For the more challenging case you have been given, it fails. Therefore you do not have a general solution and therefore it cannot be the basis of a proof of P=NP. Sorry, sounds like you are not going to get the million dollars after all.
    Check that assumed difficult task you were saying; it was not even the 30 element sets that it was said to be but it was 31 instead. Precise, the input does not follow the procedure. So, the claim is still valid that P=NP and the fact remain the same. This is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    Last edited by lebrat; December 20th, 2013 at 03:55 AM.
    Reply With Quote  
     

  57. #56  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    Precise, the input does not followed the procedure. So, the claim is still valid that P=NP and the fact remain the same.
    Sorry, but if you don't have a general solution then ... you don't have a general solution. Excuses like that don't cut it in mathematics.

    "Can I have the million dollars because I can solve this problem for a few chosen cases if you are using IE. Pleeeease..."

    This is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    That is a lie.

    You also lied about being the author of your web site and this code.

    Your credibility is slipping.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  58. #57  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    The author comes in between but if we allow that could distract our attention. It's not a lie, and if you know of any such computer program that does exactly, direct me to any? You're funny, soon the IE would not be there again.
    Reply With Quote  
     

  59. #58  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    if you know of any such computer program that does exactly, direct me to any?
    I have version that runs in constant time, requires a fixed amount of memory but only works for a subset of inputs. However, the good news is, the run time is the same for all valid inputs.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  60. #59  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by lebrat View Post
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    The subject of matter; the fact remain the same, this is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    I don't believe you. For the simple cases you have solved so far, it works. For the more challenging case you have been given, it fails. Therefore you do not have a general solution and therefore it cannot be the basis of a proof of P=NP. Sorry, sounds like you are not going to get the million dollars after all.
    Check that assumed difficult task you were saying; it was not even the 30 element sets that it was said to be but it was 31 instead. Precise, the input does not follow the procedure. So, the claim is still valid that P=NP and the fact remain the same. This is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    So I miscounted. Put the input in the proper format yourself. I don't know what format your program uses. But my point still stands. If your program can't handle a 31 element set, it can't handle a 202 element set.
    Reply With Quote  
     

  61. #60  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    This is what i have seen "Claim of proof that P = NP ...
    Don't you think it is slightly dishonest to say, "this is what I have seen" when it is you making the claim?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  62. #61  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,137
    Quote Originally Posted by MagiMaster View Post
    So I miscounted. Put the input in the proper format yourself. I don't know what format your program uses. But my point still stands. If your program can't handle a 31 element set, it can't handle a 202 element set.
    And I'm still waiting for a description of how it handles a 4 element set.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  63. #62  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Quote Originally Posted by MagiMaster View Post
    P and NP are about how the time to run grows as the size of the input grows. No P problem (or any computational problem for that matter) will be too slow to run for every input. (Even the halting problem can be practically solved for some small enough inputs.) P is defined as those decision problems that given an input of size n can be solved in time t(n), where ln(t(n)) is less than some constant for all n (roughly). NP problems are those that given a solution, can be verified in a similar amount of time. It's pretty trivial to see that if you're given a P problem and a solution to it, you can just solve the problem and see if you get the same answer. Therefore all P problems are NP. The same doesn't work in reverse as far as anyone's been able to prove. I should mention that it also doesn't whether a problem would take too long to run or not. This is a theoretical computer science question (with lots of practical importance). We can work out how long a program would take to run without having to actually run it. Also, you can't write out the NP set. Or the P set. Both are infinite. They're sets of decision problems. Do you think you could ever write out every yes/no question?
    Within a small set yes youd have to for making applications etc. Also how can you have a computer science question that completely ignores the universal computer. An area of active study for computer scientists. Just because a computational system like a solar system is outside the box doesnt mean you arent supposed to think outside the box.
    Last edited by fiveworlds; December 20th, 2013 at 06:51 AM.
    Reply With Quote  
     

  64. #63  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    Quote Originally Posted by lebrat View Post
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    The subject of matter; the fact remain the same, this is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    I don't believe you. For the simple cases you have solved so far, it works. For the more challenging case you have been given, it fails. Therefore you do not have a general solution and therefore it cannot be the basis of a proof of P=NP. Sorry, sounds like you are not going to get the million dollars after all.
    Check that assumed difficult task you were saying; it was not even the 30 element sets that it was said to be but it was 31 instead. Precise, the input does not follow the procedure. So, the claim is still valid that P=NP and the fact remain the same. This is the only computer program within a very short amount of time ever known to find such a subset that sum to zero.
    So I miscounted. Put the input in the proper format yourself. I don't know what format your program uses. But my point still stands. If your program can't handle a 31 element set, it can't handle a 202 element set.
    It can handle a 31 element set and many more only if you follow the procedure.So, a 202 element set gives you 31milliseconds.
    Reply With Quote  
     

  65. #64  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    [It can handle a 31 element set
    And yet you said:

    Quote Originally Posted by lebrat View Post
    The above requested size exceeds VM limit and out of memory error java heap size.
    I can't work out if you are deliberately dishonest or just not very bright. I favour the latter as you clearly don't understand what P or NP means; you are unable to provide a proof that your program is polynomial as claimed; I'm not even sure you know what polynomial time means or what a mathematical proof is.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  66. #65  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by Strange View Post
    Quote Originally Posted by lebrat View Post
    [It can handle a 31 element set
    And yet you said:
    Quote Originally Posted by lebrat View Post
    The above requested size exceeds VM limit and out of memory error java heap size.
    I can't work out if you are deliberately dishonest or just not very bright. I favour the latter as you clearly don't understand what P or NP means; you are unable to provide a proof that your program is polynomial as claimed; I'm not even sure you know what polynomial time means or what a mathematical proof is.
    I wonder when the 31 element set doesn't work I gave an instance of likely details. Then later, I found out. Well it isn't magic and you shouldn't expect a computer to be magical in nature. Soon, you shall have a mathematical proof. The fact remain the same, this is the only computer program within a very short amount of time ever known to find such a subset that sum to zero. If you know of any computer program that does exactly, direct me to one?
    Last edited by lebrat; December 20th, 2013 at 09:25 AM.
    Reply With Quote  
     

  67. #66  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Sets and more sets @Lebrat why not just create complicated polynomial time simultaneous equations using multiple equals signs therefore allowing for sets with thousands of elements?? Solving them is only ever as simple as solving simultaneous equations you just need to write the equation as a whole ie. x+7=y+2=z+43=t+22=n+257=3 etc
    Reply With Quote  
     

  68. #67  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    @lebrat, Let me repeat myself.

    Quote Originally Posted by MagiMaster View Post
    Put the input in the proper format yourself. I don't know what format your program uses.
    @fiveworlds, There's really not much point in trying to respond to your "arguments" as you really have no clue what you're talking about. But I will say that your simultaneous equations does not solve a subset sum problem.
    Reply With Quote  
     

  69. #68  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @MagiMaster, consistence theory is also needed such that any NP problem can be transformed into any of the NP-complete problems. It is not necessarily that they must behave randomly. What really matter is that the problem was solved.
    Reply With Quote  
     

  70. #69  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Not all NP problems are NP-complete. Also, nothing in this thread has anything to do with randomness. (All P and NP problems should be deterministic.) And you have yet to provide any proof that the problem is solved. How about you just link us to the news article about you winning the million.
    Reply With Quote  
     

  71. #70  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Quote Originally Posted by MagiMaster View Post
    @lebrat, If your program can't handle 30 inputs, then it can't handle 202. Maybe it can handle a few special cases, but not any random 202 element set.
    It is not necessarily that they must behave randomly. What really matter is that the problem was solved and if you don't believe, come up with a computer program that does exactly or you may direct me to any computer program that does exactly?
    Reply With Quote  
     

  72. #71  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,137
    Quote Originally Posted by lebrat View Post
    What really matter is that the problem was solved and if you don't believe, come up with a computer program that does exactly or you may direct me to any computer program that does exactly?
    How does our inability to come up with such a computer program prove you right?
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  73. #72  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    That's what I was about to ask. That makes no sense. Also, exactly what?
    Reply With Quote  
     

  74. #73  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    What really matter is that the problem was solved
    No what really matters is that you prove that (a) your program runs in polynomial time and (b) that it works for all cases, not just a few specially chosen ones.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  75. #74  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    It is not necessarily that the input must be random. So, there is no problem of such few cases soon you shall have the mathematical proof. The fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    Reply With Quote  
     

  76. #75  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    It is not necessarily that the input must be random.
    It is not amatter of the input being random; it is that your algorithm must work for all cases. It clearly doesn't.

    So, there is no problem of such few cases soon you shall have the mathematical proof.
    Then please go away until you have such a proof. You are just wasting everyone's time (including your own) with these empty claims.

    The fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero.
    No it isn't. I have one that runs in linear time for any size input (but only for a subset of possible inputs).

    That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    You still don't get it do you: the ability of anyone else to write a program says NOTHING about your claimed algorithm. I don't that someone with such a poor grasp of simple logic is going to develop a proof of anything.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  77. #76  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange, this is my thread nobody force you to talk. If you can't come up with the computer program you may go.
    Reply With Quote  
     

  78. #77  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    @Strange, this is my thread nobody force you to talk.
    This is a public discussion forum. You are the one wasting people's time with unsubstantiated claims. You should be spending your time developing a proof. You won't get a million dollars for posting comments here.

    If you can't come up with the computer program you may go.
    Whether or not I can come up with a program is irrelevant.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  79. #78  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange, you are wasting your precious time nobody force you to talk and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    Reply With Quote  
     

  80. #79  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    @Strange, you are wasting your precious time nobody force you to talk
    It is quite amusing so not really a waste of time. You, on the other hand, should be getting on with a proof of your claims.

    and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero.
    No one will believe this without a proof. Come one, get on with it.

    That is the extent we can prove that P=NP
    In other words, you can't prove anything.

    and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    Why do you keep saying that, when it is obviously irrelevant to your claim? What is wrong with you?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  81. #80  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange, still you are wasting your precious time nobody force you to talk and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    Reply With Quote  
     

  82. #81  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    @Strange, still you are wasting your precious time nobody force you to talk and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero.
    Prove it.

    if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    What the hell is wrong with you? Are you ill?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  83. #82  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange, ill unless you are? And I'm sure the author will be amazed seeing you like this. You are wasting your precious time nobody force you to talk and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    Reply With Quote  
     

  84. #83  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by lebrat View Post
    this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero.
    Proof required.

    That is the extent we can prove that P=NP
    In other words, you don't have a proof.

    and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero
    Can you explain why you think that is relevant? It seems to me equivalent to saying: "I have built a time machine, if you don't believe me then build one yourself". Utterly meaningless.

    p.s. I am not wasting my time: your comments are so repetitive, that I have just automated my responses. If you don't believe me, then write a program to do it.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  85. #84  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange,don't you have something else doing with your time about what you can't do already! See, you are wasting your precious time nobody force you to talk and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero.
    Reply With Quote  
     

  86. #85  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Proof needed.
    Irrelevant.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  87. #86  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange, the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero. Soon, you shall have the mathematical proof.
    Reply With Quote  
     

  88. #87  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Proof needed.
    Irrelevant.

    Stop wasting time and get on with your proof.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  89. #88  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    @Strange,don't you have something else doing with your time about what you can't do already! See, you are wasting your precious time nobody force you to talk and the fact remain the same, this is the only computer program within a very short amount of time ever known that takes large input to find such a subset that sum to zero. That is the extent we can prove that P=NP and if you're not convinced come up with any computer program that takes large input and quickly find a subset that sum to zero. Soon, you shall have the mathematical proof.
    Reply With Quote  
     

  90. #89  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    OK. I'm bored now. I await your proof with interest.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  91. #90  
    Forum Freshman
    Join Date
    Nov 2013
    Posts
    96
    Soon, you will have the mathematical proof.
    Last edited by lebrat; December 23rd, 2013 at 06:29 AM.
    Reply With Quote  
     

  92. #91  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Quote Originally Posted by MagiMaster View Post
    @lebrat, Let me repeat myself.
    Quote Originally Posted by MagiMaster View Post
    Put the input in the proper format yourself. I don't know what format your program uses.
    @fiveworlds, There's really not much point in trying to respond to your "arguments" as you really have no clue what you're talking about. But I will say that your simultaneous equations does not solve a subset sum problem.
    Actually it does so I really dont see your point. Secondly look at the Halting Problem prove wether for any finite input the equation has a finite runtime or runs forever. Hypothesis is this unsolvable its wrong every algorithm has a finite runtime because of universal resource constraints. Thirdly a simultaneous equation is a solvable P equation now since an Np exists for the subset sum problem and simultaneous equation are P then the subset sum has a solvable P equation.
    Last edited by fiveworlds; December 23rd, 2013 at 10:21 AM.
    Reply With Quote  
     

  93. #92  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by fiveworlds View Post
    Secondly look at the Halting Problem prove wether for any finite input the equation has a finite runtime or runs forever. Hypothesis is this unsolvable its wrong every algorithm has a finite runtime because of universal resource constraints.
    1. It is not a hypothesis, it is a proof.

    2. It has nothing to do with "universal resource constraints".

    3. Why do you keep posting such profoundly ignorant nonsense?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  94. #93  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Everything is to do with universal resource constraints even if I had a time machine which I dont I cant keep on traveling back in time forever a who know what happens if two of you exist at the same time. You cant just say the pressure differential between the top and bottom of the tower is its height if it is possible to equalise the pressure of the top and bottom. Otherwise you form a biased opinion
    Reply With Quote  
     

  95. #94  
    Genius Duck Moderator Dywyddyr's Avatar
    Join Date
    Jan 2013
    Location
    Scunthorpe, UK
    Posts
    10,679
    Please stop posting crap.
    "[Dywyddyr] makes a grumpy bastard like me seem like a happy go lucky scamp" - PhDemon
    Reply With Quote  
     

  96. #95  
    Suspended
    Join Date
    Apr 2012
    Posts
    690
    Hmm im sure it isnt biased. I have an image here i know what it is now im going to burn it. When you can easily verify in Np what that image was then i might listen. You know about crap actually im in a terrible predicament maybe youd help i have 2000 turkeys here that need to be bled, plucked and cleaned out Id do it myself usually but didnt I fall on the range and burn my hand. Youll get paid nothing of course couldnt afford it but there ppl who wont eat if you dont help.
    Last edited by fiveworlds; December 23rd, 2013 at 11:50 AM.
    Reply With Quote  
     

  97. #96  
    Suspended
    Join Date
    Apr 2007
    Location
    Pennsylvania
    Posts
    8,822
    Moved thread to pseudoscience. Started out to split out fiveworlds nonsense, but then decided the whole thread doesn't belong in the hard science section.
    Reply With Quote  
     

  98. #97  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    For anyone still reading, when we talk about P and NP problems, we're not talking about how they run on real computers. We're talking about how they run on idealized computers (with infinite resources) and in the worst case. Of course, you eventually have to implement the algorithms on actual computers, but their limits don't have anything to do with complexity classes. Similarly, real algorithms may run very quickly for a few special inputs, but again that doesn't imply anything about their complexity class.
    Strange likes this.
    Reply With Quote  
     

  99. #98  
    Forum Freshman WaterWalker's Avatar
    Join Date
    Jan 2013
    Location
    KZN, South Africa
    Posts
    79
    Ok, so I also have to get my 2 cents worth in. In my mind(my own small little world), P does NOT equal NP. Allow me to explain why I think so. As far as I can remember, "{-2, -3, 15, 14, 7, -10} does some nonempty subset of them sum to 0?" was only used as an example. My understanding was that for this problem to be solved or to be true, any amount of integer sets could be used, and can sum to a number "x", "x" being specified by the user.

    Also, the above should be able to be calculated in an amount of time and/or verified in an amount of time that is more or less equal. In other words, lets take this example. I'll keep it simple to demonstrate my understanding.

    Take numerical set {1, 2, 3, 4, 5, 6}. Now, is there a subset of numbers that can sum to 7? Quickly checking, you get a "Yes". 1 and 6 can sum to 7. However, 2 and 5 can aswell. As well as 3 and 4. And lets not forget 1, 2 and 4 also sums to 7. So, we have 4 subsets of numbers. For simplicity lets say it takes 1 second per subset to calculate. (I know it will take only a few nano-seconds in real life). That means it will take 4 seconds to give an answer of "Yes". The verification process will take only 1 second because it only needs to check 1 subset of numbers.

    But look, I know I'm not the brightest crayon in lightsocket, so I stand to be corrected. Please, feel free to point out any misunderstandings, misconceptions or misdirections I might have.
    "No army is stronger than an idea whose time has come." - Victor Hugo

    Dywyddyr - "You're rather good at denying reality, aren't you?"
    Plautus - "False."
    Dywyddyr - "And you've done it again. Well done. Would you like a biscuit?"
    Reply With Quote  
     

  100. #99 Combination locks! 
    New Member
    Join Date
    Jan 2014
    Posts
    1
    Imagine that there is a lock on the computer. The problem is to unlock it. It is a combination lock, andhe password is a number between 1 and... say, 1 billion. To unlock this lock, it could take up to 1 billion tries, but to prove that a number is the password, you just enter it in the lock and BAM, it's unlocked.

    Is that a legit solution? If not, I have another problem.

    Imagine that there is a lock(again) on the computer, but now it's a lock that has a password that is a combination of numbers that is between 1 and... say, 1000 (or more if you want?). For example, a possible password is to press a combination of these numbers: 135, 247, 351, 412, 547, 761 and 994. to unlock the lock, the computer has to try (lol I don't bother counting how many) A LOT of possible combinations, but to verify the password, you just chuck in the correct numbers and you unlock the lock.

    If I win the prize money, please send it to this addre-- Just kidding.
    I'm just 14 this year (2014) so forgive me if I made errors.
    Reply With Quote  
     

  101. #100  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,531
    Quote Originally Posted by nboadfnavjlolololol View Post
    Imagine that there is a lock on the computer. The problem is to unlock it. It is a combination lock, andhe password is a number between 1 and... say, 1 billion. To unlock this lock, it could take up to 1 billion tries, but to prove that a number is the password, you just enter it in the lock and BAM, it's unlocked.
    That is a very good analogy for the P=NP problem. I might use it in future.

    However, it isn't a solution. All you have considered is the "dumb" brute force approach to cracking a combination lock. This could take up to N! (I think) attempts. But other problems are known to have solutions that are faster than than the most obvious approach (but still more than polynomial time). So you need to prove (mathematical) that either there are no faster solutions or that there is at least one.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

Page 1 of 2 12 LastLast

Similar Threads

  1. Mathematical Sum of Functions Problem
    By in forum Mathematics
    Replies: 9
    Last Post: January 16th, 2011, 06:18 AM
  2. problem to be solved
    By seccam in forum General Discussion
    Replies: 2
    Last Post: January 2nd, 2011, 03:55 AM
  3. Hilbert's 6th Problem Solved:
    By Unification123 in forum Mathematics
    Replies: 7
    Last Post: December 30th, 2009, 08:04 AM
  4. Water shortages- Problem solved?
    By RosenNoir in forum Environmental Issues
    Replies: 18
    Last Post: April 4th, 2009, 02:44 PM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •