The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem... We do? ... mostly to prove Subset Sum is NP-Complete. There's no particular reason to go down that route. Karp [1] defined the Knapsack problem as: given $a_1, \dots, a_r, b\in\mathbb{Z}$, is there a set $S\subseteq \{1, \dots,... 3 Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here) That's not odd at all: it's because no such proof exists. Anything that can ... 1 Your reduction$f$works in nondeterministic logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete. What might be confusing you is that PSPACE=NPSPACE, which is ... 1 I think the easiest way is to reduce$ VC_{n/2}=\{G∣G=(V,E) $has a vertex cover of size$|V(G)|/2\}.$( https://cs.stackexchange.com/a/90487/72705) to$ HS_{n/2}=\{(S,F)∣\exists H\subseteq S: $$H is a HS of F of size at most |S|/2$$\}$. In https://cs.stackexchange.com/a/90487/72705 , they show that$VC_{n/2}$is$NP$-hard. Now, we reduce$VC_{...