Results 1 to 6 of 6

Math Help - NP P problems

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    3

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by clic-clac View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    3

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    @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)
    Last edited by clic-clac; January 31st 2009 at 06:59 AM. Reason: cal
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2009
    Posts
    3

    thank you

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

    tho_mee
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 3rd 2011, 06:35 AM
  2. binomial problems/normal problems
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 20th 2010, 12:46 AM
  3. binomial problems as normal problems
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 20th 2010, 12:41 AM
  4. Problems with integration word problems
    Posted in the Calculus Forum
    Replies: 5
    Last Post: April 25th 2010, 06:39 PM
  5. Help thease problems problems
    Posted in the Geometry Forum
    Replies: 2
    Last Post: April 1st 2008, 12:03 PM

Search Tags


/mathhelpforum @mathhelpforum