It Don’t Come EaSY
Hitting hardness makes a 30-year-old conjecture harder
Alan Selman is one of the founders of Complexity Theory, both through his deep research and his unselfish service. We will discuss his research in a moment, but his service has helped shape the field. He was one of the founders in 1986 of the Structure in Complexity Theory conference, now called Computational Complexity, and wrote with the late Steve Mahaney the NSF proposal that secured its initial funding. He is a Fellow of the ACM and was honored for Distinguished Service under the aegis of ACM SIGACT in 2001.
Today we discuss his paper with his current and former students on “A Thirty Year Old Conjecture about Promise Problems.” It was just presented at ICALP 2012 in Warwick, England.
Alan has always been interested in the core issues of the limits of computation. He especially has advanced many foundational concepts connected with the complexity of functions rather than languages, with various kinds of reducibility, and with so-called promise problems. Alan is not one to work on new areas, where there is often “low-hanging fruit”; rather he has always been attracted to classic questions. These questions, which we believe must be solved if we are to advance our understanding of computation, often are hard and often require deep new insights before they become easy to “pick.”
So it comes as no surprise that his recent paper is on a thirty-year-old conjecture. It is joint with Aduri Pavan, who is an Associate Professor in Computer Science at Iowa State University alongside Jack Lutz, and Alan’s current students Andrew Hughes and Nathan Russell here at Buffalo.
The Conjecture and Promise Problems
The conjecture bears the names of Yacov Yacobi and the late Shimon Even besides Alan, and is known by their initials ESY:
Conjecture. For every two disjoint languages , there is a language that separates from but is not -hard.
Here ‘separates’ means and , and hardness is with regard to polynomial-time Turing reductions.
One way of conveying the intuition is that if and are complements then must equal but all three languages are then in , so cannot be -hard unless . The actual weaker condition allows more ‘s, but every one would have to be -hard to falsify the conjecture.
Even and Yacobi originally thought of this in the form of promise problems, and Oded Goldreich’s memorial survey for Even credits their 1984 paper with Alan as originating the study of promise problems. The idea is that often we want to decide a property not for all strings, but only for strings that are already “promised” as belonging to a set . Dick’s own post on Even gave the example where is the set of graphs consisting of two node-disjoint directed paths from to , and is the property that the path from goes to not . The promise bumps the known complexity down to counting modulo 2.
The correspondence is:
The answers on strings outside the promise set are not supposed to matter. The hitch that makes the ESY Conjecture difficult is that in practice they do matter.
Besides the upsurge covered in Oded’s survey, promise problems have recently come into force in quantum computation. In cryptography the promise is that a given (public) key and ciphertext are valid, so that there is a plaintext to decrypt. This goes with promising that the plaintext is unique.
If then the conjecture is false, because then the choice and its complement puts too, but then the only is which is -hard. Hence the ESY Conjecture implies , already a sign that it will be hard to prove. But how about refuting it, or finding evidence for it, and what else relates to it?
ESY also impacts the tasks of computing functions and finding solutions when they are unique. If you know in advance given any that at most one will satisfy a feasibly recognizable property , then define
An important case is Factoring, where is a number and is a unique representation of its prime factorization. Then are disjoint sets in and any separating can be used to find by building up character-by-character using Turing queries to . Hence if the task of finding when it exists is ever -hard then again ESY is false. Thus the truth of ESY implies that is different from the subclass called which captures languages having this unique- property, and that there is no way even with non-determinism to winnow satisfying assignments to a formula in down to a unique choice.
The ESY Conjecture is also relevant for cryptography. The cracking problem is given a ciphertext , find its unique decoding . For any public-key cryptosystem (PKCS) with feasible key-generation, treating this as a function task as above gives disjoint sets and that belong to . The new paper extends this connection to several recent cryptosystems with probabilistic key generation.
Thus the ESY conjecture is a way of saying that no cracking problem of a “natural” PKCS can be -hard. Indeed this may be the simplest explanation of why RSA which is based on the hardness of factoring has had no convincing competitior based on an -hard problem.
I have heard this connection deprecated because it does not involve concepts of randomized hardness which are not only central to cryptography but have driven advances in complexity for 30 years. However a good and natural hard problem has ways of getting at those other core concepts. This is the essence I catch in Alan’s new paper. But since I’ve also known Alan for 30 years, since meeting him at the 1982 ICALP in Aarhus, Denmark, let me first tell my own Ringo Starr blues with ESY.
My Own Brushes with ESY
I first heard the conjecture when I attended a complexity workshop at Brooklyn College in late December 1983, where Alan was a main speaker. I was home for Christmas vacation during my third year at Oxford, where I had just won a Junior Fellowship effective the following October. My notes of Alan’s talk misunderstood “-hard” as meaning many-one reducibility. Staying up past 1am in the guest room of a Princeton friend’s parents’ house, I wrote out a proof that the “conjecture” was equivalent to . I caught Alan first thing the next morning and he clarified “Turing” and that what I’d done was basically known. Oops.
Back in England in January I got consumed with it, and in a few weeks I had 20 handwritten pages that seemed 90% of the way there, specifically to prove that no PKCS could have -hard cracking problem unless . What I’d proved is that if every separator were -hard then there was a single poly-time oracle TM such that accepted for every separator . For this the answers to queries outside could be arbitrary, and “all” I needed to complete the argument was that they could hence be avoided—with help from itself or maybe a little more.
I filled a February hole in the weekly Mathematical Institute Combinatorics Colloquium to present the problem and my progress. Likely because I had “Cryptosystems” in my talk title, several people in suits whom nobody knew were among the 20-odd attending. I did not send a copy of my MS to Alan; this was the time before e-mail and PDFs but I was really distracted by desire to get “it all” and by much else. Around May I realized my proof was an oxbow meander between a proof of the Baire category theorem for Cantor space and a dressed-up König’s Lemma. Applying those theorems shortened it to a few pages within a longer painfully double-spaced typescript, which stoked my campaign to bring affordable technical word-processing to Oxford. Finally I contacted Alan when I was in the US in August, by which time the same advance was enshrined in his FOCS-accepted paper with his student Jochen Grollmann. My proof found a different, more-abstract context in a paper for ICALP 1986.
Fast-forward to 1993 and having Alan down the hall revives my interest, this time for showing that ESY holds relative to a random oracle. This is plausible since the famous paper by Charles Bennett and John Gill separates both from and from by a random oracle. It involves oracle machines that call other oracle machines, but in 30 handwritten pages I digested seemingly every aspect of the problem, applied every trick, and got everything down to a purely analytical estimate of an exponent . I needed to show is unbounded to defeat a polynomial adversary, but crunching the numbers and -notation gave me the answer
Quadratic alas equals bupkis, with “from below” adding insult to my injury-free construction. That remains the most work I’ve ever put into a manuscript to not solve a problem—this one is still open too.
How to Make Progress
When you have a solved case, try cases in-between. Alan’s new paper considers versions of -hard between many-one and Turing. The key restriction is that the oracle queries are non-adaptive, meaning the next query string cannot depend on the answers to previous queries. Thus the oracle machine on input must select all the polynomially-many before asking any, and the result is then a truth-table of the oracle answers.
This excludes binary search and building via prefixes , which are adaptive. Thus you should never be fooled into choosing strings and the machinery for equivalence to should kick in—easy, no? No.
My ICALP 1986 paper had noted an impasse between one and two ‘s. Alan and company get it for constant-many ‘s, if they are all longer than the input . They even allow some non-determinism in choosing them, and can handle provided . But what about the general bounded truth-table case?
Here is where other notions of hardness come in. Call a machine a predictor for a language if given and the string of answers for all outputs correctly. Note that the input to has length where . Call a disjoint pair unpredictable in time if all predictors of take time above for all but finitely many that are not in . Unconditionally they show the following:
Theorem 1 For all there is a language disjoint from such that is unpredictable within time , which equals time .
This is actually a plank in their main theorem for length-increasing non-adaptive reductions. The final question is, can you get , even dropping the time down to ?
Theorem 2 If some language lacks an -time predictor, then ESY holds unconditionally for bounded truth-table reductions.
As usual see the paper for details, with a longer version forthcoming.
What happens in complexity is often we need a condition—a promise—to obtain a conclusion. Ironically this happens here. The following table summarizes what is known. ESY is the statement that every pair of disjoint sets has a separator that is not -hard under -reductions. The reductions are deterministic time, but can be relaxed to allow so-called “strong” non-determinism.
|ESY||?||The full conjecture, wide open.|
The ? marks hint that no simple statement is known to imply the ESY Conjecture, nor its three diverse consequences. Note also that the consequence for comes into play only for the adaptive Turing reductions.
This makes the truth-table cases the logical next focus. The predictability notion is classical and known to be related to pseudo-random generators in other contexts. For progress we may need to beef it up. Here we may both obtain guidance from hardness notions that bridge from worst-case to average-case hardness as surveyed by Bogdanov and Trevisan, and we may find new implications for them in the ESY setting.
But we can’t promise it will be easy.
Does the ESY conjecture hold? Are its three main consequences implied by a simpler statement? Same for the ESY() forms. Which of the forms hold with respect to a random oracle? Is there more hardness, including real hardness, lurking further below?
We also mourn the recent passing of Prof. Dr. Manfred Kudlek, while attending the CIE 2012 conference. I also met him at ICALP 1982 in Aarhus—the photo of us is taken in a tower marking Denmark’s highest point. He attended all 38 ICALP conferences prior to this year, and his passing was observed in Warwick. This obituary has photos from many of them, beginning with Aarhus. Our condolences to his family and colleagues.