Note that things like searching for solutions online is still prohibited In order to prove a...
Note that things like searching for solutions online is still prohibited In order to prove a problem is NP-complete, you must: . Show that the problem is in NP. .A reduction in the correct direction. Reductions in the wrong direction will considerably reduce the credit you can get for a problem . An explanation for why your reduction has no false positives. An explanation for why your reduction has no false negatives. You may assume that any problem shown to be NP-complete in lecture is N'P-complete. For purposes of this assignment, use only those problems 1. The STEINER TREE problem is as follows. Given an undirected graph G = (V,E) with nonnegative edge costs and whose vertices are partitioned into two sets, R and S, find a tree T C G such that for every vE R, vET with total cost at most C. That is, the tree that contains every vertex in R (and possibly some in S) with a total edge cost of at most C. Prove that this problem is N'P-complete.