Re: Question about the minesweeper consistency problem (NP-complete problems)


Proginoskes wrote:
>
> There's also a result that says that every NP-complete problem has an
> algorithm that solves the problem and whose EXPECTED running time is
> polynomial. So, for the NP-complete problems, there are a large
number
> which can be solved quickly and a very few which are pathological.
>

I'm not sure what you mean here. Usually, 'expected' running time is
used for randomized algorithms: for every instance, there is an
expected running time, and the expected running time of the algorithm
is the worst-case time of these.

However, even if you mean: the expected running time of this algorithm
on a random instance of length n, I do not believe this. While there
are some NP-complete problems for which most instances are easy (I
think 3-coloring is such a problem), I believe that for many such
problems it is thought that most instances are hard. Of course I could
be mistaken.

Could you state the theorem you refer to precisely, and give a
reference? I assume there is some subtlety in the definition of the
distribution on the instances.


Lasse

.

Relevant Pages

  • Re: one sentence proof of 4 Color Mapping Problem; direct method
    ... for you to determine whether you can color this map with THREE ... So an algorithm for this machine would look ... building the algorithm in P to solve the NP-complete problems, ... Perhaps the equivalency is the idea that Eucl geom is what is ...
    (sci.math)
  • Re: What big scientific changes will ...
    ... poliaminal time, a non poliaminal algo is no solution for me. ... NP-complete problems are not as hard as they seem. ... If such an algorithm existed, ... algorithm exists and in 1882 this was proven by von Lindemann. ...
    (sci.math)
  • Re: An approach to proving P != NP
    ... This includes all NP-complete problems and all problems in P. ... verified by an algorithm in NP0, NP1 problems. ... Eeee - any of NP problems can have solution verified by some algorithm? ...
    (comp.theory)
  • Re: Question about the minesweeper consistency problem (NP-complete problems)
    ... there's an algorithm for an NP-complete problem ... the average running time is polynomial in n. ... > which reduce to 3-SAT and SAT (the original NP-complete problems). ... But a reduction does not preserve the exact size. ...
    (sci.math)
  • Re: deques, deques, and dequeues
    ... if you will, of the algorithm. ... "The expected running time is O..." ... say any undergraduate taking an algorithms course (especially ... This one didn't when he was an undergraduate. ...
    (rec.games.roguelike.development)