Determining the minimum distortion to an image such that it will fool a classifier is itself an NP-hard problem for ReLu activated neural networks [1]}, [2]} and tree ensemble classifiers [3]}. Even approximating the minimum distortion for ReLu activated neural networks is NP-hard [4]}. Recent heuristics such as Boundary attack [5]} and HopSkipJump attack [6]} attempt to find an adversarial example with the minimum distance to the clean correctly classified version.
