Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

P=NP (preferrably MathTalk)

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

• Answer:

  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