Stark's Legacy

 This post is about 3-sat! Yay!!!!

To quote wikipedia:

http://en.wikipedia.org/wiki/3-SAT#3-satisfiability

3-satisfiability is a special case of k-satisfiability.  Oh.  Who knew?  K = 3.  This is one of Karp's 21 NP-Complete problems?  What is NP-Complete?  Glad you asked.  But first, more from wikipedia:

There are two classes of high-performance algorithms for solving instances of SAT in practice: the conflict-driven clause learning algorithm, which can be viewed as a modern variant of the DPLL algorithm (well known implementation include Chaff, GRASP) and stochastic local search algorithms, such as WalkSAT.

A DPLL SAT solver employs a systematic backtracking search procedure to explore the (exponentially sized) space of variable assignments looking for satisfying assignments. The basic search procedure was proposed in two seminal papers in the early 60s (see references below) and is now commonly referred to as the Davis–Putnam–Logemann–Loveland algorithm ("DPLL" or "DLL"). Theoretically, exponential lower bounds have been proved for the DPLL family of algorithms.

In contrast, randomized algorithms like the PPSZ algorithm by Paturi, Pudlak, Saks, and Zani set variables in a random order according to some heuristics, for example

It feels like something has been ripped out, and I am bleeding off into some dimension I can't see.  I know that this type of wound closes on its own eventually, but until then, it feels like someone has hung a heavy garment bag on my soul, and I am restless...unable to think or focus on any one thing for too long.  I dread going to my job tomorrow because I'm going to face it without her random chats to brighten my day.

A long time ago, I spotted a book called Game of Thrones in the airport bookstore, and ended up hating it, only to find that one of my friends absolutely loves this book.  I did everything I could to rain on his parade, everything I could to ruin it for the billions of people on this planet that needed to be saved from what appeared to be some new and daring form of literature but was actually just a soap opera written to be marketable.  But I digress.

Ostensibly in response to my hatred of this book, this friend of mine revealed to my girlfriend the secretly public location of this very blog.  The security of this blog is based on preventing people in Seattle from reading it, mostly by doing silly things to keep the posts out of relevant search indexes.

At the time I thought nothing of it, and was already planning my next response:  waiting for the last Game of Thrones book to be released, staying up all night to read it and take notes on the major plot twists, and then flying across the country and renting a generator and large speakers and blasting my friends house with a speech revealing the ending of the last book.  I figured that kind of response was on the same level.

Then my girlfriend read my blog, focusing specifically on the parts about her.  I was not prepared for a real problem to occur here.  At first, my sarcasm and use of negative words as compliments infuriated her.  Then, she read a post that cut far deeper, right down to a existing fissure in our relationship.  The actual post was something that, if part of a scrubs episode, would have been a sudden plot development that becomes a major but surmountable set back that ultimately leaves J.D. still dating the girl.  In real life, though, things are different.


While I watched my close college friend get married in an elaborate catholic wedding, my girlfriend was crying, alone, in the hotel room.  A few days later we broke up as she dropped me off at my apartment.

The suffocating feeling that is like a vice squeezing the life out of your heart has actually gone away, mostly, and in its wake is nothing but the dull emptiness that lingers after every girl disappears.

Perhaps expecting this to happen, and preventing myself from getting to emotionally attached, became a self fulfilling prophecy.  Perhaps its true that we really weren't compatible.  Whatever the case, I cannot even begin to put into words all of the things I am going to miss about her, and the thing that hurts the most is knowing that it was my carelessness that hurt her.

Unfortunately, its just another noir ending.  Here's looking at you, kid.