Loading ...
Sorry, an error occurred while loading the content.

What is NP-Completeness

Expand Messages
  • Shlomi Fish
    Many people talk about problems being NP-Complete, NP-Hard, etc., but I did not know what these terms exactly were until I took the course Design and Analysis
    Message 1 of 5 , Jul 6, 2002
    View Source
    • 0 Attachment
      Many people talk about problems being NP-Complete, NP-Hard, etc., but I
      did not know what these terms exactly were until I took the course
      "Design and Analysis of Algorithms" this semester. So I'd like to
      summarize this subject here.

      1. P-Space

      P-Space is the set of algorithms that can run in polynomial time (e.g:
      O(n), O(n^2), O(n*log(n)), O(n^100), etc). They have some interesting
      proprties. Like that a P algorithm will run in polynomial time in every
      Turing machine. Or that running one algorithm after another or one using
      the other when both are P would make the resultant algorithm P.

      2. Reduction

      A reduction for algorithm A to algorithm B is another algorithm that can
      take the input of A convert it to an input acceptable by B, and then use B
      to solve the original input properly. A polynomial reduction is one that
      runs at polynomial time.

      3. Verification and NP-space

      A verification algorithm V for algorithm A is an algorithm that take an
      input for A and a possible result, called the witness, and verifies that
      the witness is a valid solution to the input.

      NP are all the set of all algorithms whose verification runs at polynomial
      time. They include all P-space algorithms (because we can verify them by
      solving them in Polynomial time).

      4. NP-hard

      An NP-hard algorithm is an algorithm that there exists a polynomial
      reduction from every algorithm in NP to it. An NP-hard algorithm is not
      necessarily in NP (it could be harder than that)

      5. NP-Complete

      An NP-Complete algorithm is an algorithm in NP that is also NP-Hard. I.e:

      NPC = Intersection(NP, NPC).

      To prove that an algorithm is NP-Complete one needs to:

      1. Prove that its verification can be done in Polynomial time.

      2. Prove that another NP-Complete algorithm can be reduced to it in
      polynomial time.

      Of course, it was proven that a certain algorithm (SAT) was NP-Complete
      the hard way, by proving any NP algorithm can be reduced to it in
      polynomial time.

      6. Open Questions
      -----------------

      It can be shown that NP-Complete algorithms can be solved in exponentail
      time (i.e: O(e^P(n))). However, no one has proved that they cannot be
      solved in polynomial time, too. If an NP-Complete algorithm can be solved
      in Polynomial time than P=NP. If an NP-Complete algorithm can be proven to
      require a greater order of growth to solve, than NP is not P.

      For some NP-Complete problems, there are approximation algorithms that
      can approximate the solution up to a certain order. OTOH, for some such
      problems it was proven that finding such an approximation algorithm of any
      order, would mean that NP == P.

      There is a summary of this subject in Cormen-Leiserson-Rivest and in many
      other books.

      Regards,

      Shlomi Fish

      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      "Let's suppose you have a table with 2^n cups..."
      "Wait a second - is n a natural number?"
    • Tzafrir Cohen
      ... P-space is normally used as the set of languages for which there are machines that run with polynomial *space* . P is the common name for the class of
      Message 2 of 5 , Jul 6, 2002
      View Source
      • 0 Attachment
        On Sat, 6 Jul 2002, Shlomi Fish wrote:

        >
        > Many people talk about problems being NP-Complete, NP-Hard, etc., but I
        > did not know what these terms exactly were until I took the course
        > "Design and Analysis of Algorithms" this semester. So I'd like to
        > summarize this subject here.
        >
        > 1. P-Space
        >
        > P-Space is the set of algorithms that can run in polynomial time (e.g:
        > O(n), O(n^2), O(n*log(n)), O(n^100), etc)

        P-space is normally used as the set of languages for which there are
        machines that run with polynomial *space* . P is the common name for the
        class of languages which have polynomial time machines.

        (Although nobody has yet proved that P != P-Space)

        > . They have some interesting
        > proprties. Like that a P algorithm will run in polynomial time in every
        > Turing machine. Or that running one algorithm after another or one using
        > the other when both are P would make the resultant algorithm P.
        >
        > 2. Reduction
        >
        > A reduction for algorithm A to algorithm B is another algorithm that can
        > take the input of A convert it to an input acceptable by B, and then use B
        > to solve the original input properly. A polynomial reduction is one that
        > runs at polynomial time.
        >
        > 3. Verification and NP-space
        >
        > A verification algorithm V for algorithm A is an algorithm that take an
        > input for A and a possible result, called the witness, and verifies that
        > the witness is a valid solution to the input.
        >
        > NP are all the set of all algorithms whose verification runs at polynomial
        > time. They include all P-space algorithms (because we can verify them by
        > solving them inPolynomial time).
        >
        > 4. NP-hard
        >
        > An NP-hard algorithm is an algorithm that there exists a polynomial
        > reduction from every algorithm in NP to it. An NP-hard algorithm is not
        > necessarily in NP (it could be harder than that)
        >
        > 5. NP-Complete
        >
        > An NP-Complete algorithm is an algorithm in NP that is also NP-Hard. I.e:
        >
        > NPC = Intersection(NP, NPC).

        Intersection(NP, NP-Hard)

        >
        > To prove that an algorithm is NP-Complete one needs to:
        >
        > 1. Prove that its verification can be done in Polynomial time.
        >
        > 2. Prove that another NP-Complete algorithm can be reduced to it in
        > polynomial time.
        >
        > Of course, it was proven that a certain algorithm (SAT) was NP-Complete
        > the hard way, by proving any NP algorithm can be reduced to it in
        > polynomial time.
        >
        > 6. Open Questions
        > -----------------
        >
        > It can be shown that NP-Complete algorithms can be solved in exponentail
        > time (i.e: O(e^P(n))). However, no one has proved that they cannot be
        > solved in polynomial time, too. If an NP-Complete algorithm can be solved
        > in Polynomial time than P=NP.If an NP-Complete algorithm can be proven to
        > require a greater order of growth to solve, than NP is not P.
        >
        > For some NP-Complete problems, there are approximation algorithms that
        > can approximate the solution up to a certain order. OTOH, for some such
        > problems it was proven that finding such an approximation algorithm of any
        > order, would mean that NP == P.
        >
        > There is a summary of this subject in Cormen-Leiserson-Rivest and in many
        > other books.

        --
        Tzafrir Cohen
        mailto:tzafrir@...
        http://www.technion.ac.il/~tzafrir
      • Chen Shapira
        ... Do you have an example for a problem that is NP-Hard, but not NP? I don t think I ever saw one. Thanks, Chen.
        Message 3 of 5 , Jul 6, 2002
        View Source
        • 0 Attachment
          > 4. NP-hard
          >
          > An NP-hard algorithm is an algorithm that there exists a polynomial
          > reduction from every algorithm in NP to it. An NP-hard
          > algorithm is not
          > necessarily in NP (it could be harder than that)

          Do you have an example for a problem that is NP-Hard, but not NP?
          I don't think I ever saw one.

          Thanks,
          Chen.
        • Tzafrir Cohen
          ... If a certain language is NP-hard, it means that any NP language can be reduced to it (a misleading verb!): if you can solve it in polynomial time, you can
          Message 4 of 5 , Jul 6, 2002
          View Source
          • 0 Attachment
            On Sat, 6 Jul 2002, Chen Shapira wrote:

            >
            > > 4. NP-hard
            > >
            > > An NP-hard algorithm is an algorithm that there exists a polynomial
            > > reduction from every algorithm in NP to it. An NP-hard
            > > algorithm is not necessarily in NP (it could be harder than that)
            >
            > Do you have an example for a problem that is NP-Hard, but not NP?
            > I don't think I ever saw one.

            If a certain language is NP-hard, it means that any NP language can be
            reduced to it (a misleading verb!): if you can solve it in polynomial
            time, you can solve any NP language in polynomial time.

            Here is a semi-formal proof that the halting problem is NP-Hard:

            (Feel free to skip to its end)

            Proof
            """""
            Suppose, for instance, that you happened to have an oracle for the halting
            problem. That is: your machine is equiped with an extra helper procedure
            to which you give a turing machine and input, and it answers if the
            machine will halt on the input.

            So if you want to have a machine that can solve any NP language, that is:
            given any NP language, L, you know that there is a [polynomial] machine Mp
            that accepts the verification relation of L.

            So you simply build a machine that tries to run Mp on any possible
            "witness", until it finds such a witness. Then it asks the oracle (for the
            halting problem) if this machine will stop.

            All of your operations could be easily done in polynomial time: you know
            in advance what Mp is. So all you have to do is to create a machine that
            runs Mp in a loop.

            If a witness exists, the created machine would eventually find it, if run.
            Therefore it would stop. The oracle will therefore answer that it it would
            stop, and your machine will answer yes.

            If there is no witness, the machine would keep looking for it, and never
            stop. Therefore the oracle will answer that it wouldn't stop.

            >>>>>>>>>>>>>>>>>>>> End proof

            So what did we learn?

            1. It is dangerous to have Machines with HP oracles. You can never know
            what they will do ;-)

            2. The verb "reduce" is confusing . the empty language is easily reducable
            (with any reasonable reduction method) to almost any other language.

            3. So there are enough languages that are not even verfiable in polynomial
            time, but if you could ignore their running time and resources, you
            would have solved any NP problem easily.

            --
            Tzafrir Cohen
            mailto:tzafrir@...
            http://www.technion.ac.il/~tzafrir
          • Nadav Har'El
            ... Actually, Tzafrir, what you describe is normally spelled PSPACE , with capital letters. But you re right that using the phrase P space to refer to the
            Message 5 of 5 , Jul 6, 2002
            View Source
            • 0 Attachment
              On Sat, Jul 06, 2002, Tzafrir Cohen wrote about "Re: [hackers-il] What is NP-Completeness":
              > On Sat, 6 Jul 2002, Shlomi Fish wrote:
              > > 1. P-Space
              > >
              > > P-Space is the set of algorithms that can run in polynomial time (e.g:
              > > O(n), O(n^2), O(n*log(n)), O(n^100), etc)
              >
              > P-space is normally used as the set of languages for which there are
              > machines that run with polynomial *space* . P is the common name for the
              > class of languages which have polynomial time machines.

              Actually, Tzafrir, what you describe is normally spelled "PSPACE", with
              capital letters. But you're right that using the phrase "P space" to refer
              to the complexity class "P" is indeed ambiguous, to say the least, to
              people who also know about "PSPACE".

              Anyway, Shlomi's summary was mostly correct, and good, but I doubt that a
              person without previous knowledge of these issues would be able to grasp the
              difference between "algorithm" and "verification" (of what, by the way?
              where is your "proof" that you need to verify?), or the concept of languages,
              and Turing machines (and non-deterministic Turing machines, the reason NP,
              non-deterministic polynomial, got its name), from such a short introduction.
              Anyone who's interested in more "meat" about these issues, should probably
              take the course "Computation Theory" and later "Complexity Theory" in the
              Technion, or some comparable course in another university. Or just read
              a book that talks about this subject, if you have access to a good CS
              library.

              Good night :) (I should be sleeping in such hours...)

              --
              Nadav Har'El | Sunday, Jul 7 2002, 27 Tammuz 5762
              nyh@... |-----------------------------------------
              Phone: +972-53-245868, ICQ 13349191 |A Life? Cool! Where can I download one of
              http://nadav.harel.org.il |those from?
            Your message has been successfully submitted and would be delivered to recipients shortly.