Re: basic query regarding NP Complete...

Russell Easterly wrote:
"Simon" <count.numbers@xxxxxx> wrote in message
news:4l06s3Fe7aitU1@xxxxxxxxxxxxxxxxx
Russell Easterly wrote:
You could use MaxVertex Cover for your NP-Complete problem.
Max Vertex Cover can be converted into a sorting problem.
How, in polynomial time?

I should have said Maximum Independent Set.
Max Vertex Cover is easy to solve.

If max vertex cover asks for a vertex cover with maximum cardinality, then yes,
it is easy :-) But max vertex cover is generally defined in a different way. But
let's forget about max vertex cover and look at max independent set.

And yes, if you can show such a conversion (in polynomial time)
then you can prove P=NP.

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?

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?

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).

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.

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 :-)

Cheers,
Simon
.

Relevant Pages

  • Re: basic query regarding NP Complete...
    ... "Max Independent Set can be converted into a sorting problem." ... then the graph has an independent set of at least size n-1. ... usually NP refers to decision problems. ... of an NP-Complete problem can be converted into the sorting problem. ...
    (comp.theory)
  • RE: group but not sort
    ... i follow your instructions to solve my sorting problem on my group and now it ... the name and the sort value. ... report's record source field list so you can use it to sort in the report. ...
    (microsoft.public.access.reports)
  • RE: ASP DataGrid Sorting
    ... As for the sorting problem you mentioned, I don't think the problem is on ... Retrieving datas from sqlserver via StoreProcedure and the DataAdapter ... Microsoft Online Support ...
    (microsoft.public.dotnet.framework.adonet)
  • Re: LINK WORKSHEETS
    ... > relative formulas have solved the sorting problem only in the actual ... when i sort the original worksheet and the ...
    (microsoft.public.excel.programming)
  • Re: give me some advice
    ... Why do you insist on using a stack for sorting in Pascal? ... Perhaps because his/her instructor asked for a solution to a sorting ... sorting problem written in Pascal and using a stack. ...
    (comp.programming)