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 ${A,B \in \mathsf{NP}}$, there is a language ${C}$ that separates ${A}$ from ${B}$ but is not ${\mathsf{NP}}$-hard.

Here ‘separates’ means ${A \subseteq C}$ and ${B \cap C = \emptyset}$, and hardness is with regard to polynomial-time Turing reductions.

One way of conveying the intuition is that if ${A}$ and ${B}$ are complements then ${C}$ must equal ${A}$ but all three languages are then in ${\mathsf{NP} \cap \mathsf{co}\text{-}\mathsf{NP}}$, so ${C}$ cannot be ${\mathsf{NP}}$-hard unless ${\mathsf{NP} = \mathsf{co}\text{-}\mathsf{NP}}$. The actual weaker condition ${A \cap B = \emptyset}$ allows more ${C}$‘s, but every one would have to be ${\mathsf{NP}}$-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 ${R}$ not for all strings, but only for strings that are already “promised” as belonging to a set ${Q}$. Dick’s own post on Even gave the example where ${Q}$ is the set of graphs consisting of two node-disjoint directed paths from ${\{s_1,s_2\}}$ to ${\{t_1,t_2\}}$, and ${R}$ is the property that the path from ${s_1}$ goes to ${t_1}$ not ${t_2}$. The promise bumps the known complexity down to counting modulo 2.

The correspondence is:

$\displaystyle \begin{array}{rcl} A &=& R \cap Q\\ B &=& (\sim R) \cap Q\\ C &=& \text{any {\it solution}, meaning~} C \cap Q = R \cap Q. \end{array}$

The answers on strings outside the promise set ${Q}$ 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.

## Why Care?

If ${\mathsf{NP} = \mathsf{co}\text{-}\mathsf{NP}}$ then the conjecture is false, because then the choice ${A = \mathsf{SAT}}$ and ${B =}$ its complement puts ${B \in \mathsf{NP}}$ too, but then the only ${C}$ is ${\mathsf{SAT}}$ which is ${\mathsf{NP}}$-hard. Hence the ESY Conjecture implies ${\mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$, 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 ${x}$ that at most one ${y}$ will satisfy a feasibly recognizable property ${R(x,y)}$, then define

$\displaystyle \begin{array}{rcl} A &=& \{(x,w): \text{such a }y\text{ exists and }w\text{ is a prefix of it}\}\\ B &=& \{(x,w): \text{such a }y\text{ exists and }w\text{ is {\bf not} a prefix of it}\}.\end{array}$

An important case is Factoring, where ${x}$ is a number and ${y}$ is a unique representation of its prime factorization. Then ${A,B}$ are disjoint sets in ${\mathsf{NP}}$ and any separating ${C}$ can be used to find ${y}$ by building up ${w}$ character-by-character using Turing queries to ${C}$. Hence if the task of finding ${y}$ when it exists is ever ${\mathsf{NP}}$-hard then again ESY is false. Thus the truth of ESY implies that ${\mathsf{NP}}$ is different from the subclass called ${\mathsf{UP}}$ which captures languages having this unique-${y}$ property, and that there is no way even with non-determinism to winnow satisfying assignments to a formula in ${\mathsf{SAT}}$ down to a unique choice.

The ESY Conjecture is also relevant for cryptography. The cracking problem is given a ciphertext ${x}$, find its unique decoding ${y}$. For any public-key cryptosystem (PKCS) with feasible key-generation, treating this as a function task as above gives disjoint sets ${A}$ and ${B}$ that belong to ${\mathsf{NP}}$. 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 ${\mathsf{NP}}$-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 ${\mathsf{NP}}$-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 “${\mathsf{NP}}$-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 ${\mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$. 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 ${\mathsf{NP}}$-hard cracking problem unless ${\mathsf{NP} = \mathsf{co}\text{-}\mathsf{NP}}$. What I’d proved is that if every separator ${C}$ were ${\mathsf{NP}}$-hard then there was a single poly-time oracle TM ${M}$ such that ${M^C}$ accepted ${\mathsf{SAT}}$ for every separator ${C}$. For this ${M}$ the answers to queries ${z}$ outside ${A \cup B}$ could be arbitrary, and “all” I needed to complete the argument was that they could hence be avoided—with help from ${\mathsf{NP} \cap \mathsf{co}\text{-}\mathsf{NP}}$ 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 ${\mathsf{NP}}$ both from ${\mathsf{co}\text{-}\mathsf{NP}}$ and from ${\mathsf{UP}}$ 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 ${e}$. I needed to show ${e}$ is unbounded to defeat a polynomial adversary, but crunching the numbers and ${O}$-notation gave me the answer

$\displaystyle e = 2^{-}.$

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 ${\mathsf{NP}}$-hard between many-one and Turing. The key restriction is that the oracle queries are non-adaptive, meaning the next query string ${z_i}$ cannot depend on the answers to previous queries. Thus the oracle machine ${M}$ on input ${x}$ must select all the polynomially-many ${z_i}$ before asking any, and the result ${M(x)}$ is then a truth-table of the oracle answers.

This excludes binary search and building ${y}$ via prefixes ${w}$, which are adaptive. Thus you should never be fooled into choosing strings ${z_i \notin A \cup B}$ and the machinery for equivalence to ${\mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$ should kick in—easy, no? No.

My ICALP 1986 paper had noted an impasse between one ${z_i}$ and two ${z_i}$‘s. Alan and company get it for constant-many ${z_i}$‘s, if they are all longer than the input ${x}$. They even allow some non-determinism in choosing them, and can handle ${|z_i| = |x|}$ provided ${z_i > x}$. But what about the general bounded truth-table case?

Here is where other notions of hardness come in. Call a machine ${M}$ a predictor for a language ${A}$ if ${M}$ given ${x}$ and the string of answers ${A(y)}$ for all ${y < x}$ outputs ${A(x)}$ correctly. Note that the input to ${M}$ has length ${N \sim 2^n}$ where ${n = |x|}$. Call a disjoint pair ${(A,B)}$ unpredictable in time ${t(N)}$ if all predictors of ${A}$ take time above ${t(N)}$ for all but finitely many ${x}$ that are not in ${B}$. Unconditionally they show the following:

Theorem 1 For all ${k > 0}$ there is a language ${R}$ disjoint from ${\mathsf{SAT}}$ such that ${(R,\mathsf{SAT})}$ is unpredictable within time ${2^{\log^k N}}$, which equals time ${2^{n^k}}$.

This is actually a plank in their main theorem for length-increasing non-adaptive reductions. The final question is, can you get ${R \in \mathsf{NP}}$, even dropping the time down to ${O(N^2)}$?

Theorem 2 If some ${\mathsf{NP}}$ language lacks an ${O(N^2)}$-time predictor, then ESY holds unconditionally for bounded truth-table reductions.

As usual see the paper for details, with a longer version forthcoming.

## Promises, Promises…

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${(r)}$ is the statement that every pair of disjoint ${\mathsf{NP}}$ sets has a separator that is not ${\mathsf{NP}}$-hard under ${r}$-reductions. The reductions are deterministic ${\mathsf{poly}}$ time, but can be relaxed to allow so-called “strong” non-determinism.

 Conjecture Promise Property ESY${\;(\leq_m)}$ – ${\iff \mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$ ESY${\;(\leq_{1tt})}$ – ${\iff \mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$ ESY${\;(\leq_{btt,li})}$ – ${\iff \mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$ ESY${\;(\leq_{btt})}$ Unpredictability ${\iff \mathsf{NP} \neq \mathsf{co}\text{-}\mathsf{NP}}$ ESY${\;(\leq_{tt})}$ ? Open ESY${\;(\leq_T)}$ ? 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 ${\mathsf{UP}}$ 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.

## Open Problems

Does the ESY conjecture hold? Are its three main consequences implied by a simpler statement? Same for the ESY(${\cdots}$) 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.

1. July 14, 2012 9:38 pm

The photo of Alan comes from his visit to me in Oxford in early 1986, with his son Jeffrey—that’s High Street with Magdalen College Tower in the background. Some of the remarks about Alan in the intro come from Dick. The “much else” in 1984 included personal geometry that was definitely non-Euclidean—the angles even added up to meeting my wife a year later.

• July 19, 2012 3:21 pm

What is the building behind the person behind Alan Selman? It doesn’t look like Magdalen Tower (which I assume is supposed to be on the left). Though I can’t think of other buildings on High Street that might fit the height seems off. And it looks like it was always near-impossible to take a picture on High Street without a bus in the background.

• July 21, 2012 11:46 pm

Magdalen Tower is the tall thing on the right over the red double-decker bus. The building behind the person is another part of Magdalen College, I think.

2. July 15, 2012 6:58 pm

I’m not too familiar with the ESY conjecture, but I feel that it would be relevant to note the similarity to a result in computability: there are disjoint Turing recognizable languages that are not separated by any decidable set. Perhaps someone more knowledgeable could offer some perspective.