Search code examples
algorithmnp-completenp

Is it compulsory that the 'reduction of p‌r‌o‌b‌l‌e‌m be done in polynomial time' for it to be NP complete?

For a problem to be NP complete, it must belong to the class NP and there must be a polynomial time algorithm to reduce it to an NP complete problem .

Now what if we only have an exponential time algorithm for reduction . Will this problem still be called NP-complete ? Or are there no such existing problems?

EDIT : Also please tell me whether there is any such problem and if it exists then to which class does it belong ?

Solution 
  • Are such problems NP-complete?

    No. Proof:

    Let your problem = A.

    Let the NP-complete problem it reduces to in (at least) exponential time = B. "At least" because you can do extra trivial work to get to exponential time, or follow a less-than-optimal approach (to prove that there doesn't exist a more efficient reduction strategy is probably quite difficult, probably in the same ball-park as N != NP, which, to date, hasn't been solved).

    Since B is NP-complete, "every problem in NP is reducible to B in polynomial time".

    If A is in NP then it must be polynomial-time reducible to B. But it isn't, so it isn't in NP.

    Thus it can't be NP-complete.

    Put more simply - any problem in NP needs to be at most as hard as A and it clearly isn't.

    Are there such problems?

    I'm thinking this may be such a problem: (recursive knapsack) (I wouldn't mind a comment or two as to whether it is by someone smart)

    Given a set of items, each with a weight and a value, find a subset with maximum total weight A, and also find the subset within this subset with some maximum total weight C, with the goal to maximize the sum of values of the two subsets.

    To which class does it belong?

    I'm pretty sure there isn't a name specifically for these, but I think many (or all?) of them are NP-hard. Proof: (at least for the above problem, assuming it is such a problem)

    Definition: "A problem H is NP-hard if ... (an NP-complete problem) L can be solved in polynomial time by an oracle machine with an oracle for H".

    Let's assume the above example is such a problem and let it = H. So assume we have an oracle that can solve the above in constant time. But the knapsack problem is simply a special case of the above (C = 0), thus we can solve the knapsack problem in constant time (which is polynomial time) using the oracle.

    Not sure about proving it generically. But any given problem could possibly be solved by reducing the given problem to the above problem or by reducing the problem the given problem reduces to to the knapsack problem.

    EDIT: Oh, it looks like they may indeed have a name, 2-EXPTIME.