Alexey Guzey    Blog    Feed    Site Contents

Polynomial Time Reductions

Abstract: this post gives a quick overview of polynomial time reductions – a method for computationally cheap transformations of problems into different problems. Chiefly, it’s used to prove that some problems are at least as hard as the other ones, which taps into the discussion of P vs NP problem.

Simple problems and hard problems

Let’s divide all computational problems into two sets: the simple problems and the hard ones. The simple problems are those for which there exists (at least hypothetically) an algorithm that solves them in time polynomial from the size of the input. The hard problems are those for which there does not (and cannot) exist such an algorithm.

An example of a simple problem is the following:

You are given a sequence of numbers. Is the sequence increasing?

One algorithm for this problem is to go along the sequence and compare neighboring numbers. If in all comparisons the number to the left is smaller than the number to the right, then the sequence is indeed increasing. In total, there are comparisons.

An example of a hard problem is the following:

You are given a program. Does it halt within steps?

encoded in binary uses bits, yet a trivial simulation of the program takes steps. This means that for an input of length the simulation will take steps and that this problem can only be solved in exponential time.

The clique problem

Now, suppose we have the following problem:

Does there exist a clique (a set of vertices in a graph such that its every vertex is connected to its every other vertex) of size in a given graph?

We’ll call this problem and we want to know if it’s simple or hard, i.e. we need to prove that is either simple or hard.

If is simple, then, by definition of a simple problem, there exists a polynomial time algorithm for it. And by finding such an algorithm we would prove that is simple.

But if is hard, then to prove this fact we would have to prove that there cannot possibly exist a polynomial time algorithm, which is intuitively a much more difficult task.

Polynomial time reductions

There exists a walkaround for the second case, though.

Let us have a problem that we already know is hard. We’ll call it . Suppose, we found a way to “reduce” to and the reduction takes polynomial time.

Then, if is simple, can be solved by first transforming it into and then solving . The first step takes polynomial time (because the transformation is polynomial time) and the second step takes polynomial time (by definition of a simple problem), thus the entire solution of takes polynomial time. But this contradicts the fact that is hard! It follows that is not in fact simple.

So, to reduce to means “to solve the problem through the problem ”. It’s absurdly easy to confuse which way the reductions work and to try to reduce to when you need to reduce to . This happens because the terminology is dumb as shit. In everyday life we reduce something big to something small; here, it’s the opposite. The way to intuitively remember it is to keep in mind that a simple problem can be solved through a hard problem–doing it would simply be inefficient. But a hard problem cannot be solved through an easy problem–because this would imply that that problem is not hard after all. Thus, we always reduce a simpler problem to a more difficult one.

Let us return to now. Again, the problem statement is:

Does there exist a clique (a set of vertices in a graph that are all connected between each other) of size in a given graph?

And we suspect that this is indeed a hard problem. In this case, we have to find some problem that we know for sure is hard, and then reduce it to . A hard problem we will use here is 3-SAT problem, the formulation of which is the following:

Given a boolean expression that

(1) consists of clauses joined by ANDs

(2) each clause consists of exactly 3 variables (or their negations), joined by ORs

(for example: )

are there such values that the expression is TRUE?

To prove that is hard we need to reduce 3-SAT to . The reduction is elegant but it’s not super straightforward. Moreover it’s explained clearly and beautifully over here, so I invite to check it out and will omit the reduction in this post.

Now, there’s several things to clear up here.

First, I lied when I wrote that we know that 3-SAT is hard. 3-SAT belongs to a large class of problems all of which can be polynomially reduced to one another. This class is called NP-complete (NPC). NPC consists of the hardest problems that can be verified in polynomial time. However, we don’t know whether there exists an algorithm that solves NPC problems in polynomial time. In fact, if we call simple problems P, then finding out whether NPC P would solve the question whether P=NP.

So, for example, while we can reduce the problem of ordering numbers to e.g. clique problem, we don’t know if a reduction from clique to ordering exists. Finding such a reduction or proving that it doesn’t exist would actually constitute the solution of P versus NP.

Ok, one last time: if we suspect that is at least as hard as , then we reduce to to prove it.

A bit more about P, NP, etc.

I find most of the descriptions of the terms P, NP, NPC, and NP-hard to be far from clear. Even the best stackoverflow answer is not as clear as it could possibly be. The way I understand it is that there’s a very natural hierarchy:

  1. P – the problems that can be solved in polynomial time.
  2. NP – the problems answer to which is “yes” or “no”, and if we are presented with a solution that answers “yes”, this solution can be verified in polynomial time (for example, if we’re given a solution for that claims to find a clique of size , we will need to verify that each vertex is connected to other vertices in the clique, for a total of steps.
  3. NPC – the hardest problems in NP. Alternatively, the problems to which we can reduce all problems in NP.
  4. NP-hard – the problems that are at least as hard as NPC.

So, if PNP, then P=NP=NPC. If P NP, then P NP and NP NPC.

Further reading

OpenDSA, Limits to Computing. A more in-depth look a the topic with several reductions presented (the same site I linked to for 3-SAT reduction).

Introduction to the Theory of Computation by Michael Sipser. My fav computation theory textbook.


Thanks to Sergei Obiedkov for reading early drafts of this post and helping me to wrap my head around all of this stuff.

Why You Should Not Go on a Tinder Date with Me

This summer I had been feeling that I had lost my sense of purpose. So, I got really depressed. Then, I started to read a lot.

One of the books I read was an investigation into the appearance of consciousness in humans by Julian Jaynes, called The Origin of Consciousness in the Breakdown of the Bicameral Mind. The book was a curious one. In fact, it was so curious I decided I had to write a review of it. Part-review, part-critique, in the form of an essay slash blog post.

I write the first draft in under a week. I adore it. it exemplifies my wit, my writing talent, and my insightfulness, in a cocktail, which should probably be named “Sex on the Beach with Alexey”. So, I send it over to a friend.

He tells me that he got lost in the first paragraph and he’s not going to read any further. I think he must just be too dull to see its beauty. So, I send the essay to two more friends. The first one tells me that she’s read the first half and she feels that it’s “enough” for her. The other one tells me that she’s finished it and that it’s “ok”.

This is the point where I start to suspect that just maybe I will need to adjust a thing or two. This is also the point where you may start to wonder what the hell does this story have to do with tinder at all.


Coincidentally, I have a tinder date with a girl named L. coming up just a day after I finished the first draft and realized that I have three less friends. L. sports large glasses and flawless carré, and studies economics at my university. She’s also freakishly smart and absurdly hot. I’m just trying my best to look adequate next to her.

Somehow, our chat turns to books and this is where a revelation strikes me. The moment I see an opening, I start to recite the entire blog post I wrote yesterday to her. I can see that she’s trying her best to look interested. I can also see the strain on her face. But. By the variation in that strain I figure out exactly the parts of the post that need the most work.

After the date L. tells me that she’s sorry but she has no further romantic interest.

I chop up the post in pieces and rewrite it almost from the scratch.


Later that week I have agreed to meet up for drinks with another girl: M. She’s athletic and buzzing with energy. M. studies at a medical school and is planning to go on to get a PhD in molecular biology. While waiting for me in metro she was reading Thomas Mann’s The Magic Mountain. Of course, we move on to discuss The Glass Bead Game (which you should totally read if you haven’t yet, by the way). Another few moments later I see the opportunity and I strike: we spend the next half an hour talking about Jaynes. Most of the time her face vacillates between boredom and slight annoyance. But every now and then I see a spark of interest lighting up in her eyes.

After the date she tells me that she loved my sense of humor, but that I’m “not her type”.

I throw out about a third of the post and completely rewrite its intro.


Next week, another unsuspecting girl, V., steps right into my trap. Her jawline tells me about her assertiveness and her light blue eyes speak of the northern coast of France she recently returned from. We’ve been walking around and about the city center for the last 2 hours and eventually we end up discussing Gabriel García Márquez and Latin American magic realism. She found One Hundred Years of Solitude to be remarkable in its picturesqueness; I found it to be remarkable in its obsession with incest. But I’m getting sidetracked.

Slowly but surely, I start to retell her the latest iteration of my essay. She’s definitely immersed. Her eyes start to live up to their promise of la Manche’s excitability and I manage to make her engaged throughout the entire narrative. I realize that it has finally coalesced into something worthwhile.

A few days later she writes me that she wants to hang out some more.

I make few minor edits and finally publish the post.


Thanks to Ann Taranina for reading early drafts of this post and offering helpful suggestions and to my twitter friend Anna for pointing out some typos.

A special thanks to all the girls from tinder who were forced to endure my ramblings on topics, including, but not limited to, Julian Jaynes, modern art, and general concerns about the aesthetics of the modern world.

On a related note–I do free tinder consulting (no this is not a joke; I’m just sad that people are so bad at it and you should write me if you want to improve your tinder profile / general experience).

Make Your Android Experience Better

This post is a collection of unobvious tricks that make using my Android phone so much more pleasant.

Note: instructions here are based on pure Android, Pixel’s launcher, specifically; they may be different if your manufacturer is not Google.

Contents

  1. Clock with seconds in the status bar
  2. Better fingerprint unlock
  3. Faster everything by turning off animations
  4. Less distraction by turning off Google Now Feed
  5. Always on “OK Google”
  6. Finger trace
Continue reading...

My Favorite Textbooks

I find most textbooks to be basically unreadable. Worse still, when I google “best X textbook”, I frequently land on a “classic” textbook that feels like it was written by a fucking reptiloid for people with an entirely different from mine intelligence architecture. I hate formalism. I hate long mechanical derivations. I love thinking in pictures. I love intuitive, explainlikeim5 explanations. I believe that examples should precede definitions, not follow them. Finally, I have big troubles with working memory, which might explain most of the preceding stuff.

Thus, a list of my favorite textbooks/educational materials; all of them are either free or available on libgen.

List so far: linear algebra, calculus, multivariable calculus, topology, computation theory, microeconomics, macroeconomics, econometrics.

(if you feel that your learning style is similar to mine, do share your own favorite texts/materials not on this list!)

Linear algebra

Lecture notes by Vipul Naik. Note: these notes are targeted at social science majors; all Vipul’s course materials, including quizzes and answers to them are here.

Calculus

Calculus by Michael Spivak. Note: you absolutely need somebody to guide you/help with the problems from the book. The Correct™ way to self-study books like this is to email a professor at a local college and ask them if they could help you with stuff you don’t understand and problems (hint: they will be happy to help).

Multivariable calculus

Matec Notes by Alexey Guzey. Note: once I was so angry at the course’s main textbook that I wrote my own set of lecture notes for it; naturally, it has an econ taste to it.

Lecture notes by Vipul Naik. Note: these notes are targeted at social science majors; all Vipul’s course materials, including quizzes and answers to them are here.

Topology

Topology Without Tears by Sidney A. Morris.

Algorithms

Algorithms by Tim Roughgarden. Note: this is a MOOC, not a textbook. But too good not to be included

Computation Theory

Introduction to the Theory of Computation by Michael Sipser. Note: this book was the basis for the Algorithms-2 course I took at the university.

Microeconomics

Intermediate Microeconomics: A Modern Approach by Hal Varian.

Macroeconomics

Macroeconomics by Olivier Blanchard.

Econometrics

Introduction to Econometrics by Christopher Dougherty. Note: lmk if you need solutions for it.

Never Update Your Priors

Having ambition is hard.

You want to be famous but you realize that the closest thing you have to a talent is the ability to come up with 4-level-deep-meta-jokes.

You want to become unimaginably rich but you realize that to achieve that you either need 420 iq or utter unscrupulousness and lots and lots of luck.

You want to create great art but you realize that God probably isn’t using your mind and body to communicate with our benighted world.

You want to change the world but you realize that the chances of this happening are about the same of God finally deciding to use your body to communicate with our benighted world.

So you stop trying. Why bother when there’s twitter and videogames. You didn’t want much anyways.

Here’s how not to give up: don’t update on evidence. The problem is the word realize in each of the sentences above.

Every one of them is true and yet it shouldn’t matter. The instinct to update is almost irresistible and any appeal to faith is taken as a personal offence. The problem with not updating on evidence is the possiblity for your model of the world to become completely decoupled from the actual world. The benefit is a sort of a soft wireheading.

In fact, this is why epistemic rationality is not just useless but is actively harmful. If you’re a depressive type, you will systematically update too much on negative information, too little on positive and will give up too early.

There are two ways to avoid this: (1) recursively change the most fundamental patterns of your cognition to either avoid or properly discount the biases, or (2) to believe that you’re special. As in believe in magick. As in believe in God.

Updating on evidence will make you depressed and useless. Having blind faith will probably make you just as useless, but at least you will have a chance.