View Question
 Question
 Subject: P=NP (preferrably MathTalk) Category: Science Asked by: mrsneaky-ga List Price: \$50.00 Posted: 07 Jan 2004 17:22 PST Expires: 06 Feb 2004 17:22 PST Question ID: 294221
 ```Does P=NP? I have a theory and I would like your opinion Mathtalk? P=NP For definition and details on the problem see: http://www.claymath.org/Millennium_Prize_Problems/P_vs_NP The solution is if I want to compress data, I can take an arbitrary amount of data. For this example I?m going to use 1 Megabyte of random data (2^1,048,576 bytes) or 8,388,608 bits. If I can take a completely set of random data and compress or represent the same data in less bits than the original set for ALL data then P=NP. The data can have values than can be converted to a decimal representation (base 10 or any base for that matter). Although a VERY large number with million of digits long the number is finite. The EXACT same number can be represented by a ?series? of bytes for example broken up in 8 bytes a piece. (Like a computer program)) These 2 numbers: a series and 1 large ?whole? number although on the face have no obvious correlation they are the same data in base 10. So I can set up a relationship of my original data set of BIG NUMBER= SERIES OF DATA (a,b,c,d?.). Now OBVIOUSLY the magnitude (or size) to represent the data values is exactly the same. I?m reading the same data to create the equation. (More on Symmetry later). So if I can set the equation with a 3rd new dataset with less data then P=NP. Using the properties of Factorials I will prove P=NP. More on Factorials: http://mathworld.wolfram.com/Factorial.html Utilizing the properties of Factorials (X!), We can compress the data. The largest Factorial that satisfies this equation 2^8,388,608 > X! is 481176! Proof provided by research at Google Answers: http://answers.google.com/answers/threadview?id=292562 Second Proof we will need is that X!^2 > the next factorial http://answers.google.com/answers/threadview?id=293570 So starting from position 0 in a new data file to represent the original data I will use the first bit to tell me if I can subtract 481,176! from the ORIGINAL DATA. If it is I store the first bit as 1 and I subtract the 2 numbers. Then the remaining data is tested against (X!-1). The data will lose magnitude ( in a factorial progression). It should be no concern if the factorial could be subtracted out more than once we have plenty of room to store it if it was possible. Proof: http://answers.google.com/answers/threadview?id=293570 So the original data will get smaller and smaller to 0 when I get to the last factorial 1!. Most of the time the X! Factorial will < the data. But occasionally the factorial will subtract enough off the next factorial will not. This creates a superposition of the values being subtracted off. So if I store whether or not the factorials are < than the remaining data I will have stored all 8,388,608 in 481,176 bits. With that P=NP. (Note: this is a very rough draft and typos or spelling maybe questionable.)``` Clarification of Question by mrsneaky-ga on 07 Jan 2004 18:22 PST ```I found small error... in the smaller numbers I may need some extra bits as counters. Below a certain number the factorial may go in more than once.. But the number is very small and grows only at the VERY end (with small numbers).``` Clarification of Question by mrsneaky-ga on 07 Jan 2004 23:53 PST ```1 last point I don't think is very clear upon rereading the question. The series of data creates a whole number and why they would be equal. The data could be from a JPEG file as an example. For all intensive purposes random data. So as each byte is stored in sequence to the 1st megabyte. The result would be a very large whole number millions of digits long. So therefore the Series=Whole Number The other thing on the clarification. The last couple factorials ( < 10 )(or something very small)) may need additional "counters" which would be the exponent value (verses just 1 and 0 as counters). Even if every factorial needed 8 bits (256 (which is impossible) the data would still shrink. There are a couple typos or mistakes like (X!-1) should have been (X-1)! for example, but I think you should see through those.``` Clarification of Question by mrsneaky-ga on 08 Jan 2004 12:56 PST ```The original plan was to leave 8 bits for each factorial (255 times) which is WAY overkill. With more effort I can allocate bits as needed. But even if I allowed 255 times for each factorial to be subtracted the net is 1MB to 481,176bytes (not bits). The process is also iterative. So I can do it over and over.``` Request for Question Clarification by mathtalk-ga on 08 Jan 2004 13:12 PST ```Hi, mrsneaky-ga: I haven't completely parsed out your Question yet, but you raise two issues: 1) Does P=NP? 2) Can one "take a completely set of random data and compress or represent the same data in less bits than the original set for ALL data"? You suggest that 2) implies 1), which I can agree with (although I haven't understood yet how you see the implication) because 2), at least in the broad sense which you seem to imply by putting "ALL data" as the qualifier, is false. Consider for example a datum consisting of a single bit, which may be 0 or 1 with equal probability. Can this be compressed to less than one bit? While I think it is relatively easy to agree that further compression is impossible for "small" amounts of data, you seem to have focused on the possibility of doing something better with larger amounts of data. It is understandable that with so many frequent successes of compressing files to smaller ones, it may seem that by some more sophisticated techniques we will eventually do what you suggest, compress the size of any and all input streams. But mathematically this is impossible. The reality of any "lossless" compression technique is that there is a tradeoff between the files that can be compressed (often by a great deal) and those which actually expand when "compressed" even if it is only by a little bit. If you were to look at the entire universe of files, you'd see that the accounts balance exactly, according to the strict laws of mathematics. What makes the compression algorithms such as used in PKZIP of practical importance is that the distribution of files that are important to us (as humans) tends to overrepresent the small portion of that universe in which compression is somewhat to very effective. I will be eager to read your post more carefully this evening. In the meantime I wanted you to have a chance to rethink the price; I believe you have offered too much for the little insight that I may be able to add. regards, mathtalk-ga``` Clarification of Question by mrsneaky-ga on 08 Jan 2004 13:51 PST ```I need to add an extra term in the equations so it will make more sense tonight. I want to store the "exponent" value of the factorial that I will "subtract". not how many times I want to subtract a specific factorial. I completely understand it is impossible. I ask for an open mind.``` Clarification of Question by mrsneaky-ga on 08 Jan 2004 14:00 PST ```So to start over in a sense: I want to the Original Whole Number created by a data set. That is called Z. Z - X!^Y will give me a new remainder set. I store only Y for each factorial from 481,176! to 1! Y in my opinion will never be larger than 255. And thats what I would like help on. Can ^Y be larger than 255??? (I can't seem to find where I can make Y larger than 255)``` Clarification of Question by mrsneaky-ga on 08 Jan 2004 14:04 PST `and take it a step further Y can be as large as 2^16 and it still work.` Clarification of Question by mrsneaky-ga on 08 Jan 2004 15:49 PST ```Good Evening Mathtalk: Let me try to explain what I think is possible. And I could be wrong, and you are the man to prove me wrong. :) I want to create a factorial map back to a very large number - 1 MB(this number is arbitrary) which has a finite whole number value. Utilizing Factorials we know that the largest possible Factorial that "fits" into the data is 481176!. Using Factorials as the "currency" in expodential terms. I thought I could lay out a map from a binary number to a new equivelent "factorial" number stored as binary. So therefore compressed. That is what I was trying to do. I may need to use 4 or 5 significant digits to use predetermined fractional exponents to get "closer" to the data. This idea is been a work in progress no means finished. I'm just exploring an idea.``` Request for Question Clarification by mathtalk-ga on 08 Jan 2004 16:16 PST ```I've been trying to follow how you will define the mapping. Agreed we start with a number Z greater than 0 and less than 2^8,388,608. I would like to resist the labelling of Z as a "big" number, as I think it may be crucial to your argument to define the mapping for all numbers Z in this range. Your construction sounds a bit like using "mixed radix" position notation for numbers, where the highest order position gives the number of multiples of 481176! contained in Z, the next highest gives multiples of 481175!, and so on all the way down to the lowest position = multiples of 1! = 1. This leads to a unique representation of the form: Z = d0*(481176!) + d1*(481175!) + d2*(481174!) + . . . + d481175*(1!) Now I confess that this is merely an idea that popped into my head from reading some of your Clarifications, esp. the most recent one, and not necessarily one you meant to put there. For in places you also refer to exponents and in particular the idea of (largest?) Y such that Z - (X!)^Y gives "a new remainder set", and of this construction I am completely uncertain how to get unique representations. In particular note that when X = 1, the exponent Y can be arbitrarily large yet give the same result. I would suggest working from the simple end of the range: What does your mapping do to represent 1? 2? and so on, until the definition is clear to you. Then you can perhaps define the mapping for "large" Z in a succinct fashion. regards, mathtalk-ga``` Clarification of Question by mrsneaky-ga on 11 Jan 2004 23:24 PST ```I appreciate the very informative information. I'll continue to think about the problem. I'm sure I'll have future questions.``` Request for Question Clarification by mathtalk-ga on 12 Jan 2004 07:49 PST ```Hi, mrsneaky-ga: Perhaps you'd be interested in a discussion of P=NP ? There was actually some new announcement of results on this front, and I could try to catch you up on the story. regards, mathtalk-ga``` Clarification of Question by mrsneaky-ga on 01 Feb 2004 21:03 PST ```MathTalk: Can you review this document with attached spreadsheets. the link is http://4thandinchesinc.com/p.htm. I think you should find it at least a little interesting. Any opinion would be considered an answer to this question. Thanks, MrSneaky``` Request for Question Clarification by mathtalk-ga on 01 Feb 2004 22:43 PST ```Sure, I'll take a look! --mathtalk-ga``` Clarification of Question by mrsneaky-ga on 03 Feb 2004 15:51 PST `Great! Thanks again!` Clarification of Question by mrsneaky-ga on 05 Feb 2004 08:18 PST `Should I make a new question since this is going to expire tomorrow?` Request for Question Clarification by mathtalk-ga on 05 Feb 2004 08:23 PST ```No, I'll post my remarks tonight unless the dreaded Unable to Process message proves an obstacle. Most times one can get through with a bit of persistance. Thanks, Mathtalk-ga```
 Subject: Re: P=NP (preferrably MathTalk) Answered By: mathtalk-ga on 05 Feb 2004 19:00 PST
 ```Hi, MrSneaky: I've tried to sort out your outlined proof that by compressing any 1 Megabyte dataset into a smaller one, the P=NP problem can be solved. Here are some comments: 1) Although you declare that a goal of your construction is to solve the P=NP problem, you say little about how you mean this. Besides providing a link the the Millennium Challenge Prizes page, almost your only mention of P=NP says simply: A separate independent proof that states,? if a general solution were to be found, it would meet the requirements of P=NP and violate the Counting Theorem?. I would expect considerably more detail about why one should believe that P=NP. 2) From your earlier statements you accept that an arbitrary 1 Megabyte dataset can be identfied as a nonnegative integer between 0 and 2^N-1 where: N = 8,388,608 and from the above mention of violating "the Counting Theorem" you seem to be aware that you are in essence proposing that the basic theory of arithmetic is inconsistent. It is hard for me to understand how you might believe this, for a sincere belief in this would seem to make one completely indifferent as to whether the Millennium Prize is one million dollars or one dollar. After all, if counting gives whatever answer you wish, then objectively there is no distinction. 3) If you wish to understand in detail where your attempted construction goes awry, you can compare the formula you give for representing C: C = SUM X(k) * (k!)^Y(k) FOR k = 1 to 481,176 with the formula I gave above for a "mixed radix" number representation: C = SUM X(k) * (k!) FOR k = 1 to 481,176 I noted that in my formula, the integer values X(k) could be found to yield C in the range you want subject to X(k) between 0 and k (inclusive). In your construction you introduce exponents Y(k), which are said to be between 1 and 2, and so in general do not have integer values. But then it is no longer clear what values you will produce in your formula. You mention limiting these exponents Y to some particular values numbering as many as 256, and also you introduce a notion of "approximation". It then is completely open as to what your formula can or cannot represent. Finally I'd like to know your reaction to the following thought experiment. If your construction were applied to each of the 2^8,388,608 possible inputs, how many different outputs would you get? If there are two inputs which produce the same output, does this not prove that your "compression" algorithm would not allow for a "decompression" algorithm to undo its action? regards, mathtalk-ga```
 ```This part I agree with: "If I can take a completely set of random data and compress or represent the same data in less bits than the original set for ALL data then P=NP." That is a true statement, but the fact is that your premise is false. You cannot represent the same data in less bits than the original for ALL data. It is a logical impossibility. I can demonstrate what you claim is impossible without even looking function box for which you put in an input and you get an output. You claim that: - you can put any of the 2^8,388,608 inputs in - that you will get an output that is less than 8,388,608 bits for every input. A necessary condition for the proof is that the process is lossless. That means that it is a requirement that you cannot get the same output for two different inputs. If two inputs produce the same output the process is lossy and you cannot know which of the inputs to reproduce in the decompression. This set of requirements is a logical impossibility based on the pigeonhole principle. The pigeon hole principle says that you cannot put N pigeons into N - 1 holes and only have one pigeon in each hole. In mathematical terms, it means you cannot have a bijection between two sets of unequal size (the notion of size becomes a little more complex when talking about infinite sets, but you were talking about finite sets). An example of the pigeon hole principle is that it is impossible to assign a unique 7 digit decimal telephone number to a population of 100 million people. There are only 10 million possible 7 digit telephone number. To apply that to your proof you claim that you can compress every one of the 2^8,388,608 inputs down to 481,176 bytes. There are only 256^481,776 or 2^3,854,208 possible combinations of bits that size. If every input produces an output of that size then by the pigeon hole principle some of the inputs are produce the same output. The process is therefore lossy and fails to be true. Notice here that I didn't even delve into factorials. All I did was count the number of inputs and the number of outputs. Since the number of inputs is larger than the number of outputs it is impossible to have a bijection and therefore it is impossible for the process to be lossless.```
 ```This is to give a brief illustration of the idea of a mixed radius positional notation, using factorials as place values. Consider the decimal representation 100. Already 5! is beyond this, so we will have zeros in all positions corresponding to 5! and above. Now 4! goes into 100 four times, with a remainder of four: hundred = (four * 4!) + four = (four * 4!) + (zero * 3!) + four = (four * 4!) + (zero * 3!) + (two * 2!) + zero So in this "factorial" mixed radix notation, we would represent one hundred with this sequence of "digits": four zero two zero It is a property of this notation that the "symbol" in the place corresponding to N! is always between 0 and N (inclusive). Where N places in binary notation allow us to express unsigned numbers from 0 to 2^N - 1, the "factorial" notation allows one to express unsigned numbers from 0 to (N+1)! - 1 with N places. The increased overall range is due to the greater range of symbols in the individual positions above the lowest one (which is still limited to 0 or 1). regards, mathtalk-ga```
 ```There is a Google question addressing the random data compression issue here: http://answers.google.com/answers/threadview?id=295380 It points to a good discussion, with proof, of the impossibility of general-purpose guaranteed compression; I include the link to the Google thread in case more good comments surface. The discussion is at http://www.faqs.org/faqs/compression-faq/part1/section-8.html -Haversian```