r/mathriddles • u/Tc14Hd • 9h ago
Medium Just assume that everything is constant
(This is a theoretical computer science puzzle. I hope that's allowed here.)
When we analyze the complexity of algorithms, we usually assume that integer operations run in constant time. As long as the numbers don't explode in size, this is a reasonable assumption given the architecture of modern computers. But have you ever wondered what would happen if there was no restriction on the size of the numbers?
Consider a model of computation where basic integer operations (including arithmetic, bitwise and comparison operations) always run in constant time, regardless of the sizes of their operands. Prove that every problem in NP can be solved in polynomial time under this model.
Hint: It's enough to provide a polynomial algorithm for one particular NP-hard problem. 3-SAT seems to be quite convenient here, but others work too.