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?

Question

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 ?

Answer 1

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.

Answer 2

It can only be consider NP-complete if other NP problems can be reduced to it in polynomial time. The reason this is a useful definition is that if we find a polynomial time algorithm for one, it automatically gives one for all NP problems. If we allowed an exponential time reduction, but found a polynomial time solution to the reduced problem, that wouldn't actually help us solve the one we reduced it to.

Hope this helps.

Answer 3

Completeness in complexity theory is always defined for a particular kind of reductions, sometimes known from the context and thus not explicitly mentioned. The famous class of NP-complete problems is defined as complete for polynomial time reductions, for reasons given in the answer by Richard Rast.

You can define class of NP-complete problems for EXPTIME reductions, but this class is not very interesting. If the reduction is allowed exponential time, then it can fully solve the original problem and produce a trivial instance of the target problem. This means every problem in NP is reducible to every other problem by such type of reductions, so every problem in NP is NP-complete for exponential time reductions.

Short version: reductions are only interesting if they are (at least supposedly) weaker than the class of problems being reduced.

Answer 4

As has been remarked a lot earlier, the direction of your question is wrong. A problem A is NP-complete by definition if every problem B in NP can be reduced in polynomial time to problem A. So I assume your question is whether that reduction must be in polynomial and not exponential time.

If you allowed exponential time reduction: Take the following decision problem X: "Is the input YES?" That's almost the simplest possible decision problem. The answer is YES if the input is YES, the answer is NO if the input is not YES. But every problem in NP can be reduced to problem X in exponential time. Surely we don't want to call problem X "NP-complete". Therefore, exponential time reduction is not allowed because allowing it would make the term "NP-complete" totally meaningless.