Hello,

If there is a decision problem, which is NP-complete,

question: can the problem A be done in k steps?

then, is the following problem also np-complete

question: can the problem A be done in k+c steps, where c is some fixed constant?

Basically, I would like to know if a problem is NP-complete, then whether finding a solution which is a constant away from the optimal is also NP-complete or not?

Thanks