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

The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; ...


4

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_{...


Only top voted, non community-wiki answers of a minimum length are eligible