Scribd Logo
Upload

Welcome to Scribd!

  • 21 views

    Analysis of Algorithm: By: Waqas Haider Khan Bangyal

    Uploaded by

    resham amanat
    This document discusses complexity classes P, NP, NP-Complete, and NP-Hard. P represents problems solvable in polynomial time. NP includes problems where a yes answer can be verified in polynomial time. NP-Complete problems are the hardest in NP, such that any NP problem can be reduced to an NP-Complete problem in polynomial time. NP-Hard problems are at least as hard as NP-Complete, but are not necessarily in NP.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Analysis of Algorithm: By: Waqas Haider Khan Bangyal

    Uploaded by

    resham amanat
    21 views12 pages
    This document discusses complexity classes P, NP, NP-Complete, and NP-Hard. P represents problems solvable in polynomial time. NP includes problems where a yes answer can be verified in polynomial time. NP-Complete problems are the hardest in NP, such that any NP problem can be reduced to an NP-Complete problem in polynomial time. NP-Hard problems are at least as hard as NP-Complete, but are not necessarily in NP.

    Original Title

    AOA-Lecture-23

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses complexity classes P, NP, NP-Complete, and NP-Hard. P represents problems solvable in polynomial time. NP includes problems where a yes answer can be verified in polynomial time. NP-Complete problems are the hardest in NP, such that any NP problem can be reduced to an NP-Complete problem in polynomial time. NP-Hard problems are at least as hard as NP-Complete, but are not necessarily in NP.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    21 views12 pages

    Analysis of Algorithm: By: Waqas Haider Khan Bangyal

    Uploaded by

    resham amanat
    This document discusses complexity classes P, NP, NP-Complete, and NP-Hard. P represents problems solvable in polynomial time. NP includes problems where a yes answer can be verified in polynomial time. NP-Complete problems are the hardest in NP, such that any NP problem can be reduced to an NP-Complete problem in polynomial time. NP-Hard problems are at least as hard as NP-Complete, but are not necessarily in NP.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 12

    Analysis of Algorithm

    By:
    Waqas Haider khan Bangyal
    P, NP, NP-Complete and NP-Hard?
    Polynomial time
    Problems in class P can be solved with algorithms that
    run in polynomial time.
    Say you have an algorithm that finds the smallest
    integer in an array.  One way to do this is by iterating
    over all the integers of the array and keeping track of
    the smallest number you've seen up to that point. 
    Every time you look at an element, you compare it to
    the current minimum, and if it's smaller, you update
    the minimum.
    Polynomial time
    How long does this take?  Let's say there are n
    elements in the array.  For every element the algorithm
    has to perform a constant number of operations. 
    Therefore we can say that the algorithm runs in O(n)
    time, or that the runtime is a linear function of how
    many elements are in the array.*  So this algorithm
    runs in linear time.
    You can also have algorithms that run in quadratic
    time (O(n^2)), exponential time(O(2^n)), or
    even logarithmic time (O(log n)). 
    Polynomial time
    Binary search (on a balanced tree) runs in logarithmic
    time because the height of the binary search tree is a
    logarithmic function of the number of elements in the
    tree.

    If the running time is some polynomial function of the


    size of the input**, for instance if the algorithm runs
    in linear time or quadratic time or cubic time, then we
    say the algorithm runs in polynomial time and the
    problem it solves is in class P.
    P
    P is a complexity class that represents the set of all decision
    problems that can be solved in polynomial time. That is, given an
    instance of the problem, the answer yes or no can be decided in
    polynomial time.
    Example
    Given a graph connected G, can its vertices be coloured using
    two colours so that no edge is monochromatic?
    Algorithm: start with an arbitrary vertex, color it red and all of its
    neighbours blue and continue. Stop when you run out of vertices
    or you are forced to make an edge have both of its endpoints be
    the same color.
    NP
    NP is a complexity class that represents the set of all
    decision problems for which the instances where the
    answer is "yes" have proofs that can be verified in
    polynomial time.
    This means that if someone gives us an instance of the
    problem and a certificate (sometimes called a witness)
    to the answer being yes, we can check that it is correct
    in polynomial time
    NP-Complete
    NP-Complete is a complexity class which represents
    the set of all problems X in NP for which it is possible to
    reduce any other NP problem Y to X in polynomial time.
    NP-hard
    Intuitively, these are the problems that are at least as
    hard as the NP-complete problems. Note that NP-hard
    problems do not have to be in NP, and they do not have
    to be decision problems.
    The precise definition here is that a problem X is NP-
    hard, if there is an NP-complete problem Y, such
    that Y is reducible to X in polynomial time.
    Notice how difficulty increases top to bottom: any NP can
    be reduced to NP-Complete, and any NP-Complete can be
    reduced to NP-Hard, all in P (polynomial) time.
    If you can solve a more difficult class of problem in P time,
    that will mean you found how to solve all easier problems
    in P time (for example, proving P = NP, if you figure out
    how to solve any NP-Complete problem in P time).
    https://www.quora.com/What-are-P-NP-NP-
    complete-and-NP-hard

    You might also like