I'm maybe dense but I think I miss something about the example? You have a list of pairs - surely you can verify in polynomial time that:
a. this is a subset of original set: O(n log n) (sort pairs, then linear scan)
b. It reaches target point: O(n) -(just add the coordinates and check they never get negative along the way)
I'm maybe dense but I think I miss something about the example? You have a list of pairs - surely you can verify in polynomial time that: a. this is a subset of original set: O(n log n) (sort pairs, then linear scan) b. It reaches target point: O(n) -(just add the coordinates and check they never get negative along the way)
what am I missing? Why is this not NP?