3 ms·

What does “ compute this as a function of the length of the input encoded in binary” mean? Can someone explain it with the other sample used in the article? Doe

• qsort 5y ago
  You're parsing it wrong. "How quickly can we compute this [this = the solution to the problem], as a function of the length of the input encoded in binary?" i.e. it's just wondering what's the computational complexity. The input can be provided in any base, it makes no difference.
• ogogmad 5y ago
  Whether the input is encoded as binary or decimal doesn't change whether the time complexity is in PSPACE, NP or P. You need some finite alphabet, and then encode the input as a string in this alphabet. The time complexity of an algorithm for SSS is measured by how long it takes (in the worst case) as a function of the length of the input string. As long as you use a positional notation like binary or decimal to encode the integers, the big O of the time complexity will remain the same, and so the exact positional notation doesn't actually matter. The size of the alphabet doesn't matter either. If on the other hand you encode the integers using unary notation, then this can land the problem in P.