Skip to content

Black Versus White Boxes

February 8, 2014


What is better than how (?)

cauer
History of filters source.

Wilhelm Cauer was a German mathematician and engineer who worked in Göttingen and the US between the two world wars. He is associated with the term “black box,” although he apparently did not use it in his published papers, and others are said to have used it before. What Cauer did do was conceive a computing device based on electrical principles. According to this essay by Hartmut Petzold, Cauer’s device was markedly more advanced and mathematically general than other ‘analog devices’ of the same decades. He returned to Germany in the early 1930’s, stayed despite attention being drawn to some Jewish ancestry, and was killed in the last days of Berlin despite being on the Red Army’s list of scientists whose safety they’d wished to assure.

Today Ken and I wish to talk about black boxes and white boxes, no matter who invented them, and their relation to computing.

blackbox
src

In computing a black box is a device that given an input returns an output, but we do not get to see inside the box. We only get the output, we do not get any idea how the box computed the value. In a white box, we get to see all of the steps taken in computing the output. Probably better names would be an opaque box and a transparent box. But black and white are the most popular names.

bwbox
BB/WB testing source

The devices built by Germany’s great computing pioneer Konrad Zuse can be viewed as “white boxes,” because he devised an entire programming formalism to control them. He even wrote a computer chess program in his Plankalkül, in 1941 long before the work of Alan Turing and Claude Shannon and others, but chess was hardly a priority in those years.

What and How

Another way to think about black and white boxes is to notice the parallel with “what” and “how.” In English we use “what” to mean the goal, and “how” to mean the method for reaching the goal. A quote from a site on selling products is interesting:

What” is the end goal, it’s directional. “How” is the journey…

We have edited this slightly—caps to bold.

A Measure Of Complexity

I propose that we can use the issue of what vs. how as a measure of complexity. Problems that force us to look inside a box are much harder—if not impossible—then those where we can avoid this.

{\bullet } Physics:

We see the what/how divide all the time in physics. The famous Newtonian law of attraction between two masses,

\displaystyle  \frac{Gm_{1}m_{2}}{r^{2}},

is a perfect example of what. Issac Newton had no idea why this works—how it works. Albert Einstein, in his discovery of General Relativity, showed that the Newtonian formula was only an approximation. His field equations replace the above to explain more accurately the what of how gravity works. The theory successfully predicts many effects that show it is a refinement of Newton’s. Some are: gravitational redshift, light bending by gravity, and the anomalous perihelion shift of Mercury. I would argue that we still have no idea of how gravity works. Yes general relativity says that masses cause space-time to curve, and the curvature directs their motion. In particular, this helps explain how gravity acts at a distance. But does this really answer the how question?

The greatest example for the hundred years since general relativity has been quantum mechanics. No one knows how it works, but it yields incredibly accurate agreement of measurement with prediction for quantities on incredibly small scales. There are many competing white-box attempts to explain it, but this black-box slogan still holds sway:

ShutUpAndCalculateMug
Product source

{\bullet } Cryptography:

We see what vs. how all the time in cryptography. Indeed many crypto results view protocols as black boxes and use this routinely. Sometimes there are cases where the how is important, where white boxes are needed in crypto. But these are the exception, and usually are the harder cases.

The physical idea of devices as black boxes enters into quantum protocols. Even there, some theoretical arguments can be defeated when it comes to implementations, if light can be shined inside the box to make it white. This is quite literally the basis of an attack with a “blinding laser: that we wrote about here.

{\bullet } Programming:

We see the what/how divide all the time in programming. The whole point of abstraction, of modules, of object-oriented programming is to hide the how from us. Programmers are happy to use code written by other programmers, the what, without any understanding of the how. It is vital that a change in the how not disturb many other components in a software system that are relying on the what.

{\bullet } Mathematics:

We also see the divide in mathematics. We can use the famous classification of finite simple groups, this is the what. We need not, probably cannot, worry at all about the how. The number of experts in group theory that understand all of the how are few.

Yet applications abound of using this theorem. Right now there is great difficulty in understanding the volumnious development of intra-universal Teichmüller theory on which Shinichi Mochizuki’s claimed proof of the ABC Conjecture and several other conjectures is based. Some hope that further experience with the what of its implications will help to verify the how of Mochizuki’s proofs.

Lower Bounds and How

We see the what/how all the time in lower bounds in complexity theory. The difficulty is that in many lower bounds we must treat the computation as a white box. This forces us into the how situation which is much harder than when we can view computations as black boxes—the what case.

This shows up already with the simplest kind of circuit black box we can imagine, a comparator gate. It has two inputs {x} and {y}, and two outputs that just give {\max(x,y)} and {\min(x,y)}. The famous lower-bound theorem that circuits of these gates require {\Omega(n\log n)} size to do sorting, which is taught in many undergraduate algorithms courses, is often mis-recalled as applying to all kinds of circuits, Boolean or numerical, and to general machine models. However, in some such models it is false, as shown by the {O(n\log n/\log\log n)} upper bound of Michael Fredman and Dan Willard.

Consider a truly general circuit lower bound. All the results—all?—require a white-box view of the circuit. The whole reason that circuit lower bounds are so difficult is that we must argue, it seems, that the circuit cannot do something. And to do that we must get into the details of how a circuit can work. Sometimes the arguments that make full allowance for how do succeed, for example we can get lower bounds on monotone circuits and on constant depth circuits. All of these proofs require white-box arguments.

Consider a Turing Machine lower bound. These results sometimes can treat Turing Machines as black boxes. Turing’s original proof of the unsolvability of the halting problem did not depend on details of the machines. Okay this is a bit tricky. He needed that any such machines could be simulated, so he did get involved with the how. However, the details of how were not relevant to the core argument, just that there was some way to simulate the machine.

The same weak dependence on how is used in many other complexity results since Turing’s work. The usual diagonalization proofs use only weak information about the how. The myriad relativization results, typified by the existence of oracle sets {A} and {B} such that {\mathsf{NP}^A \neq \mathsf{NP}^A} but {\mathsf{NP}^B = \mathsf{NP}^B}, attest to the need for white-box understanding of computational efficacy.

Open Problems

Which side are you on—how do you read our ambiguous subtitle?

Perhaps there is a general way to morph black boxes into white, giving a theory that can provide “fifty shades of grey” in computation?

About these ads
28 Comments leave one →
  1. John Sidles permalink
    February 9, 2014 12:11 am

    Dick and Ken ask  “Black Versus White Boxes”: Which side are you on?

    Historian Lily Kay’s survey The Molecular Vision of Life introduces the reader to a vast “White Box” literature associated to the medical goal of healing-through understanding. Quotes to this effect include remarkably many quantum physicists:

    Linus Pauling (proposal to the of the Rockefeller Foundation, June 19, 1946)  “The methods of science have now become powerful enough to offer the promise of a successful attack on even the giant molecules, such as proteins, nucleic acids, and viruses, and on the interrelations and methods of interactions of these constituents of living matter. … Extremely important advances could be expected if the effective resolving power of the electron microscope could be considerably improved. … If it were possible to make visible the individual molecules of the serum proteins and other proteins of similar molecular weight, all the uncertainty which now exists regarding the shapes of these molecules would be dispelled.”

    John von Neumann (letter to Norbert Wiener, November 29, 1946)  [Irving] Langmuir asserts that a 2-4 year effort with strong financial backing should break the back of the problem [of observing molecular structure]. His idea of an attack is: very high precision x-ray analysis, Fourier transformation with very massive fast computing, in combination with various chemical substitution techniques to vary the x-ray pattern. In addition, there is no telling what really advanced electron-microscopic techniques will do. In fact, I suspect that the main possibilities lie in that direction. … The physiological implications are extraordinary, and they should receive a great deal of emphasis in the immediate future.

    Richard Feynman (lecture “There’s Plenty of Room At the Bottom”, December 1959)  We have friends in other fields — in biology, for instance. We physicists often look at them and say, “You know the reason you fellows are making so little progress?” (Actually I don’t know any field where they are making more rapid progress than they are in biology today.) “You should use more mathematics, like we do.” They could answer us — but they’re polite, so I’ll answer for them: “What you should do in order for us to make more rapid progress is to make the electron microscope 100 times better.”

    The near-identity of these three passages shows how prevalent White Box biomedical ideas had already become — among top-rank physicists at least — in the 1940s and 1950s! Needless to say, the White Box philosophy of Pauling, Langmuir, von Neumann, Wiener, and Feynman is nowadays the dominant paradigm of molecular, as exemplified by the Human Genome Project and its still-burgeoning successors.

    Now in the 21st century, a similar White Box paradigm is (arguably) coming to the fore in complexity theory, by essentially the path that Feynman’s reasoning suggests:

    Richard Feynman redux (“There’s Plenty of Room In the Middle”, 21st century)  We have friends in other fields — in simulation science, for instance. We complexity theorists often look at them and say, “You know the reason you fellows are making so little progress?” (Actually I don’t know any field where they are making more rapid progress than they are in simulation science today.) “You should use more complexity-class oracles, like we do.” They could answer us — but they’re polite, so I’ll answer for them: “What you should do in order for us to make more rapid progress is to explain the past five decades of Moore’s Law improvements in simulation capability, and show us how to sustain the next five decades of Moore’s Law improvements.”

    Here the common-sense point is that conditional complexity theory — by which is meant 20th century “Black Box” complexity theoretic results that are conditional upon unproved (and possibly unprovable) oracle-based complexity classes — may yield in the 21st century to an emerging oracle-free “White Box” complexity theory; whose results are seemingly tougher to derive (at least with present knowledge!) yet have the considerable practical advantage of being conditional only upon the axioms of PA/ZFC (etc).

    That is why a pair of Gödel’s Lost Letter columns that asked (in succession) “What is your favorite White Box/Black Box Complexity Theory Result?” would be read with interest by me and many!

    A starting-point for debate might be

    Resolved (for purposes of debate)  White-Box complexity theory (in which complexity classes are explicit) is in the 21st century likely to achieve a utilitarian advantage relative to Black-Box complexity theory (in which complexity classes are oracular), in the same sense (and for similar STEM reasons) that White-Box biomedicine (in which healing efficacy is appreciated at a molecular level) already enjoys a utilitarian advantage relative to Black-Box biomedicine (in which healing efficacy is determined via clinical outcome-oracles).

    Hopefully such a debate would catalyze plenty of thoughtful remarks on both sides. Which would be FUN and GOOD (for young researchers especially)!

    • rjlipton permalink*
      February 9, 2014 11:18 am

      John

      Thanks again for your thoughtful comment. I will talk to Ken about this very issue.

    • John Sidles permalink
      February 9, 2014 5:26 pm

      More Gödel’s Lost Letter discussion of Black Boxes versus White Boxes would be terrific.

      Michael Freedman’s article “Complexity classes as mathematical axioms” (2009) suggests (implicitly) some themes for at least one such GLL article:

      Complexity theory, being the metrical version of decision theory, has long been suspected of harboring undecidable statements among its most prominent conjectures. …

      While the techniques of diagonalization and oracle relativization have produced important separation results, for nearly forty years the most interesting (absolute) separation conjectures, such as P≠NP, remain unproven, and with the invention of ever more complexity classes, analogous separation conjectures have multiplied in number.

      With no prospect in sight for proving these conjectures (within ZFC) and the suspicion that some are actually independent, we propose considering them instead as potential axioms and looking for what implications they might have in mathematics as a whole.

      Concretely we can ask: What White-Box axioms might we embrace, that would require no changes whatsoever to the Black-Box Complexity Zoo?

      For example, might we specify a White-Box “Middle Earth” in which the Extended Church-Turing Thesis (ECT) is true, in the sense (for example) that the Standard Model of QFT is stated to be integrable with PTIME resources?

      This would naturally — yet provocatively … unite the mathematical challenge of proving the consistency/inconsistency of the White-Box axioms, with practical Black-Box challenges like demonstrating the feasibility/infeasibility of scalable ShorFactoring and/or BosonSampling.

      The discourse associated to this Black-versus-White challenge (as said above) would be FUN and GOOD for young researchers especially. That’s one way to appreciate Michael Freedman’s article, at any rate.

    • John Sidles permalink
      February 11, 2014 6:41 pm

      Here are a couple more references relating to “White Box” (unconditional) versus “Black Box” (conditional) STEM research.

      The first is from “Interview with Jean-Pierre Serre” (Notices of the AMS, 2004)

      As for the choice of questions made by the Clay Institute, I feel it is very good. The Riemann hypothesis and the Birch and Swinnerton-Dyer conjecture are rightly there.

      The Hodge conjecture, too, but for a different reason: it is not clear at all whether the answer will be yes or no; what will be very important will be to decide which. (I am hoping, of course, that it will not turn out to be undecidable. …)

      The P=NP question belongs to the same category as Hodge, except that there would be many more applications if the answer turned out to be yes.”

      Nowadays we commonly regard the Hodge Conjecture and/or the P≠NP Conjecture as boxes that we hope someday to open, while meanwhile proving Black Box (conditional) theorems. And yet mathematicians like Serre and Freedman (and Juris Hartmanis and many more) are right to remind us of the very real mathematical possibility that boxes like “Hodge” and “P≠NP” may perhaps have no interior contents.

      Needless to say, medical research and engineering alike are White Box cultures, in which preferable to understand how patients get well and preferable also to design and operate devices whose workings we understand … in the sense that observation, simulation, optimization, control, and treatment planning all are computationally feasible (with PTIME resources).

      From a medical point of view, however, there’s not much sense waiting around for the boxes to be opened (or proved to be unopenable). As David Deutsch remarks in his (wonderful!) TED Lecture A New Way to Explain Explanation (2009):

      “The tragedy of protracted stagnation isn’t sufficiently recognized”

      In medicine particularly, Deutsch’s tragedy is keenly felt … because the world’s need for healing is unbounded.

      So perhaps we needn’t wait for the inscrutable to be scrutinized? Because fortunately (for young researchers and entrepreneurs especially), there’s plenty that humanity has already accomplished in prior centuries — in math, science, medicine, and engineering — and much more that we can accomplish in the present century, without opening these mysterious mathematical boxes … and without assuming even that these boxes are openable in principle.

      Conclusion  At present we don’t know whether boxes like “Hodge” and “P≠NP” are black, white, or unopenable. Moreover, we don’t know even which STEM questions (if any!) depend crucially upon the status of these boxes. And the most important (and mysterious) consideration of all, is that these mysteries seemingly are not substantially obstructing sustained rapid progress that spans many STEM disciplines. And so this present ignorance is GOOD and FUN … for young STEM researchers especially.

    • John Sidles permalink
      February 12, 2014 12:34 pm

      In further regard to the (inexhaustible) theme of Black Box/White Box mathematics, Nicholas Katz is quoted in Allyn Jackson’s Comme Appelé du Néant — As If Summoned from the Void: The Life of Alexandre Grothendieck (2004)

      “As soon as [the Weil] conjectures were made [in 1949], it was clear that they were somehow going to play a central role, both because they were fabulous just as ‘black-box’ statements, but also because it seemed obvious that solving them required developing incredible new tools that would somehow have to be incredibly valuable in their own way — which turned out to be completely correct.”

      If the challenge of converting Black Boxes into White Boxes fosters the creation of “incredible new tools” (in Katz’ phrase), perhaps the reverse process also is viable? Vladimir Arnold’s essay Polymathematics: is Mathematics a Single Science or a Set of Arts? (2000) advocates this dual path as follows:

      Mistakes are an important and instructive part of mathematics, perhaps as important a part as the proofs. Proofs are to mathematics what spelling (or even calligraphy) is to poetry. Mathematical works do consist of proofs, just as poems do consist of characters [… examples follow  …] He [Gelfand] has always stressed (quite correctly) that mathematicians never appreciate new ideas, only the last step to the summit of the mountain counts in this mountain-climbing.

      Emphasis as in Arnold’s article.

      Conclusion  21st century complexity theory and quantum physics alike are blessed with abundant Black Box conjectures, that researchers struggle unceasingly to rewrap as White Box theorems. And these disciplines are blessed too with an ever-expanding set of amazing findings, both mathematical and experimental, that researchers are struggling mightily — not always successfully — to categorize neatly into traditional 20th century Black-and-White boxes.

      There is plenty of room here for many styles of 21st century STEM research … and plenty of scope for Gödel’s Lost Letter essays too. Good!

  2. February 9, 2014 6:14 am

    This post is very curios for me: in 1990s I wrote a paper about black and white boxes in OOP and that very often we need transparent class in spite of OO encapsulation principle. I sent the paper to one programming journal, but it was rejected. There is no state of art — they said :-)

    • rjlipton permalink*
      February 9, 2014 11:17 am

      mt2mt2

      So what happen to the paper? If still have would like to see what you had to say. In programming when I did more than now, I often had my team recode something. The reason was we were afraid that the available routines would have bad behavior at the “corner” cases, and so we redid stuff. I imagine related to your issues.

      • February 9, 2014 5:20 pm

        What happen to my paper? — Well, I did it! I had introduced Open OOP (OOOP) – please, see OMG newsletters: M.Trofimov, OOOP – The Third “O” Solution: Open OOP. First Class, OMG, 1993, Vol. 3, issue 3, p.14. Also, my letter about OO Languages future to the Byte editor may be interesting: M.I.Trofimov, The End of Pascal?, BYTE, March, 1990, p.36. – Now you can compare and estimate my predictions ;-)

      • February 17, 2014 12:09 am

        What is computing? A computer is an advanced counting machine, but perceived as intelligent as interactivity and artificial intelligence are built into it. Jesus says something strange in Matthew 10: But the very hairs of your head are all counted. Therefore do not fear!!!

        What?? Is the number of hairs on our heads counted?? Are we in a computer? How much RAM in this computer? Are all data stored in a black box or hole?

        How many of you have played Call of Duty? Many have found that there was more than one ”glitch” in the game. If you do things the right way, then you can get into a super mode where you can do amazing things. (I have not played much, but been coach for my son).

        The programmer has thus added a backdoor (or failure), where someone can get into a sort of supermode. God programmed the earth and the sun, moon and stars. They all are following math calculations. But there is a backdoor. The stories of Joshua and Hezekiah shows that the sun can stop or go backwards. Only the programmer knows all the back doors and all hidden opportunities.

        Anyway, our computers are ”stupid” and can not handle real calls. But when you pray to God, the biblical author, you talk to some of the highest intelligence and power. If your heart is set correctly (honest and sincere), He will answer you in His own way.

        http://wp.me/p3uvTQ-l

        I am only a pointer to a pointer, if you understand what I write about.

  3. February 10, 2014 2:25 pm

    hi RJL. this indeed deep mysterious dichotomy of “how” vs “why” is also seen in a neat/great/influential book introducing programming that was used in my freshman software engr class, “structure & interpretation of computer programs” by abelson & sussman (MIT) where they meditate on the subject a bit (free online edition). have been pondering this same deep zen question in mathematics/comp sci for over 2 decades & agree its quite fundamental and indicative of some massive future research attn/energy/motion/expansion/momentum in the area. it seems to be a unifying framework. gotta write a blog on this myself sometime.

    to me, automated theorem proving is shedding answers on this question/challenge. have been collecting recent interesting research leads in this area. to me attacking undecidable problems lies at the heart of this question. am also very interested in “answer set programming” (similar to solving SAT equations but more sophisticated) which has the ability to transform how questions into why answers. there was also a recent paper demonstrating this technique by finding record breaking sorting circuits via SAT solvers & think this is just the beginning of this type of attack/research program. some more details in tcs.se chat hope to hear from anyone interested on the subj.

  4. k-jl permalink
    February 12, 2014 3:52 am

    I think the theorems of Rice demonstrate this difference quite well. They totally make clear the situation of a what. But there is no result like that for the corresponding how.

  5. February 15, 2014 1:35 pm

    Reblogged this on Heapkhim's Blog and commented:
    Best Glass

  6. February 15, 2014 4:29 pm

    A computer is an advanced counting machine, but perceived as intelligent as interactivity and artificial intelligence are built into it. Jesus says something strange in Matt 10: But the very hairs of your head are all counted. Therefore do not fear !!!

    What ? ? Is the number of hairs on our heads counted ? ? Are we in a calculator ? How much memory in this machine then?

    How many of you have played Call of Duty ? Many have found that there was more than one ” glitch ” in the game. If you do things the right way , so you can get into a super mode where you can do amazing things. (I have not played much , but been coach for my son).

    The programmer has thus added a backdoor (or failure ) , where one can get into a sort of super mode. God programmed the earth and the sun , moon and stars. The following math courses. But there is a backdoor . The story of Joshua and Hezekiah shows that the sun can stop or go back . Only the programmer knows all the back doors and all hidden opportunities.

    Anyway, our computers are ” stupid ” and can not handle real calls. But when you pray to God , the biblical author, talks to some of the highest intelligence and power. If your heart is set correctly ( honest and sincere ) , He will answer you in their own way .

    http://wp.me/p3uvTQ-l

  7. wooleeje permalink
    February 16, 2014 5:51 am

    Reblogged this on 코리아카지노 우리카지노 다모아카지노 ∽⊙▶ http://WWW.JOWA9.COM ◀⊙∽ 월드카지노 썬시티카지노 에이플러스카지노 ∽⊙▶ http://WWW.JOWA9.COM ◀⊙∽윈스카지노 정선카지노 태양성카지노 ∽⊙▶ http://WWW.JOWA9.COM ◀⊙∽강원랜드카지노 온라인카지노 인터넷카지노∽⊙▶ http://WWW.JOWA9.COM ◀⊙∽바카라카지노 and commented:
    코리아카지노 우리카지노 다모아카지노 ☆ http://WWW.TONK6.COM ☆ 월드카지노 썬시티카지노 에이플러스카지노 ☆ http://WWW.TONK6.COM ☆ 윈스카지노 정선카지노 태양성카지노 ☆ http://WWW.TONK6.COM ☆ 강원랜드카지노 온라인카지노 인터넷카지노 ☆ http://WWW.TONK6.COM ☆ 바카라카지노 ~princemarchmraz~

  8. February 16, 2014 3:38 pm

    Reblogged this on victormiguelvelasquez.

  9. February 16, 2014 5:15 pm

    Thanx fun reading

  10. February 16, 2014 11:57 pm

    Reblogged this on The International Blogspaper.

  11. February 17, 2014 6:53 am

    Reblogged this on tjphull.

  12. February 17, 2014 11:38 am

    Reblogged this on emmadol's Blog.

  13. February 19, 2014 12:43 am

    Black Box Vs White Box!
    Useful for this post!
    #wordpress!

  14. February 19, 2014 3:28 am

    Really interesting piece. Ian x

  15. February 21, 2014 3:41 pm

    Reblogged this on The Machinehead Chronicles.

  16. February 22, 2014 4:26 pm

    Reblogged this on STOKERLAND and commented:
    I just thought this might be of interest to certain folk. Test reblog.

  17. Varun permalink
    March 4, 2014 12:29 pm

    I don’t understand how there can be a meaningful “how” in Physics. If one asks “how”, that only says something about his subjective taste. For example, one might well satisfy oneself with Newton’s theory and not interrogate any further. Or one might find such satisfaction at Einstein’s theory. On the other hand, there could be a finer “particle exchange” type theory of gravity and one could be dissatisfied even with that (“Why should those particles get exchanged?”). In my opinion, the only objective standard for a theory is its agreement with observations along with its economy in axioms. Beyond that, I believe in “Shut up and calculate”.

  18. March 4, 2014 11:50 pm

    Reblogged this on ahmadrmahfooz.

  19. March 11, 2014 5:02 pm

    Reblogged this on maha's place.

  20. May 18, 2014 3:40 am

    Reblogged this on nexsean and commented:
    Black is original

Trackbacks

  1. great moments in empirical/experimental math/TCS research, breakthough SAT induction idea | Turing Machine

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,888 other followers