Thread: P = NP, subset sum problem solved.

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.

Congratulations, I'm sure your $1m check is now in the mail.

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.

Just in case anyone's wondering, the problem isn't solving the subset sum problem, it's solving it quickly (in a technical sense).

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).

Originally Posted by lebrat

The site: www.fofallthings.com

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.

Originally Posted by MagiMaster

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.

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

Originally Posted by Strange

Originally Posted by lebrat

The site: www.fofallthings.com

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.

Originally Posted by lebrat

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"?

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"?

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.)

Originally Posted by MagiMaster

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.

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).

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.

Originally Posted by lebrat

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.

Originally Posted by lebrat

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?

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.

Originally Posted by lebrat

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.

Originally Posted by Strange

Originally Posted by lebrat

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.

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.

Originally Posted by MagiMaster

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.

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.

Originally Posted by lebrat

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.

Originally Posted by MagiMaster

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.

Originally Posted by Strange

Originally Posted by lebrat

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.

Originally Posted by lebrat

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?

Originally Posted by Strange

Originally Posted by lebrat

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.

Originally Posted by lebrat

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(n²)? Or ... ?

Then we can go for the mathematical proof on paper.

It might be wise to do that before boasting about your result.

Originally Posted by Strange

Originally Posted by lebrat

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(n²)? 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.

Originally Posted by lebrat

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.

I'm sure the author has all the capacity it takes.

It seems this voluminous capacity is full of shit though...

Originally Posted by lebrat

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.

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.

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.

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.

Originally Posted by MagiMaster

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.

Originally Posted by lebrat

Originally Posted by MagiMaster

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?

Originally Posted by KJW

Originally Posted by lebrat

Originally Posted by MagiMaster

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.

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;
}

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.

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?

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.

Originally Posted by MagiMaster

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.

Originally Posted by lebrat

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?

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??

@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.

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.

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.

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.

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?

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.

Originally Posted by lebrat

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.

Originally Posted by Strange

Originally Posted by lebrat

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.

Originally Posted by lebrat

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.

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.

Originally Posted by lebrat

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.

Originally Posted by lebrat

Originally Posted by Strange

Originally Posted by lebrat

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.

Originally Posted by lebrat

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?

Originally Posted by MagiMaster

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.

Originally Posted by MagiMaster

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.

Originally Posted by MagiMaster

Originally Posted by lebrat

Originally Posted by Strange

Originally Posted by lebrat

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.

Originally Posted by lebrat

[It can handle a 31 element set

And yet you said:

Originally Posted by lebrat

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.

Originally Posted by Strange

Originally Posted by lebrat

[It can handle a 31 element set

And yet you said:

Originally Posted by lebrat

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?

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

@lebrat, Let me repeat myself.

Originally Posted by MagiMaster

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.

@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.

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.

Originally Posted by MagiMaster

@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?

Originally Posted by lebrat

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?

That's what I was about to ask. That makes no sense. Also, exactly what?

Originally Posted by lebrat

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.

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.

Originally Posted by lebrat

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.

@Strange, this is my thread nobody force you to talk. If you can't come up with the computer program you may go.

Originally Posted by lebrat

@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.

@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.

Originally Posted by lebrat

@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?

@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.

Originally Posted by lebrat

@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?

@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.

Originally Posted by lebrat

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.

@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.

Proof needed.
Irrelevant.

@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.

Proof needed.
Irrelevant.

Stop wasting time and get on with your proof.

@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.

OK. I'm bored now. I await your proof with interest.

Soon, you will have the mathematical proof.

Originally Posted by MagiMaster

@lebrat, Let me repeat myself.

Originally Posted by MagiMaster

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.

Originally Posted by fiveworlds

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?

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

Please stop posting crap.

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.

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.

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.

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.

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.

Originally Posted by nboadfnavjlolololol

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.