December 14th, 2015


Exact cover

Karp (1972) introduces the name ‘exact cover’ for the following decision problem:

INPUT: Family Sj of subsets of a set ui, i=1,2,…,t

PROPERTY: There is a subfamily ThSj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t

(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.

Instances of this problem often arise in the solution of combinatorial problems … )


Plan to throw one away

When I had interviewed for the job, the interviewer had explained that I was needed to work on their JavaScript engine. The company was a web development tools startup, and they had spotted that it would be a good idea to have JavaScript code running on the server as well as on the client, so that you could share your business logic and validation code between the client-side and server-side parts of your application. There are now lots of products in this space but twenty years ago was probably too soon for this to be a success.

Anyway, the interviewer told me that the JavaScript engine was nearly done, but there were one or two features that were missing, and it was running a bit slowly, so I might have to do a bit of optimization. Sure, I said, that sounded like it would be fun … )