Algorithm solves NP-Complete Problems in P time

https://medium.com/@calhoun137/this-algorithm-solves-np-complete-problems-in-p-time-90f6fa938521

by calhoun137 • 6 years ago

2 13 6 years ago

eesmith6• 6 years ago

- each timestep, self-replicate the most recently made objects twice each, and append true, false to the array
- after N timesteps, every possible set of values for the boolean variables will be in memory

Creating that takes O(2^N) time, hence this algorithm is not polynomial. It's especially not linear, as claimed.

calhoun1377• 6 years ago

I disagree, did you run debugging tools to check how many frames this code takes to execute? On what basis are you claiming it takes O(2^N)? You just are just asserting that, but my code is running in time O(N) according to the debugger so im not sure why you are claiming that

eesmith6• 6 years ago

"In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows" - https://en.wikipedia.org/wiki/Big_O_notation

It does not refer to the number of high-level execution frames, which appears to be what you measured.

Consider that in Python:

   a = []
   for i in range(500_000):
     a.append(i)
   a.reverse()

takes about 0.1 seconds, while

   a = []
   for i in range(500_000):
     a.insert(0, i)

takes about a minute, to produce the same result. That's a factor of 600, even though the first one actually executes more Python code.

This is because the first uses an amortized O(N) method, while the second uses an O(N^2) method.

Hence, you need to measure run time, not the number of frames.

I don't need to try it out because you wrote "every possible set of values for the boolean variables will be in memory", which requires O(2^N) values for the worst case, which require O(2^N) for the CPU to touch each memory cell.

Also, try something with 10,000+ variables. Or one of the benchmark test sets from http://www.satcompetition.org/ .

Algorithm solves NP-Complete Problems in P time

Related Stories