Mutual information and its cousin, the Uncertainty coefficient (Theil’s U) are useful tools from Information Theory for discovering dependencies between variables that are not necessary described by a linear relationship. I’m short on time, and plenty of good material already exists on the subject: see Section 1.6 in “Pattern Recognition and Machine Learning” by Bishop, […]
The intersection of two current events have born fruit: I’m reading Christopher Bishop’s legendary book: “Pattern Recognition and Machine Learning”, (freely available as PDF from the book’s website!) I recently discovered Shiny for R, which allows building interactive web apps in R. To try out Shiny, I created an interactive visualization for Kullback-Leibler divergence (or […]
In this post, we will prove that the decision version of the set-covering problem is NP-complete, using a reduction from the vertex covering problem (which is NP-complete). This is Exercise 35.3-2 in CLRS3. We will follow the template given in an earlier post. Problem statement We will use the definition for a set cover given […]
In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete). This is Exercise 34.5-5 in CLRS3. We will follow the template given in an earlier post. Problem statement Given a set of numbers, determine whether can be partitioned into and , such […]
In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete). We will follow the template given in an earlier post. Problem statement The decision problem for 0-1 integer programming is formulated as follows: Given an integer matrix and an integer -vector , determine whether there […]
This is the first post in a series of posts where I will attempt to give visual, easy to understand, proofs* of NP-completeness for a selection of decision problems. In this post, I will give a “template” which can be used (and will be used for the proofs I post).