How Not To Prove Integer Factoring Is In P
A possible barrier to proofs that factoring is in polynomial time
Mihalis Yannakakis is a Knuth Prize-winning complexity theorist and database expert. With Christos Papadimitriou in 1988, he framed the systematic study of approximation algorithms for -hard optimization problems around the classes and . The same two showed that the case of Traveling Salesman where all distances are 1 or 2 has polynomial-time approximation within of the optimum, but it is -hard to come within a factor of given .
Today I want to talk about a “barrier” to many attempts to prove that integer factoring is in polynomial time, including a recent one that drew on ideas that were first applied to Traveling Salesman and related problems.
The very first of 94 current entries on Gerhard Woeginger’s indispensable page of claims to have resolved vs. is Ted Swart’s attempt to create a linear program to solve Traveling Salesman by relaxing specially-designed integer programs. Alan Frieze and Yannakakis and others kept finding holes in Swart’s polytopes where the desired integer-extrema properties could fail or unwanted integer solutions pop in, and Swart kept trying to patch them. Finally Yannakakis found a “meta-refutation”—a way of showing that no patch could work. To quote the page:
In 1988, Mihalis Yannakakis closed the discussion with his paper “Expressing combinatorial optimization problems by linear programs” (Proceedings of STOC 1988, pp. 223-228). Yannakakis proved that expressing the traveling salesman problem by a symmetric linear program (as in Swart’s approach) requires exponential size. The journal version of this paper has been published in Journal of Computer and System Sciences 43, 1991, pp. 441-466.
This is what we call an unconditional barrier. There are also conditional barriers, which are demonstrations that particular ways of solving one problem (such as proving a lower bound) entail solving an ostensibly harder problem (such as getting an unexpected upper bound or achieving a stronger-seeming lower bound).
Barriers Have Domains
The Maginot Line was a barrier, but it covered only one part of the border. Yannakakis’ barrier has two qualifiers: “symmetric” and “linear” before programs. By the former, it left open the chance of advances that evaded the symmetry condition, which is basically that the effect of the constraints is invariant under permutations of the variables. Such was the feeling that a recent announcement, of the extension of the barrier by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf, was titled:
Decades-old P=NP ‘proof’ finally refuted.
This work shared the Best Paper prize at STOC 2012, and the abstract explains the content simply:
We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.
However, the abstract also emphasizes another qualifier: “the LP’s polytope projects to the traveling salesman polytope.” This allows a possible loophole via different formulations for which projection to the standard TSP polytope used by Swart is not an issue. Then we need to see how far the logic of this paper (and a FOCS 2012 followup noted on the blog of my Tech colleague Pokutta) extends to alternative formulations. But first we also need to note that other kinds of constraint-management “programs” besides LP’s have powerful polynomial-time algorithms.
For those of us in computer science the term “programming” means something special: it covers the act of writing software for any computer of any type. The term is used in many other ways; one that was new to me is how architects use it. Programming is the term they use when collecting information for the design of a new building. See here for a description.
Programming also is a term used to talk about various types of problems. “Linear Programming” refers, of course, to the problem of solving a system of linear inequalities over the reals. This is a terrifically powerful problem, with an almost countless number of practical problems that can be reduced to it. Thanks to the brilliant work of George Dantzig, the powerful simplex method was created to solve them. Only later with the likewise great work of Leonid Khachiyan was it proved to be in , polynomial time.
There are many other types of programming in this sense. Here is a partial list of types that are known to be in polynomial time:
- Convex Programming over variables.
- Integer Programming over a fixed number of variables, i.e .
- Quasi-convex Programming over variables.
All of these are in polynomial time in the size of the inputs, although the second requires the number of variables to be fixed, and on the third we are a bit unsure between the 2001 source cited by this Wikipedia page and this 2006 survey. The best algorithms often use some variation of the ellipsoid method of Khachiyan.
Convex programming means that the objective function has the convexity property: for all constants ,
Quasi-convex means that for all values , the subsets are convex as subsets of . This follows from convexity but is not equivalent to it: think of the one-variable function .
We need to note that all the above problems are closed in the sense that if is a variable one can always add the constraints
for any constants and and still stay in the same type of problems. This trivial observation is the core of the new barrier, and I will explain it in the next section.
Okay you are planning to show that factoring is in polynomial time. One obvious idea is to use powerful previous work—a good problem solving rule is to be “lazy” and use other powerful methods. That is do not attempt to solve factoring, or any problem, from first principles. Use powerful tools.
The way this could be done is to try to reduce the search for the factors of a given to one of the above programming problems. Here is an example that does not work, but should give the idea:
Note that if and must be integers, then the min would be zero when and are nontrivial factors of . If this type of program were known to be in polynomial time, then we would be done. The trouble is that it is not. The function being minimized is not quasi-convex for example.
But suppose that you found a much more clever encoding into one of the programming types and the proof was correct. Here is the barrier: add the constraint . This means that you are finding not just any factor of , but a factor that is in a given interval. This small change moves factoring to a problem that is -complete under randomized reductions. See this February 2011 StackExchange thread and our own earlier discussion for details on this.
Barrier: If there is a program whose minima are integer factorings, belonging to one of the polynomial-time genres that are closed under adding constraints of the form , then is in randomized polynomial time.
…And a Loophole?
As observed on the thread, the -hardness result goes away if is forced to be a prime factor. There are ways to enforce this, for instance by changing the objective function of the above example to
Presupposing other parts still work to make extrema occur at integers, a min less than is achievable only by a factoring, and the resulting value is minimized when is the least factor of —which is always prime.
However, this kind of change may disturb quasi-convexity or other properties the objective function needs for the program to belong to the chosen class. And even so, if the formulation you are attempting to use would extend to cases where any factoring serves as a minimum, then the above conditional barrier comes back into play.
In summary, if you can reduce factoring to solving a programming problem for and as factors of a given , then you can put into randomized polynomial time. This does not mean that you cannot succeed, nor should you stop trying; it does show that you should be aware that you may be trying to do too much.
Can we make the above barrier into a more formal one? I believe that this would be helpful. Perhaps there is a more general barrier result similar to the ones for Traveling Salesman problem that can be proved.
[added to paragraph after bulleted mention of quasi-convex programming, in response to query in comments]