patternMinor
Is NP-hard closed against cartesian product with arbitrary languages?
Viewed 0 times
witharbitrarylanguagesclosedhardproductagainstcartesian
Problem
If $L_1$ is NP-hard, $L_1 \times L_2$ is NP-hard for every $L_2 \neq \emptyset$, where
$\qquad \displaystyle L_1 \times L_2 = \{(w_1,w_2) \mid w_1 \in L_1, w_2 \in L_2\}$
Is it true or false and why?
I can't prove it but I also don't find counter example.
$\qquad \displaystyle L_1 \times L_2 = \{(w_1,w_2) \mid w_1 \in L_1, w_2 \in L_2\}$
Is it true or false and why?
I can't prove it but I also don't find counter example.
Solution
$L_1 \times L_2$ is NP-hard.
Proof: Let $L$ be a language in NP, let $f$ be a reduction of $L$ to $L_1$ and let $w_2$ be in $L_2$. Define $g(x) = (f(x), w_2)$. Now $g$ is a polynomial time many-to-one reduction of $L$ to $L_1 \times L_2$ because clearly:
$x \in L \quad \Longleftrightarrow\quad (f(x), w_2) \in L_1\times L_2$
Proof: Let $L$ be a language in NP, let $f$ be a reduction of $L$ to $L_1$ and let $w_2$ be in $L_2$. Define $g(x) = (f(x), w_2)$. Now $g$ is a polynomial time many-to-one reduction of $L$ to $L_1 \times L_2$ because clearly:
$x \in L \quad \Longleftrightarrow\quad (f(x), w_2) \in L_1\times L_2$
Context
StackExchange Computer Science Q#2489, answer score: 6
Revisions (0)
No revisions yet.