Results 1 to 2 of 2

Thread: Is this NP-complete

  1. #1 Is this NP-complete 
    New Member
    Join Date
    Mar 2010

    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?


    Reply With Quote  


  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    You're asking two different questions there.

    The decision problem "can A be done in k steps" doesn't look for an actual solution, and if you knew (k+c) and c, you'd know k, so for a fixed c, yes, it'd still be NP complete.

    The question of "find a solution that is within some error of optimal" is not a decision problem, so it can't be NP complete no matter what error you use. Such problems can be in P though as there are numerous algorithms that give such answers to otherwise difficult questions.

    Reply With Quote  

Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts