They should have sent a complexity theorist

October 30, 2014

My O(1) readers are probably restlessly wondering where I’ve been, how I survived Israel’s freakishly sweaty summer, and what’s up in general.
Well, the truth is, I did manage to sweat under the Mediterranean sun, but most of the summer I spent in the United States. The official reason, given to the consulate and on my visa documents, was to do a project on “jump-starting a recent protocol on infinite randomness, using quantum-mechanical experiments”. The visa was approved, but I doubt that the people who stamped my passport understood what it was all about; hell, even I didn’t really know what I was going to do. I therefore dedicate this post to the men and women of the not-so-lubricated bureaucratic machinery that made my trip possible, in hopes that it will teach them all they ever wanted to know about unbounded randomness expansion using untrusted quantum devices, but were too afraid to ask. (Further dedication goes to Scott, who kindly took me under his wing and oversaw the project).
(The following post isn’t really technical, but feel free to skip over parts you don’t understand; there’s zounds more text that doesn’t require any fancy quantum mechanical stuff).

Randomness is important in life. For example, the optimal strategy in rock-paper-scissors is to pick each option with probability 1/3rd. This might seem easy, but it isn’t: humans are quite bad at imitating random sequences or won’t do so even if they know it’s best for them (best for them in theory; but then, what else is there?). It’d be much better if we had an infinite sequence of random bits that we could use whenever we wanted to. How do we go about getting such a sequence?
Ask any physicist, and she’ll tell you, “why it’s easy! Use quantum mechanics!” And indeed, quantum mechanics seems to be the place in nature where randomness comes not from a lack of prior information for us humans (i.e, a coin flip is random because we don’t know its precise position or the precise flipping force or the precise air pressure and currents), but is inherent in the physical reality itself. For most part, most reasonable “hidden variable” theories – theories in which the randomness observed in experiments stems from quantities that *are* deterministic, but we just don’t know them – have been ruled out.
So, the easiest way to get random bits using quantum mechanics is to take a quantum state that is in superposition – say a photon with both horizontal polarization (represented as the qubit |0 \rangle ) and vertical polarization (represented as the qubit |1 \rangle ) – and just measure which one it is. Thus, the overall state of the photon is the superposition \frac{1}{\sqrt{2}}(|0 \rangle +|1 \rangle), and measuring its polarization yields |0 \rangle with probability 0.5, and |1 \rangle with probability 0.5.
So far so good. In an ideal world, we would be done here. We’d build a nice small black box with a large red button on top. Every time we press it, the box would create a superposed photon, measure it, and output the result. Infinite bits at the press of a button.
But alas, we do not live in an ideal world, and most of us, while avid rock-paper-scissors players, do not have the necessary equipment or training to build quantum mechanical boxes. Of course, in this capitalistic global entrepreneurship enterprise world we live in, this isn’t much of a problem – we can always count on the market adjusting to the needs of the people, and companies selling quantum mechanical random number generators will sprout up like mushrooms after the rain. Hey, they already have.
The problem with these companies is that you can never quite be sure that they are honest. How do you know that they aren’t selling you only a pseudorandom number generator, which uses a deterministic algorithm and a small random seed? There are statistical tests you can run on the output, but we don’t know yet if it’s possible to discern between a pseudorandom output or a truly random output in reasonable time. If they are cheating you in this way, then your entire “random” sequence is vulnerable.
Further, even if the company you bought your box from did give you truly random bits, how do you know that they were created on the spot? Perhaps the company generated a gigantic random string back in their HQ, and just put it in your box. Every time you press the big red button, you get a new bit out of that string. The output is indeed random, but it wouldn’t be secure – the company could sell information about your random bits to the highest bidder, and you would face a gratuitous defeat in the rock-paper-scissors nationals.
These two problems apply to any true random number generators, but if you are using quantum ones there is yet another issue: even if the company did generate the bits on the fly, they could still get information on your bits by quantum entanglement. In a jiffy, instead of creating a single photon in the state \frac{1}{\sqrt{2}}(|0 \rangle +|1 \rangle), they’d create two photons in the entangled state \frac{1}{\sqrt{2}}(|00 \rangle +|11 \rangle): a superposition of “both photons have horizontal polarization” and “both photons have vertical polarization”. One photon they’d put in your box, the other they’d keep for themselves back in their HQ. The rules of quantum mechanics then say that when you press the big red button and the box measures the state – say you got a |1 \rangle – then when the company measures their photon, they also get a |1 \rangle . They always get what you got, and again, your information is not secure. This does not involve any communication between the box and the company – it would work even if you put it in an underground vault in Andromeda – its just a peculiar property of quantum states.
So right now things are looking pretty grim: there’s this wonderful startup idea – to produce random bits using quantum mechanical phenomena – but buyers don’t have a guarantee that the companies aren’t cheating them. And we all know where that leads to.
But not all is lost! For if we are allowed to tweak the way our quantum mechanical boxes operate, we can build a statistical test that has nothing to do with ordinary randomness / pseudorandomness tests, and that test guarantees honesty. Boxes which pass the test must produce random bits; they produce these bits on the fly; and they can only have a tiny amount of entanglement with the company HQ, giving the company almost no information about your random sequence. A magical cure for all our maladies!
To see how it works, we’ll look at the famous CHSH game. In this game, Alice and Bob are two players who play cooperatively in the following very realistic scenario: they are both put into separate rooms, and each one is presented with a bit: Alice is shown X, and Bob is shown Y. Based on that bit, they have to output a bit themselves: Alice outputs A, and Bob outputs B. They win the game if

A \oplus B = X \wedge Y.

They are allowed to decide on a strategy beforehand, but once they are put into the rooms, they cannot communicate.
Suppose that X and Y are chosen uniformly at random, that is, they each have a 0.5 probability of being 0, and 0.5 probability of being 1. What is the optimal strategy for Alice and Bob – the one which gives them the highest chances of winning?
Here is one strategy: Alice and Bob ignore the inputs X and Y completely, and always both output 0. So A \oplus B = 0, and this is equal to X \wedge Y for 75% of the cases: whenever either X or Y is 0. The success rate for this strategy is 0.75.
It can be shown that there is no better deterministic strategy (you can do the truth table, if you want). But then there is also no better probabilistic strategy, since it would just be a convex combination of deterministic ones. So the best Alice and Bob can do, if they are not allowed to communicate, is to win 0.75 of the time.
Well, classically, that is true, but it is not true if they are allowed to share quantum resources. Specifically, if they each have one photon of the entangled state \frac{1}{\sqrt{2}}(|00 \rangle +|11 \rangle), then once they are shown the bits, they can measure their photons from a set of agreed upon non-trivial measurement, and output whatever their measurements give. Their outputs will be completely random (individually), but correlated with each other. If they choose the right measurements, they can boost up their win rate to 0.84 (!). This is the best, known strategy that does not involve communication between the players. (For a billion details, see here)
But wait, there’s more! The CHSH game is robust, in the sense that if Alice and Bob have a success rate very close to 0.84, then with high probability they are using a strategy that is not very different than the known optimal one. This means that the bits they output are very close to random (what does it mean “very different strategy”? There is a formal definition which we won’t go into here, but as an example, the strategy “0.01 of the time output 0 and 0.99 of the time use the optimal strategy” is very close to optimal; so is “measure in a slightly different way than the optimal, so the correlations are changed just a bit”).
We now have a test for our random number generator box. Instead of having one big red button which measures a \frac{1}{\sqrt{2}}(|0 \rangle +|1 \rangle) photon, we’ll ask the manufacturer to give us two boxes. These boxes will act as Alice and Bob: they will accept as input two random bits, and output bits of their own. We can play the CHSH game many many times, and measure their success rate: if its very close to 0.84, then they cannot have coordinated their outputs in advance; they cannot have used a deterministic algorithm; and the company cannot have a lot of information about the output (ok, we haven’t shown this here, but in a jiffy: in order to have information about it, the company needs to be entangled with the two boxes; but almost all the entanglement is “used up” in order to boost the win rate from 0.75 to 0.84, so “nothing is left” for the company to know).
This is what is commonly called (well, common among the relevant community) as “certified randomness”- the CHSH game can be used to test the randomness of our devices (in fact, there is a broad class of “XOR games” that can be used – games which are similar to the CHSH, but may involve different requirements or more players).
We would really like to say that we are done here, but the keen eyed among you must have already noticed the bug in the plan. We have a pair of boxes that, when given two random bits, output two correlated bits. We need random numbers just to test if a random number generator works. What’s worse, we put in two, and get back less than two. We are actually consuming bits in the process! Alas, the market for quantum random number generators is much more blooming than the one for quantum random number extinguishers.
But not all is lost! If we are allowed to tweak the inputs to the pair of boxes, we can create a test that uses less random bits than it puts out. The main concept is as follows: we still let the boxes play a lot of CHSH games, only now, instead of having totally random X and Y (requiring 2 random bits per game), we alter the input a bit: Most of the time, we’ll have X = 0 and Y = 0. This is like a “dud” game, and if the boxes anticipate this, they can potentially output 0,0, as described before. However, for a very small percentage of randomly selected inputs, X and Y are selected at random, as usual; these are called “real” games. On these games, if the boxes are to perform with high win rate, they have to be honest – they have to actually play the winning CHSH strategy. The point is that the real games are chosen at random, and the boxes have no idea which ones they are. If they play assuming the X = 0, Y =0 dud games, they run the risk of falling on real games and winning with only 0.75 probability. The trick of these tests, then, is to find out how to distribute the real games among the duds, how strict to be when deciding if the boxes pass the tests, etc. This type of test is called a randomness expansion protocol, in that it takes requires a certain number of bits (for choosing which games are duds and which are real, and also for the inputs of the real game), but outputs more than was used. Both polynomial and exponential expansions have been developed, and more recently, even infinite expansion! The latter is generally done by back-feeding the output as input for the boxes, but the details are a bit complicated, especially the whole “proving that it works against entangled opponents” thing. It means that you can start with a finite string of randomness (say, one you obtained from a trusted source), and expand it into one as long as you wish! There will be errors, but they grow exponentially smaller the more initial bits you use.
Personally, I think this whole thing is really cool. If you trust your quantum box, then generating an infinite random string is as easy as |1 \rangle |2 \rangle |3 \rangle . But even if you don’t, you can still obtain an infinite random string. It requires a bit more pyrotechnics, and it requires you to somehow obtain a small number of random bits elsewhere, but it’s possible. And actually, despite the fact that we called our boxes quantum, they don’t necessarily have to be. All they have to do is win the CHSH game with probability close to 0.84. Quantum mechanics isn’t the final say in physics; maybe we’ll find better theories which supersede it. Any mechanism which wins better than the classical 0.75 can be used in this type of protocol.
And that’s pretty much the gist of “a recent protocol on infinite randomness, using quantum-mechanical experiments”: a method to use untrusted quantum boxes in order to take a small number of random bits, and turn it into an unbounded number of (nearly) random bits. That’s it.
Where does your humble servant come into play in this whole ordeal? A very tiny part, and that’s the “jump starting” in the clause “jump starting a recent protocol on infinite randomness”. An initial random string is needed in order to run the protocol, and the question is: how large is that string, as a function of the errors you are willing to tolerate? (there are plenty of places where errors accumulate, but I skipped the discussion of errors and robustness because it really only complicates matters, and it’s complicated enough as it is).
So that’s what I set to find out. I basically gave bounds for various expressions described in the protocols which relate to the number of random bits outputted. The answer? Well it depends on the error, of course. But, let’s say, the bound I got is on the order of O(1,000,000) for reasonable error. For the rest, you’ll have to read my paper, I guess.

Microwaves and birthdays

September 10, 2014

Without doubt, one of the largest differences between the USA and Israel is the microwave ovens. Whereas almost all microwaves I encountered in Israel had either analog rotary timers or preset “30 sec or 1 min” buttons, here in the states there is an overwhelming prevalence (100% of an astounding three cases) of numpad microwaves.

This is not advertisement

This is not advertisement

Seemingly, all you have to do is put in the number of minutes / seconds you want to heat, and fin, you are done.
But wait; is it minutes, or seconds? What happens if I put in a three or four digit number? Do I have to be an arithmetic expert to operate my microwave?
In what can only be stated as the “non-continuity of microwave space-time”, the input parsing is simple: if you put in xx:yy, it will run for xx minutes, and yy seconds. Simple and intuitive. The thing is, nothing constrains yy to be smaller than 60. 1:99 is as valid input as any, and will indeed run for 1 minute and 99 seconds (=159 seconds total). 2:00 is also a valid input, running for 2 minutes, 0 seconds (=120 seconds total).
This is the natural way to handle user input, and I totally approve of it, if only for the programmers’ and designers’ sake for not handling annoying details. There is a nice time discontinuity when you plot the actual cooking time against the numbers you punch in, if you arrange them in lexicographical order:

microwave_60

Starting from 60 seconds cook time, the user has two choices of how she wants the input to be shaped, rather than just the feeble one available with a rotary timer. This is in agreement with the USA’s enhanced economic and political freedom; it is no wonder that these microwaves are more prevalent here (as for me, you can find me standing dumbstruck in front of the machines, trying to decide which number I should punch in).

As the title of the above plot suggests, it is interesting to see how different minute lengths affect our options. The shorter the minute, the more overlap there will be, and the more options you will have, until finally, for SECONDS_PER_MINUTE = 1, we have 100(!) different options of input. Here is the example for a 30 second minute:

microwave_30

On the other hand, given that we work in base 10 and that our two digit numbers only go up to 99, if we had a longer minute (and kept the input method the same, allowing only two “seconds” digits), we would have gaps:

microwave_200

Not every desired time can be reached; we will likely not be seeing any 200 second minutes in the Imperial system any time soon.

This whole ordeal reminded me of a wonderful fact I stumbled upon that has to do with discretizing age. Consider the standard high school algebra question: Albert is X years old, and his son Jorgenhausfer is Y years old. When will Albert be twice as old as his son?
The question is easy, but one can also ask for how long Albert is twice as old as his son. It turns out that Albert will be twice as old as Jorgenhausfer for exactly one year, but that time period may be split into two sections, depending on their birthdays! I can do no better justice to the issue than the discussion given here:
http://www.math.brown.edu/~banchoff/twiceasold/

Do not track

August 23, 2014

“Home is where the wifi connects automatically”.
The question remains to be asked, how does it know to connect automatically? Well, of course, the computer saves a list of network names (or other identifiers) and their passwords, and tries to connect when it sees one it recognizes. I bet the passwords are saved in plaintext, too, but you should know better than to use the same one for your wifi and for your bank.

Anyway, Ubuntu is no exception. This is a laptop, and I don’t have a GPS that records my coordinates at all time, so it’s still interesting to see that if you know enough about me and obtain access to my computer, you can track my position with fair accuracy. Here is a list of networks I’ve connected to, by default sorted by date.

wifi_networks

Take a look at the connections. Can you reconstruct a map of where I’ve been as a function of time? Try to do so now.

.
.

All done?

.
.

I think the average user can, after a bit of thinking and googling, make at least some sense out of the somewhat-cryptic names. Certainly he will arrive at some route of the form: Technion -> Boston/MIT, with a stop in Europe. Here, let’s do it together. Start from the past:

ISRAEL-RAILWAYS – well, that’s easy. I sometimes take the train to the Technion, so no biggy there. Just two months ago I still had classes!
TechPublic, eewifi – TechPublic is, of course, the Technion’s campus-wide public wifi. eewifi is the same, for the department of electrical engineering. So a month ago I was certainly on campus.
caXXXyy – these are a bit a tricky, and require prior knowledge. “Canada” is the name of the dorms I live in. Specifically, ca94305 is my own apartment wifi. So after having connected to the public Technion wifi for the last time, I was at my dorms. But I haven’t been there for the past 29 days. It must be summer vacation.
Bezeq-n_6202 – my house wifi. Ok, you had no chance of guessing that :). But wait! Last time used, 27 days ago? Oh my, where have you been all this time?
Swisscom – that’s a Swiss communication company. How did that happen? Indeed, on my way to Boston I had a connection in Münich. Not quite Swiss, but close enough.
Loganwifi – Logan is Boston’s airport. I’ve been here for 26 days!
percher – stayed at a friend’s for a while. That might take a bit of digging. Seeing as it was used 22 days ago, and I arrived 26 days ago, one can conclude that I’ve stayed there for 4 days.
HMS public – unfortunately, not Her Majesty’s Ship, but Harvard Medical School. Went there for a visit.
MIT – ‘nough said. I spend most of my time here.
StataCenter – if it weren’t enough that you know at which institution I spend most of my time, you now also know the exact building. Oh well; as seen in a previous post, my wikipedia editing IP gives about that much information anyway.

How do you that I spend most of my time connected to the last two networks? Since it’s unlikely that I’ve been without internet access all this time (what with the blog posts and wikipedia edits and all), the fact that there are no networks in between MIT and StataCenter, and, say, the Percher / HMS ones, indicates that I’ve repeatedly connected to them, thus refreshing their status and putting them at the top of the recently used.

By the way, the Stata Center is a really cool place.

For me this isn’t confidential information – here, I’m posting it online. But I suppose that for those of us who wish to remain anonymous, for whatever reasons, wifi connection history is just one more problem to worry about. And seeing that my own connection history had entries from over a year ago, it stays with you for quite a while.

(footnote: I have intentionally omitted a network from the list, of the place I’m currently staying; I do not know if the owner would appreciate having the network name put here. This does not change the above analysis)

Credo

August 14, 2014

I believe there is life outside of Earth. There are many planets in the observable universe, and thirteen billion years is a long time. I doubt, however, that DNA has much to do with it.
I believe P ≠ NP. How else could it be so hard to prove? Relatedly, even non-standard computing architectures, based on relativity, condensed matter, and quantum physics, have not yet breached it.
I believe in a Singularity. Eventually we will find out enough about individual consciousness to be able to bend it to our will; our bodies, too, will be under our control. What field in life hasn’t succumbed to engineering?
I believe it is possible to understand the world using physics. It seems unlikely (and despairing) to me that the world does not operate according to a set of rules that can be formally described; and while claiming that humans will eventually find out these rules is a strong statement, I look at what we have done so far in so little time, and cannot but be optimistic.

I believe all of these things, and many more. So Gauss-dammit Internet, if you tell me “This policeman pulled over a speeding couple – you won’t believe what happens next!” one more time, I swear I will personally go over there, and pull the plug on you myself.

My first Wikipedia edit

August 6, 2014

Hurray! Yesterday I made my first Wikipedia edit. Years of meticulous dedication and research – in areas ranging from physics and mathematics to philosophy and absurdism – have finally paid off. I can only imagine all the wonderful places I can go from here. True, I spent about ten hours writing the whole thing, but certainly this is the starting point of a majestic career. The culmination of my open souce academic life can finally be seen here:

http://en.wikipedia.org/wiki/GCT

Yup – I added the 4th line, disambiguating geometric complexity theory from other, non-interesting matters, such as Gwinnet County Transit, or the ISO 639-3 code for a German dialect. Needless to say, not 10 minutes after hitting “save” (9, actually), my contribution was edited, trimmed of capital letters and a stray period. The wheels of perfection are grinding hard at work, I guess.

Your weakness is not your technique

July 16, 2014

[Pre-post post-note: an amazing alignment of the stars! Just hours after writing this, I came across the much stronger Lockhart’s Lament. A must read, I daresay.]

Professors, teaching assistants, professional exam-writers, lend me your ears; I come to fix the exam, not to praise it. The exams that students solve, live after them; the results are oft interred with their bones.

This week I had my final examination in quantum mechanics 1. It had three open questions, two of which can basically be reduced to something as follows:
1) Apply the second order correction according to the scheme you learned in class to the following perturbation: …
2) Diagonalize a 3×3 matrix. Using the basis transform, express some vectors as a linear combination of other ones. Use these to obtain a wavefunction and integrate it.

In essence, the questions were just (very) technical mathematics exercises, not-so-cleverly disguised with an excuse for a physical background. This type of question is exactly what keeps me off my ass when studying for these exams. Is this a test in integration? A test in algebra? I already had those last year. I want to do some physics! In this case, converting the physical premise to the mathematical relations, or identifying the right equation in the formula sheet definitely didn’t count as “physics”.

As an analog, imagine a computer science class; over the semester, you went over the whole deal – sorting, graph flow, DFS/BFS, pattern matching. Now comes the final exam, and as you open up the questionnaire, your eyes grow wide with despair.

Question 1: Apply the quicksort algorithm to sort the following array. Make sure to write the complete derivation; a final answer only will not be accepted:
318, 330, 44, 304, 181, 472, 80, 245, 185, 45, 250, 285, 404, 370, 430, 194, 273, 180, 233, 146, 132, 473, 331, 291, 265, 444… [74 more items omitted]

What, isn’t that a legitimate question? After all, you learned about the quicksort method in class; here is your chance to show that indeed you know it, earning your exam points in earnest.
Oh, what’s that? It would be a dull and error-prone thing to do, that doesn’t really show the student’s proficiency in algorithms? It would be much better to have the student invent a similar but distinct algorithm to show that they grasp the concepts? In fact, inventing new algorithms and proving correctness and bounds is what actually happens in algorithms tests?!

It’s certainly possible to ask interesting questions, that actually require invoking the student’s physics-neurons instead of just the high-speed-integration ones. In fact, we had plenty of those in our classical mechanics lessons. And they might involve some difficult mathematics in order to get the right answer.

But when I compare my classical mechanics 1 exam with my quantum mechanics 1, I notice that the former’s (great) difficulty was in understanding what the hell I needed to do, while the latter’s was in diagonalizing quickly and keeping track of the trillions of minus signs, \sqrt{2}‘s and \hbar‘s. Admittedly, I am no expert, but for some reason I am quite certain that it is not quantum mechanics that is at fault here – certainly there is no dearth of physical reasoning which can also be backed up by mathematics (see Feynman vol. III, for example).

Professors, teaching assistants, professional exam-writers, lend me your ears! Cease the technical absurdity, and return physical insights to your exams! They shall make your students all the wiser, in addition to sparing them the sprained wrists and CTS. And if you claim that the exam should portray only what has been taught in class; well, what exactly have you been teaching then?

Zero knowledge in the real world?

July 5, 2014

[Written under the influence of QCSD]
Not so long ago, I happened to watch the totally-accurate-in-every-possible-way film, “Travelling Salesman”. tl;dw: a squad of government-hired mathematicians are finally able to prove that P = NP, giving the state the power to answer every important computational question they can imagine (aka rob banks and fight terrorism). But when requested to hand over their findings, the mathematicians begin to doubt that they are doing the right thing (as opposed to, say, publishing the results and letting everyone enjoy the spoils). A difficult question indeed – unleashing a polynomial algorithm for an NP-complete problem does imply breaking almost all cryptosystems in use today, in addition to creating better flight plans for cross-country salesmen. Definitely, if we ever prove P = NP, the history of mankind will be divided into distinct “before” and “after” phases.
But what if the mathematicians aren’t interested in breaking ciphers, but just want their well deserved fame and glory for solving a very hard problem? It is here that I wonder if the computer science and mathematics communities are ready for non analytical proofs as part of science-doing, and not just as part of complexity classes.

A brief word of explanation first. The rigour with which results are demonstrated differs in various academic fields. In sociology and medicine, statistical significance is basically all there is, so saying “there is a less than 2% chance of our hypothesis being wrong given the clinical tests” is pretty darn good. In experimental physics, too, we can never be more sure than our measurement error. However, in theoretical physics, mathematics and computer science, an analytical proof, filled with lemmas, propositions and an abundance of silly symbols, is needed. Indeed, even computer-assisted proofs, ala the Four Color Theorem, are frowned upon and looked at with a wary eye.
One reason for the wariness of computers, of course, is that computer programs and hardware naturally have bugs, and who’s to say that the calculation was correct? Before stating that something is an irrevocable mathematical truth, one must be sure! Of course, humans make mistakes when writing and reading proofs as well; a small bug hiding in a 300 page manuscript might be able to evade all the reviewers and find itself in publication, impostering as a profound truth.

If printed mathematical texts can be wrong (god forbid!), why not accept that fact and welcome probabilistic proofs – proofs that are probably correct (why probably? because there is randomness involved), up to an error as small as we choose. Computer science already has this well defined – the BPP, MA, SZK, and PCP complexity classes, for example – but what about real-life science? (gee, now I know why Scott complains about naming conventions in complexity theory…)

I propose the following scheme: say our mathematician Bob wants to show the world that he has proved P = NP (and therefore, also P = co-NP), and in fact has discovered an algorithm for solving NP complete problems. However, he does not want to give away the algorithm, just show that he knows it. He thus set up a private server which handles incoming requests, and starts playing a sort of zero knowledge interactive proof protocol with the mathematical community. The community sends him boolean expressions of increasingly larger size n. For each expression s: if s is satisfiable, the server replies with a satisfying assignment. If not, the server replies with a proof that verifies that there does not exist a satisfying assignment. In other words, the server replies whether s is in SAT or in SAT-complement, and either way provides a proof for it. These are NP and co-NP complete problems, so solving them in polynomial time shows that P = NP.
Now, all currently known algorithms take super-polynomial time to run. So if Bob only had access to known algorithms, he would not be able to solve the problems as n becomes larger. However, assuming that the polynomial in Bob’s algorithm isn’t of very high degree, and that its leading coefficients aren’t gigantic, he can answer the questions even for large expressions. Knowing Bob’s computational power, the community could very well know if he runs in exponential or polynomial time, proving that he does not lie.
Where does probability come into play? Well, it may be that Bob is guessing. Bob might be a fraud, and whenever he gets a boolean expression, he randomly generates polynomial-sized certificates, and sees if they prove satisfaction / unsatisfaction of the expression. Of course, his chances of succeeding are exponentially small as n gets larger, but for every finite number of tests the community presses upon him, there is always a finite chance that he gets it right. Also, even if Bob runs a deterministic super-polynomial algorithm, for some lucky expressions he might be able to get the right answers quickly** (see problem below), so the community itself needs to randomize the expressions they send.

As it is, will this kind of “proof” catch on among fellow mathematicians? I doubt it. Even if you exclude the whole “his algorithm runs fast so it must be polynomial” problem, I think we are still far off from a more ideal world: one that has, in addition to science journals, an international array of servers dedicated to interactive, zero knowledge, and other probabilistic proofs (actually, under plausible assumptions, most those can be de-interactivated, no?), representing those theorems and propositions which we almost know are true; we’re just missing an ε.

Notes on note:
Note and future thoughts: The solution I have given is a bit awkward, in that it requires Bob to solve a lot of NP and co-NP problems, instead of just giving a normal zero knowledge proof to the expression “P = NP”. Suppose Bob only knows an algorithm for SAT. Can he encode it in such a way so that he can prove that it is indeed a polynomial algorithm for SAT, but that no one else will be able to use it? This is different from the zero-knowledge that I know of, in the sense that we aren’t just asking whether a specific string is in some language (aka an expression is in SAT) – we want to show that a string (program / proof) has some properties, without showing that actual string. If there are any real complexity theorists reading this, please do leave a comment.

Note to note to note: I recall hearing somewhere about encrypted zero knowledge computation – that is, Bob could send his algorithm to the community in an encrypted form, so that the community will do the calculations but have no idea what they are doing (and the computation will be different for each input, so they will not be able to reproduce the algorithm on different inputs than what they already asked). First of all, this is cool. Second, this will help base the fact that the algorithm is polynomial – but still won’t get around the lucky guesses that Bob could make if he frauds up a super-polynomial algorithm.

Too cool not to note: On the subject of “errors in human-reviewed manuscripts”: if rigour and no-chance-for-error is what you are looking for, why not submit formal proofs to the leading journals? This would constitute a sequence of lines; the first few would be the axioms, and the rest would be logically irrefutable inferences from the previous lines. The last would be the theorem you want to prove, stemming irrevocably from the axioms. Any monkey / mathematician / computer could go over these proofs and verify that they are true, no chance of error involved. Of course, I’m not the one to think of this idea, many have done so before me; for example, the QED manifesto (now, that’s a name I could live by…).

**Problem with solution: I assume here that expressions the mathematical community sends are, probabilistically, hard enough to solve with modern SAT solvers. I know that some of these solvers can work very well in some cases, failing miserably only, for example, on expressions with just one satisfying assignment. In this specific case, the assumption is that enough of the expressions only have one satisfying assignment (I seem to recall that this applies to a lot of boolean expressions).


Follow

Get every new post delivered to your Inbox.

Join 51 other followers