since i succeeded in finishing my tasksᵀᴹ today, i'd like to write about a favorite math thing that i learned recently ... a tale of mathematicians proving, in some semi-rigorous way, that they have no clue how to solve a certain problem
okay so part one of this story is QSolv and QVerif (in the literature called P and NP). what are QSolv and QVerif? well there are rigorous definitions for these terms, but we're gonna disregard all that technical gobbledygook.
for our purposes, a problem which can be solved quickly by a computer program is said to be QSolv, and likewise a problem which can be verified quickly is said to be QVerif.
this definition has three missing parts:
-
what is a problem? what is solving a problem?
-
what is verifying a problem?
-
what does quickly mean?
by problem i mean essentially anything you might want to write a computer program to do, such as trying to compute the quickest route from address A to B (think google maps). by solving a problem i mean writing a computer program to do it
by verifying a problem i mean checking that a presented solution is correct. for instance, checking that some chosen route between addresses A and B indeed is the quickest one
by quickly i mean ... well, let's just not worry about that.
a problem which is famously in QVerif but probably not in QSolv is map coloring (in the literature called graph coloring). the goal is to write a computer program which could look at a map and, if proverbially given a small handful of differently-colored crayons, could use the crayons to color each region of the map (ie, countries, oceans, provinces, etc, not including areas that contain countries/oceans/provinces/etc, such as continents). specifically, the program must color the regions such that every two adjacent regions have a different color: if they're touching each other on the map, then they're not allowed to be given the same color.
performing this computation is famously hard: algorithms exist for it, but they are all slow in the sense which i refused to define. no fast algorithm has been found for map coloring, and it's not unlikely that the problem is actually impossible to solve quickly (ie, is not QSolv). on the contrary, note how easy it is to verify: given a colored-in map, you can check if the solution is correct by simply making sure that all adjacent regions do indeed have different colors. map coloring is QVerif
some believe that map coloring is not QSolv, but it's not known for sure. in fact, it's not known if there's any algorithm which is QVerif but not QSolv. if there is none, then QVerif = QSolv; any problem which can be verified quickly can be solved quickly. (in the literature this conjecture is called P = NP)
this conjecture is unsolved and famous and consequential and blah blah blah, but that's not what i'm here for. i want to exhibit a fun result regarding why the QVerif = QSolv conjecture is hard to close
so, for some reason mathematicians have taken an interest in so-called oracle computer programs (in the literature oracle turing machines) which are like normal computer programs but also have magical ability (called an oracle) to quickly solve some problem of our choosing
for example. we could think of an program that has an oracle which can tell if, when the program is about to color in a region on a partially-colored map, doing so would make it impossible to fill out the rest of the map in accordance with the map coloring problem. having this oracle would make it easy to solve map coloring quickly: color regions arbitrarily, but avoid coloring a region if the oracle says not to.
but why am i talking about oracles anyway? well, note that in some sense oracle programs are not really that interesting. an oracle program is just a program which takes as input an oracle. ... and we're already used to programs than can take input. big whoop!
accordingly, most things we can say about computer programs hold also for oracle computer programs: the math is said to relativize (ie, remain true when it is made relative to an input oracle). this is maybe not so surprising because, as said, an oracle is ... just an input
but here's the thing: the QVerif = QSolv conjecture doesn't relativize
it is known that for one choice of oracle O₁ we have that QVerif = QSolv over the class of O₁-oracle computer programs, but for a different choice of oracle O₂ we have that QVerif ≠ QSolv over the class of O₂-oracle programs
what this means is that it's in principle impossible to prove that QVerif = QSolv or that QVerif ≠ QSolv by means of any technique that relativizes, because that would entail respectively that QVerif = QSolv over both O₁- and O₂,-oracle programs or that QVerif ≠ QSolv over both O₁- and O₂-oracle programs, and both possibilities are false
and as stated most theory regarding computer programs (all of it, as far as I know) relativizes, because, well, an oracle is just a program input
this means the understanding we've built of computer programs is useless for proving whether QVerif = QSolv and that we'll need some fundamentally different way of approaching the problem in order to solve it
neat, i think!
little disclaimer: i could be exaggerating a with the whole "all of our understanding of programs is now useless" shtick. as far as i understand this actually is true, but it's possible that there are many non-relativizing theorems that i just don't know about!