5 ms·

There is no general solution to deciding whether a program is O(n^k).[1] So either your static analysis won't know the answer for some programs or report a wron

There is no general solution to deciding whether a program is O(n^k).[1] So either your static analysis won't know the answer for some programs or report a wrong bound, or report a ridiculous overestimate. [1] https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no https://cstheory.stackexchange.com/questions/5004/are-runtim...

Jyaif 6y ago
Can you point me towards some source code where a human can't find the algorithmic complexity?
- adrianN 6y ago
  It's not hard to implement the construction in the proof. Generally you'll encounter problems in the wild in any interpreter. Similarly you can encode many open mathematical problems into simple programs where finding runtime bounds is equal to solving the problem. The Collatz Conjecture for example.
- namibj 6y ago
  Once you leave primitive recursive functions[0], reasoning quickly becomes very non-trivial. [0]: https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function
- smallnamespace 6y ago
  Humans can't tell you whether this program will run forever on any particular (positive integer) input, or whether all inputs terminate. def collatz(n): while n != 1: print(n) if n % 2 == 0: n = n // 2 else: n = n * 3 + 1 print(1)
  - kibibyte 6y ago
    I think your indentation needs to be adjusted? Like so: def collatz(n): while n != 1: print(n) if n % 2 == 0: n = n // 2 else: n = n * 3 + 1 print(1) Otherwise, n = 1 terminates, and n != 1 gets stuck looping at lines 2-3.
  - Jyaif 6y ago
    Thank you!
rcxdude 6y ago
So? Static analysis doesn't need to always produce an answer, only produce an answer most of the time. The question isn't whether you can do it in general for all inputs (this is not possible for basically anything you would want to know), it's whether you can do it enough of the time on the kind of code which people actually write.

Jyaif 6y ago

Can you point me towards some source code where a human can't find the algorithmic complexity?

adrianN 6y ago
It's not hard to implement the construction in the proof. Generally you'll encounter problems in the wild in any interpreter. Similarly you can encode many open mathematical problems into simple programs where finding runtime bounds is equal to solving the problem. The Collatz Conjecture for example.
namibj 6y ago
Once you leave primitive recursive functions[0], reasoning quickly becomes very non-trivial. [0]: https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function
smallnamespace 6y ago
Humans can't tell you whether this program will run forever on any particular (positive integer) input, or whether all inputs terminate. def collatz(n): while n != 1: print(n) if n % 2 == 0: n = n // 2 else: n = n * 3 + 1 print(1)
- kibibyte 6y ago
  I think your indentation needs to be adjusted? Like so: def collatz(n): while n != 1: print(n) if n % 2 == 0: n = n // 2 else: n = n * 3 + 1 print(1) Otherwise, n = 1 terminates, and n != 1 gets stuck looping at lines 2-3.
- Jyaif 6y ago
  Thank you!

rcxdude 6y ago

So? Static analysis doesn't need to always produce an answer, only produce an answer most of the time. The question isn't whether you can do it in general for all inputs (this is not possible for basically anything you would want to know), it's whether you can do it enough of the time on the kind of code which people actually write.