Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

P=NP is impossible on a turing machine

Name: Anonymous 2008-06-09 12:10

The reason?

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: Anonymous 2008-06-09 13:28

YHBT

>>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: Anonymous 2008-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.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List