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 $\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

3. Originally Posted by clic-clac
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?

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 $\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)

6. ## thank you

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

tho_mee