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


Keith Ramsay wrote:
> feeldead wrote:
> |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?
>
> There's a kind of universal searching algorithm known as
> "Levin search" that divides up its time among an ever-growing
> collection of algorithms. If there is an algorithm that finds
> a solution to some set of positive instances of the problem,
> in O(f) time, then Levin search does too, but with the constant
> in the "O" being in general astronomically large. That's
> because eventually Levin search will be spending some small
> fraction of its time simulating this other algorithm. If there
> is an algorithm requiring n bits to specify, that takes m steps
> to find a solution, Levin search in one usual form takes
> something like 2^n*m steps.

Nice explanation. I've always wondered in what way Levin's search
is an improvement over the traditional method of using 10^6 monkeys
and typewriters to reproduce Shakespeare.

Cheers,

--
Eray

.

Relevant Pages

  • 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: Complexity of a specific kind of instances of a NP-complete problem
    ... Here the main point is the size of the cluster. ... algorithm exists by calling them one by one until an answer is obtained. ... > an instance is NPC according current complexity theory. ... > years are needed to resolve it, using computer, mathematics, whatever? ...
    (comp.theory)
  • 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 ... "Levin search" that divides up its time among an ever-growing ... purposes, theoretically especially, this Levin complexity serves ...
    (comp.theory)
  • Re: Complexity of a specific kind of instances of a NP-complete problem
    ... nodes, how many years are needed to resolve it, using computer, ... the best algorithm on a modern computer could resolve such a ... with a single program, but search for a cluster of algorithms for ... Then you would have one big program that solves the NPC problem ...
    (comp.theory)