Is it necessary that "the problem can be reduced in polynomial time" to be complete?
For a problem to be NP complete, it must be NP and there must be a polynomial time algorithm to reduce it to an NP complete problem.
Now if we only have an exponential time algorithm for reduction. Will this issue still be called NP-complete? Or are there no such existing problems?
EDIT: Also tell me if there is such a problem and does it exist then what class does it belong to?
source to share
Are such problems NP-complete?
Not. Evidence:
Let your problem = A.
Let the NP-complete problem reduce to (at least) exponential time = B. "At least" because you can do some extra trivial work to get to exponential time, or follow a less optimal approach (to prove that there is no a more efficient reduction strategy is probably quite difficult, perhaps in the same ball park as N! = NP, which still hasn't been solved).
Since B is NP-complete, every problem in NP reduces to B in polynomial time .
If A is in NP, then it must be polynomial-time reducible to B. But it is not, so it is not in NP.
Thus, it cannot be NP-complete.
Simply put, any problem in NP must be no worse than A, and this is clearly not the case.
Are there such problems?
I think this could be a problem like this: (recursive knapsack ) (I wouldn't want a comment or two as to whether this is someone smart)
Given a set of items, each with a weight and value, find the subset with the maximum total weight A, and also find the subset within that subset with some maximum total weight C in order to maximize the sum of the values from the two subsets.
To which class does it belong?
I'm sure there is no name for them, but I think many (or all?) Of them are NP-hard . Proof: (at least for the above problem, assuming it's such a problem)
Definition: "Problem H is NP-hard if ... (NP-complete problem) L can be solved in polynomial time by an oracle machine with oracle for H" .
Suppose the above example is such a problem and let it = H. So, suppose we have an oracle that can solve the above in constant time. But the knapsack problem is just a special case of the above (C = 0), so we can solve the knapsack problem in constant time (that's polynomial time) with an oracle. In the meantime, there is no need to know about it. ”
Not sure to prove it in general. But any given problem could be solved by reducing the given problem to the indicated problem, or by reducing the problem with which this problem is reduced to the backpack problem.
EDIT: Oh, it looks like they might actually have a name, 2-EXPTIME .
source to share
It can only be 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 the exponential decrease in time, but found a solution in polynomial time for the given problem, it would not actually help us solve the one that we reduced it.
Hope it helps.
source to share
The completeness of complexity theory is always defined for a certain kind of abbreviation, sometimes known from the context and thus not explicitly mentioned. The well-known class of NP-complete problems is defined as complete for polynomial time cancellation for reasons given in Richard Rast's answer.
You can define a class of NP-complete problems for EXPTIME abbreviations, but this class isn't very interesting. If contraction is allowed exponential time, then it can completely solve the original problem and create a trivial instance of the target problem. This means that every problem in NP is reducible to every other problem using this type of cancellation, so every problem is NP NP-complete for exponential cancellation of time.
Short version: abbreviations are only interesting if they are (at least presumably) weaker than the class of problems.
source to share
As noted much earlier, the direction of your question is wrong. Problem A is NP-complete by definition if every problem B in NP can be reduced in polynomial time to problem A. So I guess your question is whether this reduction should be in polynomial rather than exponential time.
If you have allowed exponential shortening of time: Take the following problem solving X: "Is the input YES?" This is almost the simplest solution problem. The answer is YES if the input signal is YES, the answer is NO if the input is not YES. But every problem in NP reduces to problem X in exponential time. Of course, we don't want to call Problem X "NP-complete". Therefore, exponential shortening of time is not allowed, as it makes the term "NP-complete" completely meaningless.
source to share