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, […]

# Author Archives: Fredrik

## KL Divergence Online Demo

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 […]

## Proving the set-covering problem is NP-complete (using reduction from the vertex-cover problem)

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[1]. We will follow the template given in an earlier post. Problem statement We will use the definition for a set cover given […]

## Proving set-partition problem is NP complete (using reduction from subset sum)

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[1]). This is Exercise 34.5-5 in CLRS3[1]. 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 […]

## Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)

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[1]). We will follow the template given in an earlier post. Problem statement The decision problem for 0-1 integer programming is formulated as follows[2]: Given an integer matrix and an integer -vector , determine whether there […]

## How to show a problem is NP-complete

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).