Because you can not add in one motion. It is impossible to be given numbers: 3,4,6 and add three to each in one motion. If this was possible NP complete problems would be simple. Without this criteria it is impossible to solve NP complete problems without exponential time.
The problem of NP complete problems are not suited to the computer. Another means of calculation would be better suited.
Name:
Anonymous2008-06-09 12:16
Thank you, Dr. Science.
Name:
Anonymous2008-06-09 12:25
>>1
Fortunately, we don't use Turing machines for calculation.
Basically P=NP is just a bitch because with traditional computer methods (numerical) it becomes exponential due to all the additions that need to be made and the act of the final "is this number equal to the sum" check which is also exponential.
Pictorial systems that model numbers closer to reality suffer from the obscene space requirements to store precise information. For instance if you wanted to store the number 529520 in a pictorial system it requires 10^6 bits. Of course you get the ability to store a lot more numbers in this space than just one (since overlap means jack shit in NP complete problems). Although you get quick addition, final check, and copying (sort of if you take it independent of the huge storage needed).
Of course the "reality computer" has these obscene space storage abilities although I doubt we could ever use such a thing due to the imprecision of physical measurements.
>>8
Pictorial is just a name I came up with on the spot. Anyway basically it is the same thing as a number line type thing modeled in a computer. If you had 100 bits (with padding). And you set them all to zero then set the 54th bit to 1 you would have the number 54 stored. To add 5 to all numbers all you have to do is switch the location of the origin to -5. Then the 54th bit becomes the 59th bit automatically. This allows you to add to a set of numbers in 1 movement.
If you want to check if a number is present or copy etc bitwise operators will do the trick. Using this type of system NP complete problems are "Easy" but the precision required for more precise numbers leads to a lot of space required.
"reality computer" relates to real life. Aka instead of 1s and 0s in a programmable machine it would be a physical model such as a piece of paper you mark. This system runs into the same precision problems because of how hard it is to get accurate physical measurements.
Basically NP complete problems are hard in both precision and the growing number of possibities. The precision hurts the physically based pictorial system. While the exponential possibilities hurts the numeric system aka 150528 (which is obviously not physically based at all 150528 has no real meaning compared to a point marked 150528 distance away from an origin).
Name:
Anonymous2008-06-09 13:34
even a mix of the two runs into the same problems.
If you mix the two into one system to model numbers you can get it to the point you can add at once. The problem is the actual number is hard to determine.
For instance you could have the number 5250
In a mixed system this could be modeled as
60 in the ones place
-1 in the tens place
52 in the hundreds place
Obviously you can do operations to Sets of this representation of numbers in one movement but you run into the problem of it being so hard to figure out where the number actually is. So you can compact storage of numerical, the operations on sets of pictorial, but you lose the ability to quickly know the number in questions relation to other numbers. It would require transformation into the strictly numerical or pictorial to ascertain comparison tests.
ITT people who haven't messed with NP complete problems enough
Yes my writing is mostly scribbles as it really isn't worth the time to explain them thoroughly and I am not filtering them at all. Also none of it really matters as it sheds no new light that isn't already known about NP-completeness.
From Wikipedia:
The complexity (difficulty of solution) of subset sum can be viewed as depending on two parameters, N, the number of decision variables, and P, the precision of the problem (stated as the number of binary place values that it takes to state the problem). (Note: here the letters N and P mean something different than what they mean in the NP class of problems.)
The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. Thus, the problem is most difficult if N and P are of the same order. It only becomes easy if either N or P becomes very small.
If N (the number of variables) is small, then an exhaustive search for the solution is practical. If P (the number of place values) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.
What is happening is that the problem becomes seemingly non-exponential when it is practical to count the entire solution space. There are two ways to count the solution space in the subset sum problem. One is to count the number of ways the variables can be combined. There are 2^N possible ways to combine the variables. However, with N = 10, there are only 1024 possible combinations to check. These can be counted easily with a branching search. The other way is to count all possible numerical values that the combinations can take. There are 2^P possible numerical sums. However, with P = 5 there are only 32 possible numerical values that the combinations can take. These can be counted easily with a dynamic programming algorithm. When N = P and both are large, then there is no aspect of the solution space that can be counted easily.
>>1
Your wrong bitch. P=NP is impossible on our current turing machine implementation within reasonable human timeframe references for non-trivial data sets.
Name:
Anonymous2008-06-10 5:34
our current turing machine implementation
It is impossible to implement a turing machine unless the size of the universe is infinite.
Unfortunately, determining whether the size of the universe is infinite or not is equivalent to the halting problem.
Name:
Anonymous2008-06-10 8:26
Posting in a thread full of bullshit informal arguments
Name:
Anonymous2008-06-10 13:14
>>20 Unfortunately, determining whether the size of the universe is infinite or not is equivalent to the halting problem.
It's really not. The universe very obviously isn't infinite.
>>31
Look up what a scientific theory is and why it isn't the same as empty sophistry or a random shot in the dark.
Then look up what proof means and why it cannot possibly apply to real-world situations.
Name:
Anonymous2008-06-10 22:23
>>33
crackpots often use the word "theory" to describe things that are not, in fact, scientific theories.
can you prove that determining whether the universe is infinitely large is not equivalent to the halting problem? that's what i want proof of, not whether the universe actually is of infinite size or not.
Name:
Anonymous2008-06-10 23:44
>>34 can you prove that determining whether the universe is infinitely large is not equivalent to the halting problem?
Burden of proof, nigger. You came up with this absurd hypothesis, you prove it.
Name:
Anonymous2008-06-11 0:41
theory, science, proof, etc. Go back to overcomingbias.com, please
Name:
Anonymous2008-06-11 18:20
Prove P!=NP and collect your millions if you're so sure.
Name:
Anonymous2008-06-11 18:54
>>37
Not even remotely related to anything being discussed here. Reading comprehension, dude.
Name:
Anonymous2008-06-11 19:02
>>29 "Universe" refers to space, not the matter in it; you are retarded.
Fixed to adhere to standard.
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy