Is this a correct understanding of proving something is NP Complete?

Question

As I understand it there are two steps to proving that a problem is NP complete:

1. Give an algorithm that can verify a solution to the problem in polynomial time. That is, an algorithm whose input is a proposed solution to the problem and whose output is either "yes" or "no" based on whether the input is a valid solution to the problem.

2. Prove the problem is NP hard - eg, assume you have an oracle that can compute another known NP complete problem in one step. Using that, write an algorithm that solves this problem in polynomial time.

For example, suppose we want to prove that the following problem is NP Complete:

Given a set of integers, S, is it possible to isolate a subset of elements, S', such that the sum of the elements in S' is exactly equal to the sum of the remaining elements in S that are not included in S'?

Step 1: Verification algorithm

Verify_HalfSubset(Set S, Solution sol):
    accum = 0
    for each element i in sol:
        accum+=i
        linear search for an element with the same value as i in S.
        if found, delete it from s, if not found, return false
    end for
    accum2 = 0
    for each element i in S:
        accum2+=i
    end for
    if accum==accum2 return true, else return false

Clearly this runs in polynomial time: The first for loop runs in O(nm) and the second runs in O(n).

Step 2: Reduction

Assume we have an oracle O(Set S, int I) that computes the subset sum problem in a single step (that is, is there a subset of elements in S that sum up to I)?

Then, we can write a polynomial time algorithm that computes our half-subset problem:

HalfSubset(Set S):
    accum = 0
    for each s in S:
        accum+=S
    end for
    if(accum%2==1) 
    // this question forbids "splitting" values to non-integral parts
        return NO_ANSWER
    end if
    half1 = O(S, accum/2)
    if(half1 == NO_ANSWER)
        return NO_ANSWER
    end if
    for each i in half1:
        linear search for an element with the same value as half1[i] in S
        delete it from S.
    end for
    half2 = S
    return (half1 and half2)

Can someone please tell me if I've made any mistakes in this process? This is the one question on my final exam review that I'm not entirely sure I understand completely.

Answer 1

The second portion of your answer is a bit off. What you are saying in step two is that you can reduce this problem to a known NP-complete problem in polynomial time. That is, you are saying that this problem is at most as hard as the NP-complete problem.

What you want to say is that the NP-complete problem can be reduced to your example problem in polynomial time. This would show that, if you could solve this problem in polynomial time, then you could also solve the NP-complete problem in polynomial time, proving that your example problem is NP-complete.

Answer 2

No, this is incorrect. You could set up a situation where you use the NP-Complete oracle to solve the problem, yet still have the problem itself be in P.

What you have to do is show that you can reduce another NP-Complete problem to your problem. That is, provide a polynomial-time algorithm to transform any instance of a particular NP-Complete problem to an instance of your problem such that a solution of your (transformed) problem is also a solution to the given NP-Complete problem. This shows that if you can solve your problem, then you can also solve any NP-Complete problem, meaning your problem is at least as hard as any other NP-Complete problem.