3 ms·

The running time is polynomial, and there is some constant c independent of n (or X in your notation) such that the running time is O(n^c). The only "sleight of

The running time is polynomial, and there is some constant c independent of n (or X in your notation) such that the running time is O(n^c). The only "sleight of hand" is that we don't know what this c is. Yet, provably, there is some constant c such that for absolutely no satisfiable input does the program take more than c*n^c steps to halt, where n is the length of the input. Note that not knowing c doesn't mean we can't put an upper bound on c. For example, I believe (but don't quote me on this) that c can be upper bounded by Rayo's number. As, otherwise, I think we can derive a compact first-order expression for an upper bound on Rayo's number, which would be a contradiction. And, although Rayo's number is big, it's ultimately still a constant. But ultimately none of this is necessary to prove that the problem is in P. The mere existence of the constant c independent of n suffices.

deleted 3y ago
[deleted]
Retric 3y ago
Your algorithm is dependent on both n and the existence of a solution so as do right now it isn’t guaranteed to actually have some constant c that works for all n. More pedantically, it’s possible for a polynomial solution to P=NP to exist without it running in polynomial time in python. So no there’s doesn’t necessarily exist a c that works for all n even if there exists a polynomial solution to P=NP.
- CaptainNegative 3y ago
  > More pedantically, it’s possible for a polynomial solution to P=NP to exist without it running in polynomial time in python. That's not true. Any Turing machine can be compiled into a Python program with at most cubic slowdown. More precisely, the number of Python bytecode operations executed will be at most quadratic in the running time p(n) of the TM, with all operation acting on a bounded number of objects of size O(log p(n)) (which for polynomial p() is just O(log n)). One can check Chapter 1 of Arora & Barak's Computational Complexity book for a description of the C/Java analogue of this claim, but it follows from a straightforward simulation argument: literally just hardcode the TM states and transition model, then execute it. The only bit to be careful about is addressing and address sizes growing unbounded, but the max size is only logarithmic in running time (simple proof, I believe this is an exercise in Sipser's book), and that's why we give ourself a cubic buffer.
  - Retric 3y ago
    Actually my concern was running into finite recursion limits, sys.maxsize for arrays, etc. The language does specify that the highest possible limit is platform-dependent and there are functions that must return a number so the limit must exist, be enforced, and be a finite number. But that’s a really pedantic class of issues and the spec has few specific limitations so you could probably avoid any of them but it’s a more complicated problem than what you posted.

deleted 3y ago

[deleted]

Retric 3y ago

Your algorithm is dependent on both n and the existence of a solution so as do right now it isn’t guaranteed to actually have some constant c that works for all n. More pedantically, it’s possible for a polynomial solution to P=NP to exist without it running in polynomial time in python. So no there’s doesn’t necessarily exist a c that works for all n even if there exists a polynomial solution to P=NP.

CaptainNegative 3y ago
> More pedantically, it’s possible for a polynomial solution to P=NP to exist without it running in polynomial time in python. That's not true. Any Turing machine can be compiled into a Python program with at most cubic slowdown. More precisely, the number of Python bytecode operations executed will be at most quadratic in the running time p(n) of the TM, with all operation acting on a bounded number of objects of size O(log p(n)) (which for polynomial p() is just O(log n)). One can check Chapter 1 of Arora & Barak's Computational Complexity book for a description of the C/Java analogue of this claim, but it follows from a straightforward simulation argument: literally just hardcode the TM states and transition model, then execute it. The only bit to be careful about is addressing and address sizes growing unbounded, but the max size is only logarithmic in running time (simple proof, I believe this is an exercise in Sipser's book), and that's why we give ourself a cubic buffer.
- Retric 3y ago
  Actually my concern was running into finite recursion limits, sys.maxsize for arrays, etc. The language does specify that the highest possible limit is platform-dependent and there are functions that must return a number so the limit must exist, be enforced, and be a finite number. But that’s a really pedantic class of issues and the spec has few specific limitations so you could probably avoid any of them but it’s a more complicated problem than what you posted.