Is "Find a Steiner Tree of cost < K" NP-hard? Finding the minimum Steiner tree is well known NP-hard.
It seems obviois that asking "find a Steiner tree of cost &lt; K" has to be NP hard, because I could solve the original problem by repetedly calling an algorithm that solves the second. But is this "repeteadly call"/loop a valid reduction? There seems to be something fishy with it, isn't it exponential in the number of bits of K (like the famous knapsack DP algorithm)?

Thanks
In fact, the optimization version of minimum Steiner tree isn't NP-hard, since only decision problems can be NP-hard. When we say that a minimization problem like minimum Steiner tree is NP-hard, what we mean is that the corresponding decision version is NP-hard. The decision version is just what you wrote: given an instance of minimum Steiner tree and a number $K$, to decide whether the minimum Steiner tree has cost at most $K$.