VRP is NP hard Can we reduce this problem to the problem tha

VRP is NP hard. Can we reduce this problem to the problem that dealt with splitting a set of integers V = {v1, v2,… , vn} to two different groups that had the same sum.

Solution

Yes, the problem VRP which is NP hard, can be reduced to the problem of set splitting since set splitting is both NP and NP hard, hence the set splitting will be a NP complete problem because it is both NP and NP hard

To prove it is NP

Given a sum, it can be proved in polynomial amount of time that which groups give the same amount of sum, we need to use for loops which will raise the polynomial to the order of x^3 or x^4

To prove it is NP-hard, we can reduce the problem to 3SAT problem and since 3SAT problem is NP hard, hence set splitting is also NP hard

Therefore, the set splitting of integers is NP-Complete