Gödel's Lost Letter and P=NP

News on Intermediate Problems

March 5, 2015

tags: Bireswar Das, Cody Murray, complexity, discrete log, Eric Allender, Factoring, graph isomorphism, MCSP, minimum circuit size, NP-intermediate, randomized reductions, Ryan Williams, succinctness

by KWRegan

The Minimum Circuit Size Problem goes front and center

Eric Allender, Bireswar Das, Cody Murray, and Ryan Williams have proved new results about problems in the range between ${\mathsf{P}}$ and ${\mathsf{NP}}$ -complete. According to the wide majority view of complexity the range is vast, but it is populated by scant few natural computational problems. Only Factoring, Discrete Logarithm, Graph Isomorphism (GI), and the Minimum Circuit Size Problem (MCSP) regularly get prominent mention. There are related problems like group isomorphism and others in subjects such as lattice-based cryptosystems. We covered many of them some years back.

Today we are delighted to report recent progress on these problems.

MCSP is the problem: given a string ${x}$ of length ${n = 2^k}$ and a number ${s}$ , is there a Boolean circuit ${C}$ with ${s}$ or fewer wires such that

$\displaystyle C(0^k)\cdot C(0^{k-1} 1)\cdot C(0^{k-2}10) \cdots C(1^{k-1} 0)\cdot C(1^k) = x?$

For ${x}$ of other lengths ${m}$ , ${2^{k-1} < m < 2^k}$ , we catenate the values of ${C}$ for the first ${m}$ strings in ${\{0,1\}^k}$ under the standard order. Since every ${k}$ -ary Boolean function has circuits of size ${O(\frac{2^k}{k}) = O(\frac{n}{\log n})}$ which are encodable in ${O(n)}$ bits, MCSP belongs to ${\mathsf{NP}}$ with linear witness size.

Several Soviet mathematicians studied MCSP in the late 1950s and 1960s. Leonid Levin is said to have desired to prove it ${\mathsf{NP}}$ -complete before publishing his work on ${\mathsf{NP}}$ -completeness. MCSP seemed to stand aloof until Valentine Kabanets and Jin-Yi Cai connected it to Factoring and Discrete Log via the “Natural Proofs” theory of Alexander Razborov and Steven Rudich. Eric and Harry Buhrman and Michal Koucký and Dieter van Melkebeek and Detlef Ronneburger improved their results in a 2006 paper to read:

Theorem 1 Discrete Log is in ${\mathsf{BPP}^{\mathrm{MCSP}}}$ and Factoring is in ${\mathsf{ZPP}^{\mathrm{MCSP}}}$ .

Now Eric and Bireswar have completed the triad of relations to the other intermediate problems:

Theorem 2 Graph Isomorphism is in ${\mathsf{RP}^{\mathrm{MCSP}}}$ . Moreover, every promise problem in ${\mathsf{SZK}}$ belongs to ${\mathsf{BPP}^{\mathrm{MCSP}}}$ as defined for promise problems.

Cody and Ryan show on the other hand that proving ${\mathsf{NP}}$ -hardness of MCSP under various reductions would entail proving breakthrough lower bounds:

Theorem 3

If ${\mathrm{SAT} \leq_m^p \mathrm{MCSP}}$ then ${\mathsf{EXP} \not\subseteq \mathsf{NP} \cap \mathsf{P/poly}}$ , so ${\mathsf{EXP \neq ZPP}}$ .

If ${\mathrm{SAT} \leq_m^{\log} \mathrm{MCSP}}$ then ${\mathsf{PSPACE \neq ZPP}}$ .

If ${\mathrm{SAT} \leq_m^{ac_0} \mathrm{MCSP}}$ then ${\mathsf{NP} \not\subset \mathsf{P/poly}}$ (so ${\mathsf{NP \neq P}}$ ), and also ${\mathsf{E}}$ has circuit lower bounds high enough to de-randomize ${\mathsf{BPP}}$ .

In any many-one reduction ${f}$ from ${\mathrm{Parity}}$ (let alone ${\mathrm{SAT}}$ ) to ${\mathrm{MCSP}}$ , no random-access machine can compute any desired bit ${j}$ of ${f(x)}$ in ${|x|^{1/2-\epsilon}}$ time.

The last result is significant because it is unconditional, and because most familiar ${\mathsf{NP}}$ -completeness reductions ${f}$ are local in the sense that one can compute any desired bit ${j}$ of ${f(x)}$ in only ${(\log |x|)^{O(1)}}$ time (with random access to ${x}$ ).

Why MCSP is Hard to Harden

The genius of MCSP is that it connects two levels of scaling—input lengths ${k}$ and ${n}$ —in the briefest way. The circuits ${C}$ can have exponential size from the standpoint of ${k}$ . This interplay of scaling is basic to the theory of pseudorandom generators, in terms of conditions under which they can stretch a seed of ${\mathsf{poly}(k)}$ bits into ${n}$ bits, and to generators of pseudorandom functions ${g: \{0,1\}^k \longrightarrow \{0,1\}^k}$ .

An issue articulated especially by Cody and Ryan is that reductions ${f}$ to MCSP carry seeds of being self-defeating. The ones we know best how to design involve “gadgets” whose size scales as ${k}$ not ${n}$ . For instance, in a reduction from ${\mathrm{3SAT}}$ we tend to design gadgets for individual clauses in the given 3CNF formula ${\phi}$ —each of which has constant-many variables and ${O(\log n) = O(k)}$ encoded size. But if ${f}$ involves only ${\mathsf{poly}(k)}$ -sized gadgets and the connections between gadgets need only ${\mathsf{poly}(k)}$ lookup, then when the reduction outputs ${f(\phi) = (y,s)}$ , the string ${y}$ will be the graph of a ${\mathsf{poly}(k)}$ -sized circuit. This means that:

if ${s > \mathsf{poly}(k)}$ then the answer is trivially “yes”;
if ${s \leq \mathsf{poly}(k)}$ then the answer can be found in ${\mathsf{poly}(n)}$ time—or at worst quasipolynomial in ${n}$ time—by exhaustively trying all circuits of size ${s}$ .

The two horns of this dilemma leave little room to make a non-trivial reduction to MCSP. Log-space and ${\mathsf{AC^0}}$ reductions are (to different degrees) unable to avoid the problem. The kind of reduction that could avoid it might involve, say, ${n^{1/2}}$ -many clauses per gadget in an indivisible manner. But doing this would seem to require obtaining substantial non-local knowledge about ${\phi}$ in the first place.

Stronger still, if the reduction is from a polynomially sparse language ${A \in \mathsf{NP}}$ in place of ${\mathrm{SAT}}$ , then even this last option becomes unavailable. Certain relations among exponential-time classes imply the existence of hard sparse sets in ${\mathsf{NP}}$ . The hypothesis that MCSP is hard for these sets impacts these relations, for instance yielding the ${\mathsf{EXP \neq ZPP}}$ conclusion.

A paradox that at first sight seems stranger emerges when the circuits ${C}$ are allowed oracle gates. Such gates may have any arity ${m}$ and output 1 if and only if the string ${u_1 u_2\cdots u_m}$ formed by the inputs belongs to the associated oracle set ${A}$ . For any ${A}$ we can define ${\mathrm{MCSP}^A}$ to be the minimum size problem for such circuits relative to ${A}$ . It might seem axiomatic that when ${A}$ is a powerful oracle such as ${\mathrm{QBF}}$ then ${\mathrm{MCSP}^{\mathrm{QBF}}}$ should likewise be ${\mathsf{PSPACE}}$ -complete. However, giving ${C}$ such an oracle makes it easier to have small circuits for meaningful problems. This compresses the above dilemma even more. In a companion paper by Eric with Kabanets and Dhiraj Holden they show that ${\mathrm{MCSP}^{\mathrm{QBF}}}$ is not complete under logspace reductions, nor even hard for ${\mathsf{TC}^0}$ under uniform ${\mathsf{AC}^0}$ reductions. More strikingly, they show that if it is hard for ${\mathsf{P}}$ under logspace reductions, then ${\mathsf{EXP = PSPACE}}$ .

Nevertheless, when it comes to various flavors of bounded-error randomized Turing reductions, MCSP packs enough hardness to solve Factoring and Discrete Log and GI. We say some more about how this works.

Randomized Reductions to MCSP

What MCSP does well is efficiently distinguish strings ${x \in \{0,1\}^n}$ having ${n^{\alpha}}$ -sized circuits from the vast majority having no ${n^{\beta}}$ -sized circuits, where ${0 < \alpha < \beta < 1}$ . The dense latter set ${B}$ is a good distinguisher between pseudorandom and uniform distributions on ${x \in \{0,1\}^n}$ . Since one-way functions suffice to construct pseudorandom generators, MCSP turns into an oracle for inverting functions to an extent codified in Eric’s 2006 joint paper:

Theorem 4 Let ${B}$ be a dense language of strings having no ${n^{\beta}}$ -sized circuits, and let ${f(x,y) = z}$ be computable in polynomial time with ${x,y,z}$ of polynomially-related lengths. Then we can find a polynomial-time probabilistic oracle TM ${M}$ and ${c > 0}$ such that for all ${n}$ and ${y}$ ,

$\displaystyle \Pr_{x,r}[M^B(y,f(x,y),r) = w \text{ such that } f(w,y) = f(x,y)] \geq \frac{1}{n^c}.$

Here ${x}$ is selected uniformly from ${\{0,1\}^n}$ and ${r}$ is uniform over the random bits of the machine. We have restricted ${f}$ and ${B}$ more than their result requires for ease of discussion.

To attack GI we set things up so that “ ${x}$ ” and “ ${y}$ ” represent a graph ${G}$ and a permutation ${\pi}$ of its vertices, respectively. More precisely “ ${G}$ ” means a particular adjacency matrix, and we define ${f(\pi,G) = G'}$ to mean the adjacency matrix ${G'}$ obtained by permuting ${G}$ according to ${\pi}$ . By Theorem 4, using the MCSP oracle to supply ${B}$ , one obtains ${M}$ and ${c}$ such that for all ${n}$ and ${n}$ -vertex graphs ${G}$ ,

$\displaystyle \Pr_{\pi,r}[M^{\mathrm{MCSP}}(G,f(\pi,G),r) = \rho \text{ such that } f(\rho,G) = f(\pi,G)] \geq \frac{1}{n^c}.$

Since ${f}$ is 1-to-1 we can simplify this while also tying “ ${G'}$ ” symbolically to ${f(\pi,G)}$ :

$\displaystyle \Pr_{\pi,r}[M^{\mathrm{MCSP}}(G,G',r) = \pi] \geq \frac{1}{n^c}. \ \ \ \ \ (1)$

Now given an instance ${(G,H)}$ of GI via adjacency matrices, do the following for some constant times ${n^c}$ independent trials:

Pick ${\pi}$ and ${r}$ uniformly at random and put ${G' = f(\pi,G)}$ .
Run ${M^{\mathrm{MCSP}}(H,G',r)}$ to obtain a permutation ${\rho}$ .
Accept if ${\rho(H) = G'}$ , which means ${H = \rho^{-1}\pi(G)}$ .

This algorithm has one-sided error since it will never accept if ${G}$ and ${H}$ are not isomorphic. If they are isomorphic, then ${G'}$ arises as ${\rho(H)}$ with the same distribution over permutations that it arises as ${G' = \pi(G)}$ , so Equation (1) applies equally well with ${H}$ in place of ${G}$ . Hence ${M^{\mathrm{MCSP}}(H,G',r)}$ finds the correct ${\rho}$ with probability at least ${\frac{1}{n^c}}$ on each trial, yielding the theorem ${\mathrm{GI} \in \mathsf{RP}^{\mathrm{MCSP}}}$ .

The proof for ${\mathsf{SZK \subseteq BPP}^{\mathrm{MCSP}}}$ is more detailed but similar in using the above idea. There are many further results in the paper by Cody and Ryan and in the oracle-circuit paper.

Open Problems

These papers also leave a lot of open problems. Perhaps more importantly, they attest that these open problems are attackable. Can any kind of many-one reducibility stricter than ${\leq_m^p}$ reduce every language in ${\mathsf{P}}$ to MCSP? Can we simply get ${\mathsf{EXP} \not\subset \mathsf{P/poly}}$ from the assumption ${\mathrm{SAT} \leq_m^p \mathrm{MCSP}}$ ? The most interesting holistic aspect is that we know new lower bounds follow if MCSP is easy, and now we know that new lower bounds follow if MCSP is hard. If we assume that MCSP stays intermediate, can we prove lower bounds that combine with the others to yield some non-trivial unconditional result?

The Right Stuff of Emptiness

February 23, 2015

tags: aviation, empty set, empty string, formal languages, Jeff Skiles, set theory, teaching

by KWRegan

How ∅ versus {ε} can be a life-and-death difference

Cropped from source

Jeff Skiles was the co-pilot on US Airways Flight 1549 from New York’s LaGuardia Airport headed for Charlotte on January 15, 2009. The Airbus A320 lost power in both engines after striking birds at altitude about 850 meters and famously ditched in the Hudson River with no loss of life. As Skiles’s website relates, he had manual charge of the takeoff but upon his losing his instrument panel when the engines failed,

“Captain Chesley Sullenberger took over flying the plane and tipped the nose down to retain airspeed.”

Skiles helped contact nearby airports for emergency landing permission but within 60 seconds Sullenberger and he determined that the Hudson was the only option. His front page does not say he did anything else.

Today we tell some stories about the technical content of forms of emptiness.
Read more…

Ada the Amplifier

February 17, 2015

tags: Ada Lovelace, Charles Babbage, programming, systems

by KWRegan

Plus updated links to our Knuth and TED talks

Ada Lovelace was nuts. Some have used this to minimize her contributions to the stalled development of Charles Babbage’s “Analytical Engine” in the 1840s. Judging from her famously over-the-top “Notes” to her translation of the only scientific paper (known as the “Sketch”) published on Babbage’s work in his lifetime, we think the opposite. It took nuttily-driven intensity to carry work initiated by Babbage several square meters of print beyond what he evidently bargained for.

This month we have been enjoying Walter Isaacson’s new book The Innovators, which leads with her example, and have some observations to add.
Read more…

Still A Brilliant Idea

February 7, 2015

tags: Adam Smith, Cynthia Dwork, databases, differential privacy, Frank McSherry, Kobbi Nissim, privacy, security

by Pip

An apology and correction

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith are the inventors of differential privacy, as formulated in their 2006 paper “Calibrating Noise to Sensitivity in Private Data Analysis,” in the proceedings of the 2006 Theory of Cryptography Conference.

Today Ken and I want to talk about differential privacy again.
Read more…

Cynthia Dwork and a Brilliant Idea

February 6, 2015

tags: Adam Smith, Bernard Dwork, Cynthia Dwork, definitions, differential privacy, Frank McSherry, Kobbi Nissim, Moni Naor, privacy, security

by Pip

Differential Privacy

Taekwondo source

Cynthia Dwork is a computer scientist who is a Distinguished Scientist at Microsoft Research. She has done great work in many areas of theory, including security and privacy.

Today Ken and I wish to talk about the notion of differential privacy and Dwork’s untiring advocacy of it.
Read more…

Where Hard Meets Easy

January 31, 2015

tags: busy beaver, chaos, congruence, Joseph Ford, Turing machines, uncomputability

by Pip

Some hard to compute functions are easy modulo a number

Georgia Tech source

Joseph Ford was a physicist at Georgia Tech. He earned his undergrad degree here in 1952, and after earning his PhD at Johns Hopkins, went to work for two years at Union Carbide in Niagara Falls before joining the University of Miami and then coming back to Tech. He was possibly lured back into academia by considering a paradox studied by Enrico Fermi, John Pasta, Stanislaw Ulam, and Mary Tsingou in the mid-1950s. The paradox is that periodic rather than ergodic motion can often result in complicated systems.

Today we wish to present a simple observation about hard-to-compute functions.
Read more…

Why is Congruence Hard to Learn?

January 25, 2015

tags: Babbage, congruence, Denys Fisher, education, Gauss, Grothendieck, Legendre, modulo, number theory, rings, Spirograph

by Pip

Gears and rings…

Flickr source:

Denys Fisher was a British engineer and maker of board games and other toys. In 1965 he invented the Spirograph toy. Some speculate that he was influenced by the designs of the artist, composer, and film animator John Whitney, whose opening sequence for Alfred Hitchcock’s 1958 film “Vertigo” is considered the first use of computer graphics in cinema. The Spirograph toy involves drawing with a pen guided by a gear with m teeth going around inside a ring or around a track or other gear with x teeth. The kind of design you get depends on how x relates to m.

Today Ken and I want to talk about a basic notion of mathematics and theory that is simple to define, very useful, and yet seems to be tough for some students to get.
Read more…

	Helpful Linker on News on Intermediate Prob…
	Martin Schwarz on News on Intermediate Prob…
	Yahiko on Space Is Easier Than Time
	News on Intermediate… on Who’s Afraid of Natural…
	News on Intermediate… on And Then There Were Two
	Sunkhirous Yadegar on Mathematical Intuition—W…
	Paul Hartzer on Why is Congruence Hard to…
	a on The Right Stuff of Emptin…
	Emi on The Right Stuff of Emptin…
	Michaël Cadilhac on The Right Stuff of Emptin…
	The Fundamental Grou… on Computational Topology
	KWRegan on The Right Stuff of Emptin…
	Guy on A Computer Chess Analysis Inte…
	kamouna on The Right Stuff of Emptin…
	m50d on The Right Stuff of Emptin…

Gödel’s Lost Letter and P=NP

a personal view of the theory of computation

News on Intermediate Problems

Why MCSP is Hard to Harden

Randomized Reductions to MCSP

Open Problems

The Right Stuff of Emptiness

Ada the Amplifier

Still A Brilliant Idea

Cynthia Dwork and a Brilliant Idea

Where Hard Meets Easy

Why is Congruence Hard to Learn?

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

Follow “Gödel's Lost Letter and P=NP”