3 ms·
The claims of "solve NP problems in linear time" appear to come with a giant gotcha: they involve allowing the number of membranes to grow exponentially with th
by al2o3cr 4y ago
The claims of "solve NP problems in linear time" appear to come with a giant gotcha: they involve allowing the number of membranes to grow exponentially with the problem size! For instance, see:
https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/102paun.pdf https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researc...
This seems like a huge problem for any electronic representation, since most any computational approach will deliver "super-Turing" results if you allow the machine to grow faster than the problem...