- #1
The Number Juggler
- 1
- 0
Hi Physics Forums
Is there a specific technique to measure how smooth a discrete function is?
By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.
For example The Closest String Problem is completely smooth function, since if you change the input string by only one letter, then the distance to the furthest string will change by at most one.
The Traveling Salesman Problem is also smooth, but not completely so. If you change only the order that you visit two cities then the total distance traveled could not change as much as if you altered more. However there could be larger and smaller jumps.
Moving around a grid of random numbers would be completely unsmooth.
I'm sure there must be another word for this phenomena and some research done already. But google is providing anything except "smoothing discrete functions" which is a completely different thing altogether!
Is there a specific technique to measure how smooth a discrete function is?
By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.
For example The Closest String Problem is completely smooth function, since if you change the input string by only one letter, then the distance to the furthest string will change by at most one.
The Traveling Salesman Problem is also smooth, but not completely so. If you change only the order that you visit two cities then the total distance traveled could not change as much as if you altered more. However there could be larger and smaller jumps.
Moving around a grid of random numbers would be completely unsmooth.
I'm sure there must be another word for this phenomena and some research done already. But google is providing anything except "smoothing discrete functions" which is a completely different thing altogether!