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 ?
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With