5
$\begingroup$

I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin NP. But I can't seem to wrap my head around this.

Why is this so?

$\endgroup$
7
$\begingroup$

What is normally meant in cases like this is

there is a simple, obvious algorithm which demonstrates that the problem is in $\mathcal{NP}$,

with an implicit

but we don't have enough space, can't be bothered, or don't want to bore the reader by including it.

Whether it really is trivial is a trickier thing (but often it really is).

Before returning to the Steiner Tree problem, recall the two common definitions of $\mathcal{NP}$ membership:

  1. A problem is in $\mathcal{NP}$ if, given the input and a solution, we can check that the solution is correct in deterministic polynomial time, or
  2. given the input, we can compute the solution in non-deterministic polynomial time.

So for the Steiner Tree problem (remember we only concern ourselves with the decision versions), they are saying that at least one of the following is true:

  1. Given a graph, a set of required points, a value $k$ and a tree (the alleged solution), we can easily check that the tree is a Steiner tree of value at most $k$, or

  2. Given a graph, a set of required points and a value $k$, we can easily compute a Steiner tree of value at most $k$ if we can make some really good guesses.

Hopefully in this case both of these should be more obviously true. In the first case, we need only check that the tree1 contains the required points, and the total weight of the tree is at most $k$. In the second, we can use the magic of non-determinism to guess which edges are in the tree, then check that it's okay as in the first case.

The only further requirement is that these procedures be computable in polynomial time, but in both cases we at most need to look at each edge of the graph and each vertex of the graph once(-ish) (if we have sensible data structures to store the graph and tree), so even without being too precise, we can see that they can both be done in polynomial time.

Footnotes.

  1. As A. Schulz notes in the comments, there is an additional issue of ensuring that the witness (the solution handed to us) has an encoded length bounded by a polynomial in the size of the original input. This may be easy to see, but as A. Schulz also notes, if we're talking about the Geometric Steiner Tree problem, then we might have to make an additional argument about how we encode the geometry of the tree - not necessarily too complicated, but still important. If we're talking about the Steiner Tree Problem in Graphs, then it's more straightforward (as we don't have to worry about the geometry), and perhaps something you can gloss over. Nonetheless it is important to be careful :).
$\endgroup$
  • $\begingroup$ that definitely cleared up the confusion! $\endgroup$ – MMP Dec 2 '14 at 5:09
  • $\begingroup$ @MMP, excellent! As a side note, writing something like "problem X is trivially in NP" in assignments or your thesis is also a good way to get a roasting from the examiners ;). It's like swearing; adults (academics) do it all the time, kids (students) get grounded for it. $\endgroup$ – Luke Mathieson Dec 2 '14 at 5:14
  • $\begingroup$ It's not that obvious. You also have to show that you witness (in case of 1.) is bounded in length by a polynomial. This is often trivial, but especially in the Steiner Tree problem you have to be more careful. How do you specify the geometry of your witness, how many bits do you need to encode the coordinates of the vertices (if you do)? $\endgroup$ – A.Schulz Dec 2 '14 at 8:24
  • $\begingroup$ @A.Schulz true, I was thinking of the Steiner Tree problem in graphs - the encoding is more obvious there. $\endgroup$ – Luke Mathieson Dec 2 '14 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.