Complexity Theory - Part 2

Polynomial Verification:

NP:

Reducibility:

NP-Completeness:

Graphical representation of the complexity classes

Procedure for proof:

  1. Prove L ϵ NP.
  2. Select a known NP-complete language L’.
  3. Describe an algorithm that computes a function f mapping every instance x ϵ {0, 1}* of L’ to an instance f(x) of L.
  4. Prove that the function f satisfies x ϵ L’ iff f(x) ϵ L for all x ϵ {0,1}*.
  5. Prove that the algorithm computing f runs in polynomial time.

Decision vs Optimization Problems:

References:

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Probability Distributions

Quantitative Comparison Questions: Doubtful D!

Econometrics — How to Perform Price Optimization

Creating Maximally Entangled State Using Controlled-Y Gate

The Theory of Renewal Processes

Learning Math With Manipulatives — Base Ten Blocks (Part II)

Top Ten Chess Openings to Try!

Infinite Dice Game

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sohamchauhan

Sohamchauhan

More from Medium

Union Find / Algorithm

Complexity classes in Algorithms

Divide and Conquer: Karatsuba Integer Multiplication

Loop Unrolling Explained (Part 1)