1. ## NP P problems

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

2. Assume that $A\prec B$ . Then:

$B$ is $\mathcal{P}$ $\Rightarrow A$ is $\mathcal{P}$
$B$ is $\mathcal{NP}$ $\Rightarrow A$ is $\mathcal{NP}$
$A$ is $\mathcal{NP}$-hard $\Rightarrow B$ is $\mathcal{NP}$-hard

3. Originally Posted by clic-clac
Assume that $A\prec B$ . Then:

$B$ is $\mathcal{P}$ $\Rightarrow A$ is $\mathcal{P}$
$B$ is $\mathcal{NP}$ $\Rightarrow A$ is $\mathcal{NP}$
$A$ is $\mathcal{NP}$-hard $\Rightarrow B$ is $\mathcal{NP}$-hard

I assume $\prec$ denotes a "polynomial time (Turing) reducible" and first one and second one make sense to me.

I don't understand the below one.
$A$ is $\mathcal{NP}$-hard $\Rightarrow B$ is $\mathcal{NP}$-hard

Any explanation?

4. ## I think this will explain....

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

5. @aliceinwonderland: If i've understood, a problem $\mathcal{NP}$-hard is a problem, which has not to be $\mathcal{NP}$, such that every problem in $\mathcal{NP}$ can be reduced to it (it is as hard as every $\mathcal{NP}$ problem).
Maybe do you know problems called $\mathcal{NP}$-complete. A problem is $\mathcal{NP}$-complete if it is $\mathcal{NP}$-hard to it and if it is $\mathcal{NP}$.
(so $\mathcal{NP}$-complete $\Rightarrow$ $\mathcal{NP}$-hard, but not conversely)

Therefore we have: $A$ is $\mathcal{NP}$-hard $\Rightarrow B$ is $\mathcal{NP}$-hard , like with $\mathcal{NP}$-complete problems.

@tho_mee: Yep that's right. All that can be written using the polynomial reduction.
$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 $B$ is $\mathcal{NP}$, checking a solution $x$ for the problem $A$ is the same that checking $f(x)$ for $B$.
$B$ is $\mathcal{NP}$ so the time used to check wether or not $f(x)$ is in $B$ is polynomial, and $f(x)$ is calculated in a polynomial time from $x$, hence checking if $x$ is in $A$ is done in a polynomial time (the composition of polynomials is a polynomial).

(sorry for my english)

6. ## thank you

thank you friend....Thankz for clearing my doubts..
Sorry that I was late.

tho_mee