---

Classification of problems: The class NP and beyond...

---

• Decision problems
  • Decision problem:

    A decision problem is a problem that takes as input: An input string w       and produces as output: Yes, or No

    ---

  • Example:

    Input string: x1 x2 x3 x4 y1 y2 y3 y4 (x1, y1) (x1, y2) (x2, y1) (x2, y2) (x3, y1) (x3, y2) (x3, y3) (x3, y4) (x4, y2) representing the following bi-partite graph: Decision problem: Does the graph have a maximum matching ?

  ---

  ---

• The clas P: Polynomial Time Problems
  • The class P of problem is one of the most fundamental complexity classes.

    ---

  • The class P contains:

    All decision problems which can be solved by a deterministic Turing machine (~ uses no "guessing") in polynomial time. I.e.: There is an algorithm (a computer program with unbounded memory) that can produce the correct answer for any input string of length n in at most c × nk steps, where c and k are constants

    ---

  • Examples:

    Maximum flow: Does (a given basic network) G has a max flow value ≥ 10 ?       We can find the solution without guessing using the flow augmenting path technique and use the solution to resolve the above decision problem Maximum matching: Does (a given bi-partite graph) G has a maximum matching ?       We can find the solution without guessing using the alternating path technique and use the solution to resolve the above decision problem

  ---

  ---

• The class NP
  • The class NP contains:

    All decision problems which can be solved by a non-deterministic Turing machine (~ allows good guessing) in polynomial time

    ---

  • A non-deterministic Turing machine is (more or less) a computer that can guess a "good" solution

    But the computer must still verify that the guessed solution is correct

    Therefore, the class NP contains:

    All decision problems where a potential solution for the problem can be verified by a deterministic Turing machine in polynomial time

  ---

  ---

• Relationship between classes P and NP
  • P ⊆ NP

    Clearly, if you can determine the solution using a deterministic Turing machine in polynomial time, you can also verify the solution using a deterministic Turing machine in polynomial time...

    ---

    ---

  • What about: NP ⊆ P ???

    This is probably the holy grail in Computer Science.... We still do not have found the answer to this question

    From Wikipedia:

    ---

  • Note:

    If we can prove that NP ⊆ P        Then it follows that: NP = P       So the research question is commonly known as the: P = NP ?          problem

    See: click here

    ---

  • Feeling about the answer (from Wikipedia):

  ---

  ---

  ---

  ---

• NP-complete problems
  • Researcher have identified a number of toughtest problems ∈ NP

  • These problem are called NP-complete problems

    ---

  • Properties of NP-complete problems

    If we can find a polynomial time algorithm to solve any one NP-complete problem, then we would have shown that: P = NP

    And because years of CS research could not settle this question, it implies that:

    Finding a polynomial time algorithm for any NP-complete problem is very difficult

  ---

  ---

• Some NP-complete problems that you have encountered
  • Integer Programming:

    Class notes: click here Wikipedia page: click here

  • Knapsack Problem:

    Class notes: click here Wikipedia page: click here

  • Bin Packing:

    You saw a bin packing problem in a homework: click here More details: click here

    ---

  • Note:

    It is not the case that we cannot solve any NP-complete problems We can solve NP-complete problems of limited (i.e., small) input size

  ---

  ---

• WAIT....   Didn't we find an efficient algorithm for the Knapsack problem ?
  • Recall the Knapsack problem:

    Pack as many items into the knapsack such that the total value of the items packed is maximized        Note: you cannot exceed the capacity of the knapsack !

    Mathematical formulation:

    max: v1×x1 + v2×x2 + ... + vN×xN s.t.: w1×x1 + w2×x2 + ... + wN×xN ≤ W

    ---

    ---

  • Recall the runtime complexity for the Knapsack problem:

    Running time = O(WN) --- See: click here

    $64,000 question:

    Isn't the running time of the Knapsack Problem polynomial ????

  ---

  ---

• Precise Definition of Running Time
  • Time complexity (running time):

    The time complexity of an algorithm is the amount of time taken by an algorithm to run as a function of the size of the input to the problem.

    ---

  • Polynomial running time:

    A polynomial time algorithm is an algorithm whose running time as a function of the size of the input is a polynomial function

  ---

  ---

  ---

  ---

• The reason why the solution of Knapsack is not polynomial

  • Running time:

    O(WN)

  • Inputs used by the Knapsack Problem:

    v1, w1 v2, w2 ... vN, wN W

    Size of the input = 2N + 1 (numbers) !!!!!

    ---

    ---

  • Not polynomial:

    The term W in O(WN) makes the expression non-polynomial in terms of the size of the input (= 2N+1)

    You can look at the situation this way:

    I can make the Knapsack run a very very long time by simply changing W to say 100000000000 It takes no effort at all to make Knapsack run slowly In a real polynomial algorithm, (such as sorting), it will take major effort to make it run slower. In sorting, I would have to type in 100000000000 numbers !!!

  ---

  ---

  ---

  ---

• Possible divisions of the NP problems
  • Depending on whether:

    P = NP or      P ≠ NP

    there are 2 possible divisions of the problems in the class NP:

    If   P = NP	If   P ≠ NP

    ---

  • More information on different topics can be found here:

    NP-intermediate problems: click here NP-complete problems: click here A list of NP-complete problems: click here

  ---

  ---

• Beyond NP-complete: NP-hard
  • NP-complete problems may not be solve by an algorithm in polynomial time

    However, a solution for an NP-complete problem can be verified by an algorithm in polynomial time

    ---

  • There are problems whose solution cannot be verified by an algorithm in polynomial time

    We call these problems: NP-hard problems

    Wikipedia page: click here

  ---

  ---

• What makes a problem NP-complete ?
  • Short Answer:

    We don't have a clue....

    ---

  • What is even worst:

    There are similar looking problems where:          One is NP-complete The other is Polynomial

    ---

  • Example:

    Traveling salesman problem: (actually: Hamiltonian Cycle because I use cost = 1 on all edges) A traveling salesman has to visit customers in several towns, exactly one customer in each town. Given a graph G where: Vertices represent the towns Edges represent a connecting flight between 2 towns              Find a walk that visits every vertex in G and visits each vertex exactly once The Traveling salesman problem (and Hamiltonian Path problem) is NP-complete Euler path problem: A tourist visits a Japanese Garden with plavilion connected by bridges. The tourist wants to see all the views by walking each bridge once Given a graph G where: Vertices represent the plavilions Edges represent a bridges connecting 2 plavilions              Find a walk that visits every edge in G and visits each edge exactly once The Euler Path is polynomial In fact: there is a Euler Path iff every vertex (except 2 - the start and end vertex) has an even degree

    ---

  • Another example:

    Find the shortest path between two vertices in a graph This problem is polynomial (using Dijkstra's Algorithm Find the longest (simple) path between two vertices in a graph This problem is NP-complete

  ---

  ---

• Course to take to learn more on NP
  • CS 424: Theory of Computing