Recent content by JohnDoe2013

Hi, I'm working on the decision version of the Knapsack optimization problem that asks whether there is a subset of the items with a total value of at least V and where the total weight of the items is at most W. I'm looking for an equivalent problem P for this version of the knapsack...

There is a Theorem that states that if G = (V, E) is a graph, then S is an independent set $\Leftarrow\Rightarrow$ V - S is a vertex cover. Suppose the vertices have positive integer weights. Does it follow from the theorem that: S is an independent set with maximum weight...

Meaning of "Non-Deterministically select" in context of a Non-Deterministic Polynomial Time Decider The following is an example from Sipser. CLIQUE = { <G, k> : G s an undirected graph with a k-clique} The following is a Non-Deterministic Polynomial Time Decider that decides CLIQUE: 1...