3 ms·

Algorithm could solve NP Complete problem in P time

3 points by calhoun137 7y ago

xkapastel 7y 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 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.
bryanrasmussen 7y ago
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 https://news.ycombinator.com/submitted?id=calhoun137 but a lot of people don't seem to be of the same opinion.
- eesmith 7y 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.
  - calhoun137 7y 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

3 points by calhoun137 7y 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 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.

bryanrasmussen 7y ago

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 https://news.ycombinator.com/submitted?id=calhoun137 but a lot of people don't seem to be of the same opinion.

eesmith 7y 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.
- calhoun137 7y 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