Re: basic query regarding NP Complete...


"Simon" <count.numbers@xxxxxx> wrote in message
news:4l2cduFdmbjfU1@xxxxxxxxxxxxxxxxx
Russell Easterly wrote:
"Simon" <count.numbers@xxxxxx> wrote in message

Then I'm missing your point. If I replace "vertex cover" by "independent
set"
you said: "Max Independent Set can be converted into a sorting problem."
So you
are saying P=NP?

Not yet.

For example, you can show that an ordering of vertices
such that the nth vertex in the ordering is the first vertex
that has an edge with a vertex that occurs earlier in the list,
then the graph has an independent set of at least size n-1.

Is there anything to show at all?

One of the many ways of solving Max Independent Set involves
finding a way to order (sort?) the vertices so that the first N vertices
in the list are all connected to vertices that come after N in the list.
My own experience is that this is not a very efficient way to solve
the Max Independent set problem, but it has been extensively
studied because there are analytical ways to do the "sorting".

That's why I was asking what a "sorting problem" is. I know sorting as the
task
of putting elements of a list into an order such that a_i <= a_(i+1) for
all
i=1,...,n-1 according to some total order "<=". In general, NP contains
only
decision problems and sorting is not a decision problem ("Is this list
sortable?" seems to be pretty pointless).

Yes, usually NP refers to decision problems. like, is there a way to order
the vertices into a list such that the first N elements of the list form an
independent set.


What you are specifying for your independent set ordering is not a total
order,
since it is not even a relation defined on the set of vertices at all. It
is
rather a property of a list. So it is not a reduction of independent set
to sorting.

OK.

I assume you are referring to something different when talking about
"sorting
problems" but then I find this a pretty confusing answer to someone who is
trying to understand NP-completeness :-)

The OP referred to sorting problems. I was pointing out that to prove
a sorting problem is NP-Complete one must show that any instance
of an NP-Complete problem can be converted into the sorting problem.

Sorry for any confusion.


Russell
- 2 many 2 count


.

Relevant Pages

  • Re: basic query regarding NP Complete...
    ... Max Vertex Cover can be converted into a sorting problem. ... I should have said Maximum Independent Set. ... let's forget about max vertex cover and look at max independent set. ...
    (comp.theory)
  • Re: basic query regarding NP Complete...
    ... What is a sorting problem and why is it in NP? ... I should have said Maximum Independent Set. ... if you can show such a conversion (in polynomial time) ...
    (comp.theory)