I don't see how counting steps done on paper with pencil is subject to any applicable physics, so I see no obvious violation of the laws of physics. (NKS?)
What kind of violation are you expecting? Computability is an abstract concept, and computational complexity is used to define the "hardness" of a problem in terms of how it's scaling asymptotically with its input size. This of course will correspond to a physical time, since each step in the computation can be assumed to take some finite amount of time. However, it is not important how much time each step takes, what's important is how this number behave in the limit of large input size. If the complexity is exponential, then no matter how small the time step is, eventually (after a relatively small number of steps), you should still wait a huge amount of time until the computation comes to an end.
Vlad,
Thank you. You are correct. My question should read:
In P v NP, what happens if we define time and steps to be equivalent?
Then it only holds true for RISC architectures not CISC architectures where a step could take more than one cycle. The current formulation works for either as easily because you simply count the cycles for each step to get the time taken. If all the steps take 1 cycle, then they are equivalent, if some steps slip, or extend cycles, then they aren't.
The current formulation also deals well with high level languages where the number of cycles for each line of code is variable depending on the compiler/interpreter.
- Badges
- Science topic
- Similar topics
- Theoretical Physics
- Time