REAL late here, but what you're missing is it has to be polynomial time with respect to the size of the problem. Take S = (0, 0, 0, 0), G = (0, 0, 0, 10), M = {(1, 0, 0, 0), (-9, 1, 0, 0), (-9, -9, 1, 0), (-9, -9, -9, 1)}. The solution is ~10,000 steps long. If we add another dimension to this problem, we can make the solution ~100,000 steps long, but only increase the size of the input by couple dozen characters (new number for each vector + one more move vector).
So even though your verification algorithm is linear with the size of the solution, it's (at least) exponential with the size of the input, meaning the problem is not in NP. More pathological construct can push it to ACKERMANN.
(BTW you can do better than O(n log n) for checking the subset: you have to iterate through the list anyway to check you reach the target, so you can test for subsetness of the original set as you go!)
REAL late here, but what you're missing is it has to be polynomial time with respect to the size of the problem. Take S = (0, 0, 0, 0), G = (0, 0, 0, 10), M = {(1, 0, 0, 0), (-9, 1, 0, 0), (-9, -9, 1, 0), (-9, -9, -9, 1)}. The solution is ~10,000 steps long. If we add another dimension to this problem, we can make the solution ~100,000 steps long, but only increase the size of the input by couple dozen characters (new number for each vector + one more move vector).
So even though your verification algorithm is linear with the size of the solution, it's (at least) exponential with the size of the input, meaning the problem is not in NP. More pathological construct can push it to ACKERMANN.
(BTW you can do better than O(n log n) for checking the subset: you have to iterate through the list anyway to check you reach the target, so you can test for subsetness of the original set as you go!)