5 ms·

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

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

eesmith 7y 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 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/ http://www.satcompetition.org/ .
- calhoun137 7y ago
  Thanks for this. After much research I have concluded that your reply here is accurate and my previous reply contained either misleading or wrong information. Your comments about space and high-level excution frames are on point imo. Thanks for taking the time to explain your thinking here, I really appreciate it! I only care about the execution time for my research purposes. See this Math SE post where I explain this algorithm as a people type algorithm system. Curious for your thoughts? ___ Imagine there is a party with an infinite number of mathematicians at it, and I walk up to my friend with the following instructions: "every 1 minute, find 1 person at the party who has not been told this message yet, and repeat this message to them" It's clear that after N minutes, provided these instructions are followed exactly, there will be 2^N people who have heard this message. I will now describe an algorithm which can solve the boolean satisfiability in N variables in N minutes. 1 - find 2 people at the party, hand one of them a paper that says "True" and another a paper which says "False" and has a boolean expression on it 2 - tell them these instructions "in 1 minute, find 2 people at the party who have not been told this message yet, and repeat this message to them, give 1 of these people your paper but add True to the list, find a new piece of paper and copy over the list + expression from the paper I gave you, but add False to the list" 3 - after N minutes, whoever has a piece of paper in their hands has to compute the solution of the boolean expression (we are assuming since all the people at the party are mathematicians, they can all check this in less than 30 seconds) and if its solvable they have to shout out "ITS SOLVABLE EVERYONE" Then given any boolean expression involving N variables, I can use this algorithm to solve the boolean satisfiability problem in N minutes and 30 seconds [1] https://math.stackexchange.com/q/3605352/1417 https://math.stackexchange.com/q/3605352/1417
  - eesmith 7y ago
    "in 1 minute, find 2 people at the party who have not been told this message yet" What if they are not able to do so? Let's suppose the party has 1 million people, and you start in the center. At first it's easy to find 2 people. As the instructions spreads out, it gets harder and harder, because the number of new people you can reach within a minute goes from quadratic towards linear. "there will be 2^N people who have heard this message" Big-O complexity assumes an upper bound exists in the amount of compute power available. If the number of processors can grow exponentially to limitless size, then it's outside of the usual N vs. NP - many problems are linear if an unbounded amount of CPU power is available which can scale exponentially.
    - calhoun137 7y ago
      > What if they are not able to do so? Good question! Since you have already corrected one of my mistakes, I don't want to start off by disagreeing lol In my head, this is just a silly word problem, the purpose of which is to show the mathematical theory of computation requires a new axiom Here is a map which describes my idea: Party with infinite number of mathematicians --> theory of computation a mathematician --> Turing Machine getting a new piece of paper --> a new axiom that gives Turing Machines a new self-replication feature According to this new theory of computation which I am trying to invent, and which I have named The Theory of Self Reproducing Machines, it would not be an issue that "because the number of new people you can reach within a minute goes from quadratic towards linear" As a counter example to your idea: consider twitter and the abstract concept of a social network graph where it's quite possible to send messages instantly for all practical purposes Curious for your thoughts
      - eesmith 7y ago
        If you have access to an infinite number of CPUs then every problem can be solved in finite time. This is clearly obvious conclusion (excepting perhaps problems which involve transfinite numbers, in which case you need to pin down which infinity you mean). In the real world, communication is limited to the speed of light. If your message is going out to the "infinite number of mathematicians", then after time T your message reaches 4/3 π (c*T)^3 of space, which is polynomial in time. You therefore cannot contact an exponential number of mathematicians, which is what you would need in order to demonstrate the trivial reduction of an NP problem into P. See https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation for other real-world limitations. You mention "twitter ... where it's quite possible to send messages instantly for all practical purposes." There are fewer than 10 billion people in the world. That's a finite number. Even a quadratic problem remains quadratic if there is a bounded number of compute resources. (Any finite number of people/CPUs will be a problem, even if the entire galaxy were populated by humans and/or computronium) Consider https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numb... with the famous description attributed to Erdős: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. Even with the entire mathematical population of the world working on it, Erdős doesn't think R(6, 6) solvable in reasonable time. Now try solving R(n, n). Can it really be solved in linear time even if the entire world becomes proficient in mathematics?

eesmith 7y 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 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/ http://www.satcompetition.org/ .

calhoun137 7y ago
Thanks for this. After much research I have concluded that your reply here is accurate and my previous reply contained either misleading or wrong information. Your comments about space and high-level excution frames are on point imo. Thanks for taking the time to explain your thinking here, I really appreciate it! I only care about the execution time for my research purposes. See this Math SE post where I explain this algorithm as a people type algorithm system. Curious for your thoughts? ___ Imagine there is a party with an infinite number of mathematicians at it, and I walk up to my friend with the following instructions: "every 1 minute, find 1 person at the party who has not been told this message yet, and repeat this message to them" It's clear that after N minutes, provided these instructions are followed exactly, there will be 2^N people who have heard this message. I will now describe an algorithm which can solve the boolean satisfiability in N variables in N minutes. 1 - find 2 people at the party, hand one of them a paper that says "True" and another a paper which says "False" and has a boolean expression on it 2 - tell them these instructions "in 1 minute, find 2 people at the party who have not been told this message yet, and repeat this message to them, give 1 of these people your paper but add True to the list, find a new piece of paper and copy over the list + expression from the paper I gave you, but add False to the list" 3 - after N minutes, whoever has a piece of paper in their hands has to compute the solution of the boolean expression (we are assuming since all the people at the party are mathematicians, they can all check this in less than 30 seconds) and if its solvable they have to shout out "ITS SOLVABLE EVERYONE" Then given any boolean expression involving N variables, I can use this algorithm to solve the boolean satisfiability problem in N minutes and 30 seconds [1] https://math.stackexchange.com/q/3605352/1417 https://math.stackexchange.com/q/3605352/1417
- eesmith 7y ago
  "in 1 minute, find 2 people at the party who have not been told this message yet" What if they are not able to do so? Let's suppose the party has 1 million people, and you start in the center. At first it's easy to find 2 people. As the instructions spreads out, it gets harder and harder, because the number of new people you can reach within a minute goes from quadratic towards linear. "there will be 2^N people who have heard this message" Big-O complexity assumes an upper bound exists in the amount of compute power available. If the number of processors can grow exponentially to limitless size, then it's outside of the usual N vs. NP - many problems are linear if an unbounded amount of CPU power is available which can scale exponentially.
  - calhoun137 7y ago
    > What if they are not able to do so? Good question! Since you have already corrected one of my mistakes, I don't want to start off by disagreeing lol In my head, this is just a silly word problem, the purpose of which is to show the mathematical theory of computation requires a new axiom Here is a map which describes my idea: Party with infinite number of mathematicians --> theory of computation a mathematician --> Turing Machine getting a new piece of paper --> a new axiom that gives Turing Machines a new self-replication feature According to this new theory of computation which I am trying to invent, and which I have named The Theory of Self Reproducing Machines, it would not be an issue that "because the number of new people you can reach within a minute goes from quadratic towards linear" As a counter example to your idea: consider twitter and the abstract concept of a social network graph where it's quite possible to send messages instantly for all practical purposes Curious for your thoughts
    - eesmith 7y ago
      If you have access to an infinite number of CPUs then every problem can be solved in finite time. This is clearly obvious conclusion (excepting perhaps problems which involve transfinite numbers, in which case you need to pin down which infinity you mean). In the real world, communication is limited to the speed of light. If your message is going out to the "infinite number of mathematicians", then after time T your message reaches 4/3 π (c*T)^3 of space, which is polynomial in time. You therefore cannot contact an exponential number of mathematicians, which is what you would need in order to demonstrate the trivial reduction of an NP problem into P. See https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation for other real-world limitations. You mention "twitter ... where it's quite possible to send messages instantly for all practical purposes." There are fewer than 10 billion people in the world. That's a finite number. Even a quadratic problem remains quadratic if there is a bounded number of compute resources. (Any finite number of people/CPUs will be a problem, even if the entire galaxy were populated by humans and/or computronium) Consider https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numb... with the famous description attributed to Erdős: > Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. Even with the entire mathematical population of the world working on it, Erdős doesn't think R(6, 6) solvable in reasonable time. Now try solving R(n, n). Can it really be solved in linear time even if the entire world becomes proficient in mathematics?