Advent of Code 2020 has finally started! I’ve been looking forward to it, as it will be a good excuse to brush off my absolute favorite general purpose language: Racket.
Follow my solutions on: https://github.com/AvitusA/adventofcode2020
Racket
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.
We seek to answer whether a set cover \(\mathcal{C}\) exists for \(X\) (the set containing the elements to be covered), containing a maximum of \(k\) sets.
[Read More]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. I created these while studying them back in college. Hopefully, they’ll be helpful for someone.
In this post, I will give a “template” which can be used (and will be used for the proofs I post). [Read More]
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.
The decision problem for 0-1 integer programming is formulated as follows:
Given an integer \(m \times n\) matrix \(A\) and an integer \(m\)-vector \(b\), determine whether there exists an integer \(n\)-vector \(x\) with elements in \(\{0, 1\}\), such that:
\[ Ax \le b \] [Read More]
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 also happens to be Exercise 34.5-5 in CLRS3.
We will follow the template given in an earlier post.
Given a set \(S\) of numbers, determine whether \(S\) can be partitioned into \(A\) and \(\overline{A} = S - A\), such that: \[ \sum_{x \in A} x = \sum_{x \in \overline{A}} x \] [Read More]