My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
February 20th, 2014, 02:19 PM   #1
Senior Member
 
Joined: Jan 2013

Posts: 209
Thanks: 3

P equals NP if any hashlife scales for Clique on the board

This is exactly the kind of thing you'd expect if P equals NP.

http://en.wikipedia.org/wiki/Hashlife
Quote:
The 6,366,548,773,467,669,985,195,496,000 (6 octillionth) generation of a very complicated Game of Life pattern computed in less than 30 seconds on an Intel Core Duo 2GHz CPU using hashlife in Golly. Computed by detecting a repeating cycle in the pattern, and skipping ahead to any requested generation.
Quote:
This itself leads to significant improvements in resource requirements; for example a generation of the various breeders and spacefillers, which grow at polynomial speeds, can be evaluated in Hashlife using logarithmic space and time.
Polynomial becomes log? Then what does polynomial^n become? e^log(p) = p.

I imagine if P equals NP, then there is such a thing as an average of subconstant time, as in simulating a particle being many places at once for the cost of simulating a single particle.

Hashlife means any algorithm or equation for generating a hashcode of a subset of the bits on the 2d game board of Conways Game Of Life.

Majority Color is where new cells are the color of the majority of the 3 cells which created them, and this can only work for 2 possible colors since more could have ties. Majority color blobs together like a majority of pieces surrounding a minority, capturing the minority in the game Go.

On the other hand, Minority Color (the exact opposite each time a color is chosen, while other colors continue existing as live cells) looks more like a 1-way function, if there is such a thing, jumping around as if it were random. Minority is like Xor/Nand. Majority is like And/Or.

Both majority and minority color act symmetricly regardless of how you mirror a piece of the game board. They are dimensionless logic.

It is said that P does not equal NP because you have to choose somewhere to start and from there continue doing things in some order, but thats exactly what does not happen in "dimensionless logic".

The next questions we should ask are...

What variations of hashlife are there? Do they use majority color and/or minority color? Do they use dimensionless logic (I read they do)? Do they always scale up regardless of whats on the life board, or is it only for the things not specificly designed to be hard?

As an example of a hard Clique problem, create a graph which has a large number of cliques of size N that overlap eachother on many of their nodes as nearly a continuous manifold with cliques overlapping other cliques when they are near on its surface, and ask... Does this have a clique of size N+1? Since the manifold can be high dimensional and closed, it will have your P equals NP algorithm running around in circles for an exponential time, unless you can look at them all together.

As further motivation to those interested in pursuing possible research paths, consider how much faster we could simulate protein folding, economic flows, and many other scientific and entertainment computations, if it only cost linearly more computing to double the amount of work done, and we get to keep doubling without limit? I dont want to get rich, I want everyone to get filthy rich for less effort than doing the one thing.


-----

The dimensionless logic of majority color and minority color can work anywhere theres an odd number of bit vars, so it will also work in Rule 110 which is the simplest general computing math. Someone claims to have built a Rule 110 emulator as a picture you would paint into the Life game board, and it will run Rule 110...
http://pentadecathlon.com/lifenews/2005 ... _cell.html

Then we could build a Life emulator in Rule 110, so we have the 2 kinds of math able to simulate eachother recursively to any depth, and can use some variety of hashlife in each of them.

Theres so many possibilities, but all we need is 1 and the world will change in a way most cant imagine and others can only imagine a few steps into. We may need to add some unimagined possibilities to http://en.wikipedia.org/wiki/Kardashev_scale because we would no longer be impressed by anyone who can move a black hole or synthesize arbitrary materials and forms, in only 3 dimensions at a time.

Watch the video...
Life running inside of Life.... http://www.youtube.com/watch?v=xP5-iIeKXE8 Its like being in the matrix, running another matrix, and you have no idea if you're at the top or bottom or if direction has any meaning.
BenFRayfield is offline  
 
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
board, clique, equals, hashlife, scales



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to calculate max/min scales on a scatter plot expertalmost Algebra 8 March 26th, 2014 02:49 PM
Find the Mafia!: an iOS game on the maximum clique problem experiware Applied Math 1 June 17th, 2013 12:52 PM
2d Clique Crystal is Turing Complete by simulating Rule 110 BenFRayfield Applied Math 0 May 7th, 2013 05:00 PM
P equals NP - Max Clique using n dim distance constraints BenFRayfield Applied Math 5 May 4th, 2013 11:45 AM
Superfluid Gaussian Clique Timeless Soliton Field BenFRayfield Advanced Statistics 0 April 11th, 2013 02:42 PM





Copyright © 2017 My Math Forum. All rights reserved.