| ▲ | bjornsing 6 days ago | ||||||||||||||||
It doesn’t need to be linear though. Polynomial is enough. But I guess it can be proven that the shortest possible sequence grows faster than polynomial. | |||||||||||||||||
| ▲ | hwayne 5 days ago | parent | next [-] | ||||||||||||||||
Proving it's nonpolynomial is pretty easy: just make the goal vector `(10, 10, 10)` and the displacement vectors `{(1, 0, 0), (-10, 1, 0), (-10, -10, 1)}`. It takes ~1000 steps to reach the goal, and if we add one more dimension we need 10x more steps. So it grows, at least, exponentially. Back in 1970ish someone found a problem that's at least double-exponential, proving it was 2-EXPTIME-hard. It was conjectured to be 2-EXPTIME-complete for the longest time, but turned out to be significantly harder. | |||||||||||||||||
| ▲ | trixthethird 6 days ago | parent | prev [-] | ||||||||||||||||
I think they proved it grows with Ackermann function. | |||||||||||||||||
| |||||||||||||||||