NP P problems

**tho_mee** · January 28th 2009, 12:06 AM

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

**clic-clac** · January 28th 2009, 01:08 PM

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

**aliceinwonderland** · January 28th 2009, 02:45 PM

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?

**tho_mee** · January 28th 2009, 07:28 PM

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

**clic-clac** · January 29th 2009, 01:01 AM

@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)

**tho_mee** · February 10th 2009, 12:47 AM

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

tho_mee

Thread: NP P problems

LinkBack

Thread Tools

Display

NP P problems

I think this will explain....

thank you

Similar Math Help Forum Discussions

memory problems/concentration problems with age?

binomial problems/normal problems

binomial problems as normal problems

Problems with integration word problems

Help thease problems problems

Search Tags