Re: basic query regarding NP Complete...


"Simon" <count.numbers@xxxxxx> wrote in message
news:4l06s3Fe7aitU1@xxxxxxxxxxxxxxxxx
Russell Easterly wrote:
For example. if a. b. and c are sorting algorithms, you will have
^^^^^^^^^^
I assume you meant sorting _problems_?
to show a polynomial method of converting a 3-SAT instance
into a sorting problem.

What is a sorting problem and why is it in NP?

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.

And yes, if you can show such a conversion (in polynomial time)
then you can prove 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.


Russell
- 2 many 2 count


.

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