Results 1 to 2 of 2

Math Help - NP Completeness

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    130

    NP Completeness

    Assume P=NP. Then every language in P except the empty language and the everything language (sigma*) is NP complete.

    Suppose A is in P. I want to reduce any language L in NP to A in polynomial time. I tried to think of a specific language that is NP-complete like SAT, but I couldn't come with an argument. Since L is in P maybe I can come with a polynomial argument that runs A and L and accepts only if they agree.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    It seems to me that if you replace all occurrences of NP with P in the original problem, that would also be true. Then the original problem would follow.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The Completeness Axiom
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 2nd 2010, 01:32 PM
  2. Completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: January 12th 2010, 07:17 AM
  3. Completeness Property
    Posted in the Differential Geometry Forum
    Replies: 10
    Last Post: November 14th 2009, 01:29 PM
  4. completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: August 13th 2009, 06:30 PM
  5. Completeness
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 4th 2009, 11:52 PM

Search Tags


/mathhelpforum @mathhelpforum