hai
If a problem A is NP-Complete and A can be reduced to B then B is also NP complete.
same way can you say
if A is P then B is also P.
if A is NP then B is also NP.
if A is NP Hard then B is also NP Hard.....
tho_mee
Assume that $\displaystyle A\prec B$ . Then:
$\displaystyle B$ is $\displaystyle \mathcal{P}$ $\displaystyle \Rightarrow A$ is $\displaystyle \mathcal{P}$
$\displaystyle B$ is $\displaystyle \mathcal{NP}$ $\displaystyle \Rightarrow A$ is $\displaystyle \mathcal{NP}$
$\displaystyle A$ is $\displaystyle \mathcal{NP}$-hard $\displaystyle \Rightarrow B$ is $\displaystyle \mathcal{NP}$-hard
I assume $\displaystyle \prec$ denotes a "polynomial time (Turing) reducible" and first one and second one make sense to me.
I don't understand the below one.
$\displaystyle A$ is $\displaystyle \mathcal{NP}$-hard $\displaystyle \Rightarrow B$ is $\displaystyle \mathcal{NP}$-hard
Any explanation?
A<B
means A is as hard as B
A & B can be either P,NP,NP-Complete or NP-Hard.
We knw P < NP but not NP-Complete < NP-Complete < NP-hard
So if A is reducible to B ... A<B
if A is NP-Hard then it means A is as hard as B. NP-hard is the maximum case of complexity. So if A itself is NP-hard then B has to be NP-Hard.
Same way we can explain the others also.
if B is P then A has to be P as nothing less than P is there. But if A is P then since A<B, B can be either P, NP NP-Complete or NP -Hard .
if B is NP then A can be P or NP . But P is a subset of NP. So there is nothing wrong saying A is NP.But if you take the other way round..if A is NP then B can be either NP-complete or NP-Hard.
Correct me if I am wrong.
-tho_mee
@aliceinwonderland: If i've understood, a problem $\displaystyle \mathcal{NP}$-hard is a problem, which has not to be $\displaystyle \mathcal{NP}$, such that every problem in $\displaystyle \mathcal{NP}$ can be reduced to it (it is as hard as every $\displaystyle \mathcal{NP}$ problem).
Maybe do you know problems called $\displaystyle \mathcal{NP}$-complete. A problem is $\displaystyle \mathcal{NP}$-complete if it is $\displaystyle \mathcal{NP}$-hard to it and if it is $\displaystyle \mathcal{NP}$.
(so $\displaystyle \mathcal{NP}$-complete $\displaystyle \Rightarrow$ $\displaystyle \mathcal{NP}$-hard, but not conversely)
Therefore we have: $\displaystyle A$ is $\displaystyle \mathcal{NP}$-hard $\displaystyle \Rightarrow B$ is $\displaystyle \mathcal{NP}$-hard , like with $\displaystyle \mathcal{NP}$-complete problems.
@tho_mee: Yep that's right. All that can be written using the polynomial reduction.
$\displaystyle A\prec B \Rightarrow \exists f\ \text{recursive and calculable in polynomial-time s.t.}\ \forall x,\ x\in A \Leftrightarrow f(x)\in B $.
So, for instance, if $\displaystyle B$ is $\displaystyle \mathcal{NP}$, checking a solution $\displaystyle x$ for the problem $\displaystyle A$ is the same that checking $\displaystyle f(x)$ for $\displaystyle B$.
$\displaystyle B$ is $\displaystyle \mathcal{NP}$ so the time used to check wether or not $\displaystyle f(x)$ is in $\displaystyle B$ is polynomial, and $\displaystyle f(x)$ is calculated in a polynomial time from $\displaystyle x$, hence checking if $\displaystyle x$ is in $\displaystyle A$ is done in a polynomial time (the composition of polynomials is a polynomial).
(sorry for my english)