Algorithm could solve NP Complete problem in P time (opens in new tab)

(medium.com)

3 pointscalhoun1376y ago4 comments

4 comments

4 comments · 2 top-level

You seem to have been quite adamant in your recent posting history that this is a major breakthrough https://news.ycombinator.com/submitted?id=calhoun137 but a lot of people don't seem to be of the same opinion.

eesmith6y ago

Indeed, calhoun137 appears to repeat a problem that I and another have pointed out earlier. Quoting from this link:

> The basic idea is to make use of a practically infinite amount of computer power which grows exponentially in time.

The speed of light means computer power can only grow to cubic power - 4/3 π (c T)³, to be precise.

If T is small then exponential growth may dominate, but as T continues to grow, there's no getting around the speed of light limitation even in a universe made of uniform computronium.

calhoun137OP6y ago

I agree with everything eesmith has said to me so far in our discussion. I apologize for not communicating how seriously I take all of his replies to me, or how helpful this is for my research

I am working on a very fun project making a 3d computer game in unity, its got a beautiful user interface where you can play with the parameters of a single self reproducing machine and it lands on a fake planet and you can do (fake/simulated) physics experiments with imaginary "programmable self-replicating 3d printers" and its all running a physics simulation of what a real planet might be like, but you can adjust these parameters in the game too.

It's inspired by John Conway's The Game of Life. It's quite fun! I believe I have discovered an infinite family of new 3-dimensional self reproducing machines, and own the website selfreproducingmachines.com for the purpose of releasing this game as a free open source program when its finished

Thank you so much for keeping me in line and helping me with these ideas. It means so much to me.

I did not post on this website so heavily because I didn't want to be mercilessly dragged by people like eesmith who know much more about this than me

I have many questions about a "fake math" theory I made up, where its kind of like theoretical physics, but its about the mathematical theory of life, evolution, dna; but from first principles

I have discovered the existence of mathematical laws which relate the properties of the environment, and the local encoding of a single self reproducing programmable machine, and the way these types of systems tend to evolve

Clearly, I am very likely making a large number of conceptual mistakes at this time. This is the purpose for my posting these articles on here. Any advice is most welcome

xkapastel6y ago

> As a model for computation, P systems offer the attractive possibility of solving NP-complete problems in less-than exponential time. Some P system variants are known to be capable of solving the SAT (boolean satisfiability) problem in linear time and, owing to all NP-complete problems being equivalent, this capability then applies to all such problems. As there is no current method of directly implementing a P system in its own right, their functionality is instead emulated and therefore solving NP-complete problems in linear time remains theoretical. However, it has also been proven that any deterministic P system may be simulated on a Turing Machine in polynomial time.

https://en.wikipedia.org/wiki/P_system

This is not as interesting as it sounds, since you're just trading exponential time for exponential space. It's still not practical or very interesting.

j / k navigate · click thread line to collapse