NP optimization problems (definition)

398 views Asked by At

I'm trying to understand the definition of NPO.

I read the definition here : http://www.nada.kth.se/~viggo/wwwcompendium/node2.html

If we consider trying to find a minimal vertice cover, what is I,sol(x) and m ? (goal is min)

1

There are 1 answers

0
Anders Lindahl On BEST ANSWER

Judging by the link you posted I think this is the interpretation for minimal vertex cover:

  • I: The set of all graphs.
  • sol(x): The set of possible solutions to a graph x ∈ I, that is all subsets of vertices that cover all edges.
  • m(x,y): The value of solution y to instance x. In the vertex cover case the number of vertices in the set.