The knapsack problem How to write a book / P and NP / leaving home
Soon after we heard a knock on the window and found out that Cathy has been at our terrace smoking cigarettes for the past hour and she already had a half-full ashtray in front of her. Anna, who was already wearing her normal clothes again, opened the door to let her in, and as soon as she entered she started talking, retelling us some news report that she had read about how the leader of some nazi party is gaining more and more followers and how they (I didn’t know if they were a man or a woman) might have a very good result at the next election. She seemed sad at first, but, as Anna was listening to her and encouraging her to tell us more, she quickly got back to her normal self.
“Oh, but you are just doing it to cheer me up,” Cathy said, when she saw my featureless expression which reminded her that, like me, Ann had zero interest in politics and the like, “let’s talk about something else!” And she immediately began a second topic telling us about how her evening with Alex went. It turned out that Alex was so tired that he fell asleep after a really short sex session and she couldn’t wake him up any more, even by touching him and blasting music from the TV.
“Sounds like you had much fun though?” I muttered and then went on to explain that we heard some noises, but Cathy just laughed and explained that she barely made any sound when they were having sex, so what we heard were most probably the sounds of her masturbating next to her sleeping boyfriend.
“That bastard, he always does that” she continued. And then me or Ann asked her if she meant that he always cums and falls asleep after a minute, but she shook her head “No, it’s not that he is bad at it, he just always does exactly what he wants.”
“Well, you didn’t seem like you needed anything more,” Anna retorted immediately in a way that seemed envious, which prompted Cathy to start a long monologue on the topic of sex and masturbation, which I don’t remember very well (something about whether two are connected, like can you have good sex without being good at masturbating) I remember how she ended it: “It’s important to have fun. But you must put some work into it, not just expect it to happen by itself.”.
Then Cathy started asking how our evening went and Ann tried to retell some highlights while carefully trying not to say anything about me, although I didn’t care that much. At some point I even started laughing in the middle of my sentence because I remembered that I had told Ann that the best part I like most about sex was the part I cum, and then I came before actually having sex with her. “Well, you looks like you had a lot more fun than us, even if you didn’t have sex.” Cathy said pointing at me, as even though I didn’t tell the “joke”, I still couldn’t suppress my laughter.
Hearing her say this made this whole leit motif about the parallel between me and Alex enter my mind again, as if the thoughs were sitting there all along preparing to ambush my brain whenever they have a chance. In particular, I thought how I had spend my life falling in love with girls, while he seemed to have spent his time just fucking them (and falling asleep, at this particular instance (which was something that I myself was better off doing at that moment, but my brain couldn’t stop.)) i.e. I spent it seeking things, (while he spent it finding them.
The first person I fell in love with was one that I met online, who was living in another city. I never met her, although arranging it was not strictly impossible. Nothing in real-life connected us, and she barely knew how I looked like, but she said she loved me and it felt great, even greater than hearing it from someone I knew, plus she wrote some of the most beautiful poetry that I have ever heard, especially from a 14-year-old. I remember this particular line which is probably relevant to the topic:
Probably it’s better for me to suffer from feelings pure and love that’s boundless Than it is, for the lonely soul to count it’s conquests, boring and perverse.
(It sounded better in Bulgarian, I cannot really translate poetry, sorry.)
Now, the thought that occured to me related to this was that if Alex was in a similar situation, he would drive directly to her town as, unlike me, he was pursuing a clear and obtainable goal, which is a prerequisite for achieving something, but also a way to limit what you can achieve.
Upon realizing that, after spending a whole evening being jealous of him, I started to suddenly feel sad for Alex. For although unfulfilled, my dreams suddenly started seeming way more exciting that anything that he can experience, either by dreaming or doing, and my world - immensely richer. At that time, (though not always) sex without feelings seemed just a glorified form of masturbation.
A little later at night I looked at my notes on the Knapsack problem which were laying there, on Anna and Cathy’s desk (which looked exactly like the one on mine and Alex’s room) and with my reversed judgment I instantly realized that the problem had no solution, that P and NP were just two unrelated classes of problems, that the connection between them was made up. My shift was so complete that I didn’t understand how can a person even imagine that P=NP.
Whenever you study mathematics, as in real life, you came across those very weird and convoluted structures that are beyond any kind of explanation - you have the fractals like the Mandelbrot set, that is a result of a super simple equation but looks totally out of this world, you had the continuous processes that work in a way that is totally inexplicable to me, NP , the monster group (for which John Conway said that it’s his only wish to “know what it is about”). But no, most people who study maths would either ignore most of those or dismiss them as uninteresting, or alternatively obsess over one of them, forcefully trying to fit it in their invented structure, like so many people tried to fit NP into P. But neither worked. They were not normal, nor they were weird. They were just inexplicable.
Thinking about all this, I wrote a proof that P does not equal NP, which I thought was correct, but which did not resemble any of the mathematical proofs that I have seen (with the possible exception of the one in Turing’s “On computable numbers…” (the one where he introduced the Turing machine in order to prove that some mathematical problems are undecidable.)) but instead looked more like an essay. I will sketch the proof in the remainder of this chapter:
It started with an idea in logic. The idea that, when they are reduced to logic, mathematical truths (as well as all other absolute truths) are tautologies i.e. they are just repetitions of things that are already given (axioms, postulates etc.) i.e. all mathematical truths are basically a very convoluted formulations of the statement A = A.
An important corollary of this which may surprise some people (while at the same time being completely obvious to others) is that mathematical propositions don’t say anything about the real world. So, for example when you say that something like 1 + 1 = 2 is true, you are not asserting a fact about some real objects (apples oranges, etc.), you are merely simply saying that the terms 1 + 1 and 2 are defined in such a way that they can be used interchangeably. It’s all semantics, like Wittgenstein says (Hey, do you know that Wittgenstein taught maths to Allan Turing? Nevermind, that’s probably not relevant.)
My next step is to try to see what the statement P=NP would look like when we take this idea as a premise, that is, if all mathematical statements are tautologies. If so, then proving that P=NP would involve reformulating the statement “ The solution of Problem A can be check for correctness in n iterations” to “Problem A can be solved in n iterations”.
Finally, my paper went on to prove that such reformulation is impossible. This is where it gets hairy, because I wanted to be as verbose as possible, but intuitively it is obvious that the process of solving a problem, as the process of checking if a solution to a problem is correct are two different real-world (physical) processes and therefore a mathematical statement that is about one cannot be expected to derive something about the other. To rephrase the computer scientist Scott Aaronson, being able to appreciate Mozart’s symphonies does not mean that you are as good as Mozart. And just like liking music is different from composing music, verifying solutions is different from creating them, and P=NP would imply that the two things are equivalent.
I finished my proof with the same words that I would use to finish this part of the book: “The believe in P=NP is the believe in all-powerful agent, one that is capable of achieving all that is theoretically possible. This belief, however neglects the very essence of what theories are - possible explanations for already existing phenomena.”
The knapsack problem How to write a book / P and NP / leaving home
Meeting my roommate Alex / Picking friends / Who am I / How switching places would solve both of our issues
Hallway Church and Turing / Being stupid
X Nerd stereotypes / How I got my nickname / Establishing connection with my younger self
Good company Social code / Anna / Catherine
Fence Outside / Not being punished / Discreet and continuous models
Outside This or nothing / The moon / Fractals / Me and Alex / Explanations / Is the world mathematical
What are we in for Anna's kinky alter ego / Marijuana
What are we in for contd The conformist choice / Taboos / Dichotomies /Marijuana
Back to the facility Anna and Cathy / Trying to be like other people / Sleeping with Anna
The sleepover Anna's childish behavior / Critics / Boring robots / Adoring Anna
The sleepover contd Irony / Heroes and deserters / Retreat to where? / Real and ideal / Choices
Us and them The uncut book pages / Envy
Sex Anna's fantasy / What makes us weird / The establishment and being normal
Cigarettes Alex's good night sleep / About me and Alex again / Sex and love / The proof that P does not equal NP