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

Here the main point is the size of the cluster.

If the cluster is of finite size, and everyone is in P, then a universal
algorithm exists by calling them one by one until an answer is obtained.

If the cluster is of infinite size, how to store and use them?

Thomas Li


"feeldead" <feeldead@xxxxxxxxx> wrote in message
news:1127391886.721145.90080@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> I have almost the same wondering. NPC makes sense only regarding a
> class of instances belonging to a certain problem and we can't say that
> an instance is NPC according current complexity theory. My question is
> for a certain instance, for example TSP with 10000 nodes, how many
> years are needed to resolve it, using computer, mathematics, whatever?
> If we can resolve it in a resonabe time limit, supposing 1000 years,
> which is far more less than the time needed for a computer program to
> resolve the general TSP problem, why can't we find solution for another
> TSP instance? If we don't expect to resolve all the instances of TSP
> with a single program, but search for a cluster of algorithms for
> resolve all the instances, with every algorithm aiming to one or
> several instances. Can we resolve the NPC problem in this sense?
>


.

Relevant Pages

  • Re: Gene expression: Is Natural Selection a tautology?
    ... the Gaia selection force selects. ... cluster of rocks can't imply anything, ... battle between the good and bad algorithm, the strong algorithm won, ... Scientists mostly don't care that much about precise definitions. ...
    (talk.origins)
  • Re: How to rearrange text fields in sed?
    ... bugs where the expression didn't resolve to true in corner ... but at first sight it looks like it's an assignment. ... least what the algorithm is. ... newline, append " " otherwise. ...
    (comp.unix.questions)
  • Re: Sequence clustering - order of the model
    ... The research paper for the algorithm is here: ... The algorithm is essentially a mixture of markov and cluster models. ... The input sequence is used to determine the cluster probability of the ...
    (microsoft.public.sqlserver.datamining)
  • Re: Complexity of a specific kind of instances of a NP-complete problem
    ... > |If we don't expect to resolve all the instances of TSP ... > There's a kind of universal searching algorithm known as ... > in Otime, then Levin search does too, but with the constant ... > fraction of its time simulating this other algorithm. ...
    (comp.theory)
  • Re: problem with arp who-has
    ... > I am running a linux cluster on an isolated network ... > and I am having a network issue that I cannot resolve. ... > switches are at fault. ... Are the nodes' ARP tables loaded ...
    (comp.os.linux.networking)