Skip to content

Complexity NP Completeness

  • Hard Problems -> So far no-one else has been able to solve this problem yet
  • Reduction
    • How to use code for other algorithms to generate a new algorithm without having to reinvent the wheel and doing it all yourself.
    • Graph Example Concepts
      • Q -> Given an algorithm for perfect matching design an algorithm for maximum matching
      • Matching -> set of edges 'M' from 'E' such that no vertices are shared
      • Perfect Matching -> Matching but with all vertices included in the set 'M' \(\(It\ has\ \ \ \ \ \frac{|V|}{2}\ \ \ edges\)\)
    • Given an efficient algorithm for problem \(p_1\) , we show that there is an algorithm for \(p_2\) using the algorithm \(p_1\).
    • We say problem A reduces to Problem B if we can use B's functionality to solve A/ part of A.
  • Efficient
    • Running time of the algorithm is bounded by a polynomial in the input size.
    • i.e There exists a constant c such that the running time \(T(n)\) is \(O(n^c)\) where n is the input size
    • Hamiltonian Path -> a path of length n-1 where n is the number of vertices. All vertices are covered through this path
    • Hamiltonian Cycle -> A cycle in graph that spans all vertices
    • if Hamiltonian Cycle exists Hamiltonian Path will exist! Not necessarily the reverse
    • Q. Given an efficient algo for Hamiltonian Cycle prove that an efficient algorithm exits for Hamiltonian Path
    • Problem Types
      • Search Problems
        • Output is many bits
        • Search for a solution and output the solution
        • Output a Hamiltonian Cycle if it exists
      • Decision Problem
        • Output 1 bit
        • Decide whether true or false
        • E.g. Does G have Hamiltonian Cycle
      • For similar problems, if the search problem is easy the other one is hard as well, and vice versa.
    • Q -> Given a search problem [Does the graph have a Hamiltonian Cycle? ] find the cycle in the graph
      • Approach
        1. Consider the edges one by one
        2. For Edge \(E_i\) , remove \(E_i\) and ask the HC algorithm if cycle exists
          1. If Yes -> The edge \(E_i\) is not part of the cycle; discard it
          2. If No -> The edge \(E_i\) is part of the cycle ; keep it
        3. At the end what remains is the cycle itself
  • The Class NP (Non-deterministic Polynomial Time)
    • P vs NP - A very well made video
    • A Decision Problem is said to be in the class NP if for all YES(positive/true) inputs there is a proof (advice/string) using which it can be verified (quickly) that the input is indeed a YES input
      • Proof is what the prover send to verifier
      • Quickly -> efficiently| in time polynomial in the input size
    • A bool Formula in Conjunctive Normal Form (CNF) is an OR of clauses C_1 v C_2 v C_3..v C_n and is an AND of clauses if C_1 ^ C_2 ^ C_3..^ C_n
    • SAT -> Satisfiability Problem (NP Problem)
      • for boolean questions, whether there exists an interpretation that satisfies the formula.
      • SAT belongs to NP
        • Prover gives proof using which verifier can verifiy the problem
        • Proof is an assignment to the variable
        • Verifier uses this assignment to check if the formula evaluates to True!
      • Theorem of Cook If SAT has an efficient algorithm then so does every other problem in NP. Efficient means polynomial time!!!!
      • Goal -> Decision version is among the hardest NP
        • If there is an efficient algorithm to solve decision version problems, then there is an algorithm to solve all algorithms in the NP?
      • IF there exists a polynomial time algorithm for SAT, there is one for all problems in NP
      • Thus SAT is an NP Hard Problem
        • A problem is NP Hard if has the following property
          • If it has a polynomial time algorithm then there is one for every problem in NP.
          • an NP hard is not necessarily part of NP, it can be outside NP but solving it will give efficient algo for all NP problems
    • NP Complete
      • NP Complete Video
      • A problem is NP Complete if
        • The problem belongs to NP
        • Problem is NP Hard!
    • Vertex Cover
      • Given a graph return set of vertices (minimum size) such that the vertices in the result cover all the edges of the graph.
      • To prove -> Vertex cover is NP
        • Proover gives the subset result of k vertices and Graph to the verifier
        • The verifier checks the graph with the subset from the proover
        • Thus, Vertex cover is NP
      • T Prove Vertex cover is NP Hard

        - Assume there is a polynomial time algorithm for Vertex cover