P=NP

What does “can” mean, anyway?

PNRJ cognitive science, personal, science and academia , , , , , , , , , , ,

Apr 7 JDN 2460409

I don’t remember where, but I believe I once heard a “philosopher” defined as someone who asks the sort of question everyone knows the answer to, and doesn’t know the answer.

By that definition, I’m feeling very much a philosopher today.

“can” is one of the most common words in the English language; the Oxford English Corpus lists it as the 53rd most common word. Similar words are found in essentially every language, and nearly always rank among their most common.

Yet when I try to precisely define what we mean by this word, it’s surprisingly hard.

Why, you might even say I can’t.

The very concept of “capability” is surprisingly slippery—just what is someone capable of?

My goal in this post is basically to make you as confused about the concept as I am.

I think that experiencing disabilities that include executive dysfunction has made me especially aware of just how complicated the concept of ability really is. This also relates back to my previous post questioning the idea of “doing your best”.

Here are some things that “can” might mean, or even sometimes seems to mean:

1. The laws of physics do not explicitly prevent it.

This seems far too broad. By this definition, you “can” do almost anything—as long as you don’t make free energy, reduce entropy, or exceed the speed of light.

2. The task is something that other human beings have performed in the past.

This is surely a lot better; it doesn’t say that I “can” fly to Mars or turn into a tree. But by this definition, I “can” sprint as fast as Usain Bolt and swim as long as Michael Phelps—which certainly doesn’t seem right. Indeed, not only would I say I can’t do that; I’d say I couldn’t do that, no matter how hard I tried.

3. The task is something that human beings in similar physical condition to my own have performed in the past.

Okay, we’re getting warmer. But just what do we mean, “similar condition”? No one else in the world is in exactly the same condition I am.

And even if those other people are in the same physical condition, their mental condition could be radically different. Maybe they’re smarter than I am, or more creative—or maybe they just speak Swahili. It doesn’t seem right to say that I can speak Swahili. Maybe I could speak Swahili, if I spent a lot of time and effort learning it. But at present, I can’t.

4. The task is something that human beings in similar physical and mental condition to my own have performed in the past.

Better still. This seems to solve the most obvious problems. It says that I can write blog posts (check), and I can’t speak Swahili (also check).

But it’s still not specific enough. For, even if we can clearly define what constitutes “people like me” (can we?), there are many different circumstances in which people like me have been in, and what they did has varied quite a bit, depending on those circumstances.

People in extreme emergencies have performed astonishingly feats of strength, such as lifting cars. Maybe I could do something like that, should the circumstance arise? But it certainly doesn’t seem right to say that I can lift cars.

5. The task is something that human beings in similar physical and mental condition to my own have performed in the past, in circumstances similar to my own.

That solves the above problems (provided we can sufficiently define “similar” for both people and circumstances). But it actually raises a different problem: If the circumstances were so similar, shouldn’t their behavior and mine be the same?

By that metric, it seems like the only way to know if I can do something is to actually do it. If I haven’t actually done it—in that mental state, in those circumstances—then I can’t really say I could have done it. At that point, “can” becomes a really funny way of saying “do”.

So it seems we may have narrowed down a little too much here.

And what about the idea that I could speak Swahili, if I studied hard? That seems to be something broader; maybe it’s this:

6. The task is something that human beings who are in physical or mental condition that is attainable from my own condition have performed in the past.

But now we have to ask, what do we mean by “attainable”? We come right back to asking about capability again: What kind of effort can I make in order to learn Swahili, train as a pilot, or learn to SCUBA dive?

Maybe I could lift a car, if I had to do it to save my life or the life of a loved one. But without the adrenaline rush of such emergency, I might be completely unable to do it, and even with that adrenaline rush, I’m sure the task would injure me severely. Thus, I don’t think it’s fair to say I can lift cars.

So how much can I lift? I have found that I can, as part of a normal workout, bench-press about 80 pounds. But I don’t think is the limit of what I can lift; it’s more like what I can lift safely and comfortably for multiple sets of multiple reps without causing myself undue pain. For a single rep, I could probably do considerably more—though how much more is quite hard to say. 100 pounds? 120? (There are online calculators that supposedly will convert your multi-rep weight to a single-rep max, but for some reason, they don’t seem to be able to account for multiple sets for some reason. If I do 4 sets of 10 reps, is that 10 reps, or 40 reps? This is the difference between my one-rep max being 106 and it being 186. The former seems closer to the truth, but is probably still too low.)

If I absolutely had to—say, something that heavy has fallen on me and lifting it is the only way to escape—could I bench-press my own weight of about 215 pounds? I think so. But I’m sure it would hurt like hell, and I’d probably be sore for days afterward.

Now, consider tasks that require figuring something out, something I don’t currently know but could conceivably learn or figure out. It doesn’t seem right to say that I can solve the P/NP problem or the Riemann Hypothesis. But it does seem right to say that I can at least work on those problems—I know enough about them that I can at least get started, if perhaps not make much real progress. Whereas most people, while they could theoretically read enough books about mathematics to one day know enough that they could do this, are not currently in a state where they could even begin to do that.

Here’s another question for you to ponder:

Can I write a bestselling novel?

Maybe that’s no fair. Making it a bestseller depends on all sorts of features of the market that aren’t entirely under my control. So let’s make it easier:

Can I write a novel?

I have written novels. So at first glance it seems obvious that I can write a novel.

But there are many days, especially lately, on which I procrastinate my writing and struggle to get any writing done. On such a day, can I write a novel? If someone held a gun to my head and demanded that I write the novel, could I get it done?

I honestly don’t know.

Maybe there’s some amount of pressure that would in fact compel me, even on the days of my very worst depression, to write the novel. Or maybe if you put that gun to my head, I’d just die. I don’t know.

But I do know one thing for sure: It would hurt.

Writing a novel on my worst days would require enormous effort and psychological pain—and honestly, I think it wouldn’t feel all that different from trying to lift 200 pounds.

Now we are coming to the real heart of the matter:

How much cost am I expected to pay, for it to still count as within my ability?

There are many things that I can do easily, that don’t really require much effort. But this varies too.

On most days, brushing my teeth is something I just can do—I remember to do it, I choose to do it, it happens; I don’t feel like I have exerted a great deal of effort or paid any substantial cost.

But there are days when even brushing my teeth is hard. Generally I do make it happen, so evidently I can do it—but it is no longer free and effortless the way it usually is.

There are other things which require effort, but are generally feasible, such as working out. Working out isn’t easy (essentially by design), but if I put in the effort, I can make it happen.

But again, some days are much harder than others.

Then there are things which require so much effort they feel impossible, even if they theoretically aren’t.

Right now, that’s where I’m at with trying to submit my work to journals or publishers. Each individual action is certainly something I should be physically able to take. I know the process of what to do—I’m not trying to solve the Riemann Hypothesis here. I have even done it before.

But right now, today, I don’t feel like I can do it. There may be some sense in which I “can”, but it doesn’t feel relevant.

And I felt the same way yesterday, and the day before, and pretty much every day for at least the past year.

I’m not even sure if there is an amount of pressure that could compel me to do it—e.g. if I had a gun to my head. Maybe there is. But I honestly don’t know for sure—and if it did work, once again, it would definitely hurt.

Others in the disability community have a way of describing this experience, which probably sounds strange if you haven’t heard it before:

“Do you have enough spoons?”

(For D&D fans, I’ve also heard others substitute “spell slots”.)

The idea is this: Suppose you are endowed with a certain number of spoons, which you can consume as a resource in order to achieve various tasks. The only way to replenish your spoons is rest.

Some tasks are cheap, requiring only 1 or 2 spoons. Others may be very costly, requiring 10, or 20, or perhaps even 50 or 100 spoons.

But the number of spoons you start with each morning may not always be the same. If you start with 200, then a task that requires 2 will seem trivial. But if you only started with 5, even those 2 will feel like a lot.

As you deplete your available spoons, you will find you need to ration which tasks you are able to complete; thus, on days when you wake up with fewer spoons, things that you would ordinarily do may end up not getting done.

I think submitting to a research journal is a 100-spoon task, and I simply haven’t woken up with more than 50 spoons in any given day within the last six months.

I don’t usually hear it formulated this way, but for me, I think the cost varies too.

I think that on a good day, brushing my teeth is a 0-spoon task (a “cantrip”, if you will); I could do it as many times as necessary without expending any detectable effort. But on a very bad day, it will cost me a couple of spoons just to do that. I’ll still get it done, but I’ll feel drained by it. I couldn’t keep doing it indefinitely. It will prevent me from being able to do something else, later in the day.

Writing is something that seems to vary a great deal in its spoon cost. On a really good day when I’m feeling especially inspired, I might get 5000 words written and feel like I’ve only spent 20 spoons; while on a really bad day, that same 20 spoons won’t even get me a single paragraph.

It may occur to you to ask:

What is the actual resource being depleted here?

Just what are the spoons, anyway?

That, I really can’t say.

I don’t think it’s as simple as brain glucose, though there were a few studies that seemed to support such a view. If it were, drinking something sugary ought to fix it, and generally that doesn’t work (and if you do that too often, it’s bad for your health). Even weirder is that, for some people, just tasting sugar seems to help with self-control. My own guess is that if your particular problem is hypoglycemia, drinking sugar works, and otherwise, not so much.

There could be literally some sort of neurotransmitter reserves that get depleted, or receptors that get overloaded; but I suspect it’s not even that simple either. These are the models we use because they’re the best we have—but the brain is in reality far more complicated than any of our models.

I’ve heard people say “I ran out of serotonin today”, but I’m fairly sure they didn’t actually get their cerebrospinal fluid tested first. (And since most of your serotonin is actually in your gut, if they really ran out they should be having severe gastrointestinal symptoms.) (I had my cerebrospinal fluid tested once; most agonizing pain of my life. To say that I don’t recommend the experience is such an understatement, it’s rather like saying Hell sounds like a bad vacation spot. Indeed, if I believed in Hell, I would have to imagine it feels like getting a spinal tap every day for eternity.)

So for now, the best I can say is, I really don’t know what spoons are. And I still don’t entirely know what “can” means. But at least maybe now you’re as confused as I am.

The fragility of encryption

PNRJ computer science, mathematical models , , , , , , ,

Feb 13 JDN 2459620

I said in last week’s post that most of the world’s online security rests upon public-key encryption. It’s how we do our shopping, our banking, and paying our taxes.

Yet public-key encryption has an Achilles’ Heel. It relies entirely on the assumption that, even knowing someone’s public key, you can’t possibly figure out what their private key is. Yet obviously the two must be deeply connected: In order for my private key to decrypt all messages that are encrypted using my public key, they must, in a deep sense, contain the same information. There must be a mathematical operation that will translate from one to the other—and that mathematical operation must be invertible.

What we have been relying on to keep public-key encryption secure is the notion of a one-way function: A function that is easy to compute, but hard to invert. A typical example is multiplying two numbers: Multiplication is a basic computing operation that is extremely fast, even for numbers with thousands of digits; but factoring a number into its prime factors is far more difficult, and currently cannot be done in any reasonable amount of time for numbers that are more than a hundred digits long.


“Easy” and “hard” in what sense? The usual criterion is in polynomial time.

Say you have an input that is n bits long—i.e. n digits, when expressed as a binary number, all 0s and 1s. A function that can be computed in time proportional to n is linear time; if it can only be done in time proportional to n2, that is quadratic time; n3 would be cubic time. All of these are examples of polynomial time.

But if instead the time required were 2n, that would be exponential time. 3n and 1.5n would also be exponential time.

This is significant because of how much faster exponential functions grow relative to polynomial functions, for large values of n. For example, let’s compare n3 with2n. When n=3, the polynomial is actually larger: n3=27 but 2n=8. At n=10 they are nearly equal: n3=1000 but 2n=1024. But by n=20, n3 is only 8000 while 2n is over 1 million. At n=100, n3is a manageable (for a modern computer) 1 million, while 2nis a staggering 1030; that’s a million trillion trillion.

You may see that there is already something a bit fishy about this: There are lots of different ways to be polynomial and lots of different ways to be exponential. Linear time n is clearly fast, and for many types of problems it seems unlikely one could do any better. But is n100 time really all that fast? It’s still polynomial. It doesn’t take a large exponential base to make for very fast growth—2 doesn’t seem that big, after all, and when dealing with binary digits it shows up quite naturally. But while 2n grows very fast even for reasonably-sized n, 1.0000001n grows slower than most polynomials—even linear!—for quite a long range before eventually becoming very fast growth when n is in the hundreds of millions. Yet it is still exponential.


So, why do we use these categories? Well, computer scientists and mathematicians have discovered that many types of problems that seem different can in fact be translated into one another, so that solving one would solve the other. For instance, you can easily convert between the Boolean satisfiability problem and the subset-sum problem or the travelling salesman problem. These conversions always take time that is a polynomial in n(usually somewhere between linear and quadratic, as it turns out). This has allowed to build complexity classes, classes of problem such that any problem can be converted to any other in polynomial time or better.

Problems that can be solved in polynomial timeare in class P, for polynomial.

Problems that can be checked—but not necessarily solved—in polynomial time are in class NP, which actually stands for “non-deterministic polynomial” (not a great name, to be honest). Given a problem in NP, you may not be able to come up with a valid answer in polynomial time. But if someone gave you an answer, you could tell in polynomial time whether or not that answer was valid.

Boolean satisfiability (often abbreviated SAT) is the paradigmatic NP problem: Given a Boolean formula like (A OR B OR C) AND (¬A OR D OR E) AND (¬D OR ¬C OR B) and so on, it isn’t a simple task to determine if there’s some assignment of the variables A, B, C, D, E that makes it all true. But if someone handed you such an assignment, say (¬A, B, ¬C, D, E), you could easily check that it does in fact satisfy the expression. It turns out that in fact SAT is what’s called NP-complete: Any NP problem can be converted into SAT in polynomial time.

This is important because in order to be useful as an encryption system, we need our one-way function to be in class P (otherwise, we couldn’t compute it quickly). Yet, by definition, this means its inverse must be in class NP.


Thus, simply because it is easy to multiply two numbers, I know for sure that factoring numbers must be in NP: All I have to do to verify that a factorization is correct is multiply the numbers. Since the way to get a public key from a private key is (essentially) to multiply two numbers, this means that getting a private key from a public key is equivalent to factorization—which means it must be in NP.

This would be fine if we knew some problems in NP that could never, ever be solved in polynomial time. We could just pick one of those and make it the basis of our encryption system. Yet in fact, we do not know any such problems—indeed, we are not even certain they exist.

One of the biggest unsolved problems in mathematics is P versus NP, which asks the seemingly-simple question: “Are P and NP really different classes?” It certainly seems like they are—there are problems like multiplying numbers, or even finding out whether a number is prime, that are clearly in P, and there are other problems, like SAT, that are definitely in NP but seem to not be in P. But in fact no one has ever been able to prove that P ≠ NP. Despite decades of attempts, no one has managed it.

To be clear, no one has managed to prove that P = NP, either. (Doing either one would win you a Clay Millennium Prize.) But since the conventional wisdom among most mathematicians is that P ≠ NP (99% of experts polled in 2019 agreed), I actually think this possibility has not been as thoroughly considered.

Vague heuristic arguments are often advanced for why P ≠ NP, such as this one by Scott Aaronson: “If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found.”

That really doesn’t follow at all. Doing something in polynomial time is not the same thing as doing it instantly.

Say for instance someone finds an algorithm to solve SAT in n6 time. Such an algorithm would conclusively prove P = NP. n6; that’s a polynomial, all right. But it’s a big polynomial. The time required to check a SAT solution is linear in the number of terms in the Boolean formula—just check each one, see if it works. But if it turns out we could generate such a solution in time proportional to the sixth power of the number of terms, that would still mean it’s a lot easier to check than it is to solve. A lot easier.

I guess if your notion of a “fundamental gap” rests upon the polynomial/exponential distinction, you could say that’s not “fundamental”. But this is a weird notion to say the least. If n = 1 million can be checked in 1 million processor cycles (that is, milliseconds, or with some overhead, seconds), but only solved in 1036 processor cycles (that is, over a million trillion years), that sounds like a pretty big difference to me.

Even an n2 algorithm wouldn’t show there’s no difference. The difference between n and n2, is, well, a factor of n. So finding the answer could still take far longer than verifying it. This would be worrisome for encryption, however: Even a million times as long isn’t really that great actually. It means that if something would work in a few seconds for an ordinary computer (the timescale we want for our online shopping and banking), then, say, the Russian government with a supercomputer a thousand times better could spend half an hour on it. That’s… a problem. I guess if breaking our encryption was only feasible for superpower national intelligence agencies, it wouldn’t be a complete disaster. (Indeed, many people suspect that the NSA and FSB have already broken most of our encryption, and I wouldn’t be surprised to learn that’s true.)

But what I really want to say here is that since it may be true that P=NP—we don’t know it isn’t, even if most people strongly suspect as much—we should be trying to find methods of encryption that would remain secure even if that turns out to be the case. (There’s another reason as well: Quantum computers are known to be able to factor numbers in polynomial time—though it may be awhile before they get good enough to do so usefully.)

We do know two such methods, as a matter of fact. There is quantum encryption, which, like most things quantum, is very esoteric and hard to explain. (Maybe I’ll get to that in another post.) It also requires sophisticated, expensive hardware that most people are unlikely to be able to get.

And then there is onetime pad encryption, which is shockingly easy to explain and can be implemented on any home computer.

The problem with substitution ciphers is that you can look for patterns. You can do this because the key ultimately contains only so much information, based on how long it is. If the key contains 100 bits and the message contains 10,000 bits, at some point you’re going to have to repeat some kind of pattern—even if it’s a very complex, sophisticated one like the Enigma machine.

Well, what if the key were as long as the message? What if a 10,000 bit message used a 10,000 bit key? Then you could substitute every single letter for a different symbol each time. What if, on its first occurrence, E is D, but then it’s Q, and then it’s T—and each of these was generated randomly and independently each time? Then it can’t be broken by searching for patterns—because there are no patterns to be found.

Mathematically, it would look like this: Take each bit of the plaintext, and randomly generate another bit for the key. Add the key bit to the plaintext bit (technically you want to use bitwise XOR, but that’s basically adding), and you’ve got the ciphertext bit. At the other end, subtracting out each key bit will give back each plaintext bit. Provided you can generate random numbers efficiently, this will be fast to encrypt and decrypt—but literally impossible to break without the key.

Indeed, onetime-pad encryption is so secure that it is a proven mathematical theorem that there is no way to break it. Even if you had such staggering computing power that you could try every possible key, you wouldn’t even know when you got the right one—because every possible message can be generated from a given ciphertext, using some key. Even if you knew some parts of the message already, you would have no way to figure out any of the rest—because there are no patterns linking the two.

The downside is that you need to somehow send the keys. As I said in last week’s post, if you have a safe way to send the key, why can’t you send the message that way? Well, there is still an advantage, actually, and that’s speed.

If there is a slow, secure way to send information (e.g. deliver it physically by armed courier), and a fast, insecure way (e.g. send it over the Internet), then you can send the keys in advance by the slow, safe way and then send ciphertexts later the fast, risky way. Indeed, this kind of courier-based onetime-pad encryption is how the “red phone” (really a fax line) linking the White House to the Kremlin works.

Now, for online banking, we’re not going to be able to use couriers. But here’s something we could do. When you open a bank account, the bank could give you a, say, 128 GB flash drive of onetime-pad keys for you to use in your online banking. You plug that into your computer every time you want to log in, and it grabs the next part of key each time (there are some tricky technical details with synchronizing this that could, in practice, create some risk—but, done right, the risk would be small). If you are sending 10 megabytes of encrypted data each time (and that’s surely enough to encode a bank statement, though they might want to use a format other than PDF), you’ll get over 10,000 uses out of that flash drive. If you’ve been sending a lot of data and your key starts to run low, you can physically show up at the bank branch and get a new one.

Similarly, you could have onetime-pad keys on flash drives (more literal flash keys)given to you by the US government for tax filing, and another from each of your credit card issuers. For online purchases, the sellers would probably need to have their own onetime-pad keys set up with the banks and credit card companies, so that you send the info to VISA encrypted one way and they send it to the seller encrypted another way. Businesses with large sales volume would go through keys very quickly—but then, they can afford to keep buying new flash drives. Since each transaction should only take a few kilobytes, the cost of additional onetime-pad should be small compared to the cost of packing, shipping, and the items themselves. For larger purchases, business could even get in the habit of sending you a free flash key with each purchase so that future purchases are easier.

This would render paywalls very difficult to implement, but good riddance. Cryptocurrency would die, but even better riddance.It would be most inconvenient to deal with things like, well, writing a blog like this; needing to get a physical key from WordPress sounds like quite a hassle. People might actually just tolerate having their blogs hacked on occasion, because… who is going to hack your blog, and who really cares if your blog gets hacked?

Yes, this system is awkward and inconvenient compared to our current system. But unlike our current system, it is provably secure. Right now, it may seem like a remote possibility that someone would find an algorithm to prove P=NP and break encryption. But it could definitely happen, and if it did happen, it could happen quite suddenly. It would be far better to prepare for the worst than be unprepared when it’s too late.