Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 ?

like image 373
Nikunj Banka Avatar asked Oct 27 '25 07:10

Nikunj Banka


1 Answers

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.

like image 52
Richard Rast Avatar answered Oct 29 '25 05:10

Richard Rast