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
