Re: Complexity of a specific kind of instances of a NP-complete problem

Thanks for the answer. But how about if for each problem size n, there
is one different instance. I think it is impossible to solve all
instances (with infinite many n) by writing all solutions in the code
of the algorithm.

In fact, all the articles (except about instance complexity) I read
about P and NP only consider the problems which has many instances for
one problem size n. What happen to the problems which has one or two
instances for each n? It is not possible to reduce a known NP-complete
problem to this kind of problems due to the obvious different
structures. Any technique to discuss/prove the hardness of this kind of
problems?

Thanks again.

.

Relevant Pages

  • Re: Michelle Wei Someday she will learn
    ... Perhaps a "stress-reduction" technique that Leadbetter teaches? ... Lopez Gomez ... Prev by Date: ...
    (rec.sport.golf)
  • Re: WAYLTL September 2005
    ... - Russ (not Martha) ... Prev by Date: ...
    (rec.music.classical.recordings)
  • Re: Pocket PC Network Connection Error
    ... In your past posts you have also used this "Please send me the solution ... technique on previous problems with your webservice. ... mood to help people who don't help themselves first. ... Prev by Date: ...
    (microsoft.public.pocketpc.developer)
  • Re: Cowboy song revenge
    ... Priceless! ... Looks like a technique he picked up from Mike Gordon. ... Prev by Date: ...
    (rec.music.gdead)
  • Re: I would like to discuss this
    ... >>> I will use Joel's technique ... >> Gee, would it be so hard to just begin a new conversation about the ... Prev by Date: ...
    (sci.med.dentistry)