From: c-blair@uiuc.edu (Charles Blair) Subject: Re: Factoring and 3-SAT Date: Thu, 18 Oct 2001 13:39:44 GMT Newsgroups: sci.math.research Summary: Reduce integer factorization to a satisfiability problem (3-SAT)? This is a special case of Cook's theorem, which says anything done by a (non-deterministic) Turing machine can be simulated by a suitably constructed instance of satisfiability, or by 3-SAT. I don't think that anyone has shown that factoring has any special features compared to other such problems. Standard reference: Garey and Johnson, COMPUTERS AND INTRACTABILITY ============================================================================== From: Antti Huima Subject: Re: Factoring and 3-SAT Date: 20 Oct 2001 15:04:47 +0300 Newsgroups: sci.math.research c-blair@uiuc.edu (Charles Blair) writes: > gerrynagel@yahoo.com (Gerry Nagel) writes: > > >c-blair@uiuc.edu (Charles Blair) wrote in message... > >> This is a special case of Cook's theorem, which says > >> anything done by a (non-deterministic) Turing machine can > >> be simulated by a suitably constructed instance of satisfiability, > >> or by 3-SAT. > > >I believe Cook said that any NP-complete problem can be converted to > >any other NP-complete problem in polynomial time. I don't believe > >that factoring can be converted to 3-SAT in polynomial time and I > >challenge anyone to come up with an algorithm to do so. From what I > >see, the 3-SAT problem grows exponentially as the number to be > >factored grows linearly. > > What you may be missing is "polynomial-time" means polynomial in > the number of digits. Thus, multiplying two 20-digit numbers in the > "textbook" way is 4 times as much work as multiplying two 10-digit > numbers. So, polynomial in O(log n) where `n' is to be factored. But Gerry maybe claimed that there wouldn't be an algorithm even polynomial in O(n), which is clearly even stronger claim. Anyway, factorization is not known to be NP-complete, but Cook's thm of course allows any NP problem (not only any NP-COMPLETE problem) to be converted to 3-SAT in polynomial time. And factorization is in NP when the problem size is measured by O(log n), as we can guess two factors whose sizes are bounded by O(log n), multiply them by the trivial school method and check the answer, giving something like O((log n)^2), which is polynomial in O(log n). -- Antti Huima ============================================================================== From: dima pasechnik Subject: Re: Factoring and 3-SAT Date: 20 Oct 01 17:05:51 -0400 (EDT) Newsgroups: sci.math.research Gerry Nagel wrote: >> This is a special case of Cook's theorem, which says >> anything done by a (non-deterministic) Turing machine can >> be simulated by a suitably constructed instance of satisfiability, >> or by 3-SAT. > I believe Cook said that any NP-complete problem can be converted to > any other NP-complete problem in polynomial time. this is a rather straightforward consequence of the definition of NP-completness. Cook(-Levin) theorem is something deeper than this. > I don't believe > that factoring can be converted to 3-SAT in polynomial time and I > challenge anyone to come up with an algorithm to do so. From what I > see, the 3-SAT problem grows exponentially as the number to be > factored grows linearly. Converting factoring to 3-SAT can be done in polynomial time, because of the abovementioned theorem (note that factoring can be done on a Turing machine) Then, it's in fact not quite clear what you mean by "factoring". Finding all the factors? Testing whether a given number is a prime? The latter is known to be in NP as well as in coNP. It is commonly believed that the intersection of NP and coNP is properly contained in NP; hence testing whether a number is a prime would not be a NP-complete problem. If you mean factoring as enumerating all the factors, and 3-SAT as finding all the truth assignments, then you should talk about "counting complexity". This version of 3-SAT is usually called #3-SAT. HTH, Dmitrii [reformatted --djr] ============================================================================== From: Keith Ellul Subject: Re: Factoring and 3-SAT Date: Sat, 20 Oct 2001 15:14:24 -0400 Newsgroups: sci.math.research On 17 Oct 2001, Gerry Nagel wrote: > Can anyone provide an algorithm for converting the problem of finding > the factorization of a number into a 3-SAT problem? This looks rather > daunting and since I'm not a researcher myself, I don't have the time > to work this out. > Thanks There's been quite a bit written in response to this, but I don't think that anyone's quite hit it on the head yet. The problem is this: FACTORING is a function problem. That is, you input an integer, and you want the output to be a list of factors. 3-SAT is a decision problem. That is, you input a boolena function in CNF with each clause having 3 variables, and you output YES if there is a satisfying assignment and NO otherwise. So, no, one cannot be reduced to the other. Not because of any computational limits, but simply because they are different kinds of problems. So, we have two choices: 1. Consider the decision-problem version of FACTORING. This is known as COMPOSITES, that is, a number is input, and YES is output if the number is composite (ie, if it can be factored) and no otherwise (if it is prime) This is clearly in NP (a list of factors makes a suitable witness) and so it can be reduced to 3-SAT, since 3-SAT is NP-Complete. Furthermore, this reduction can be done in log-space, which is a subset of poly-time. 2. Consider the function-problem version of 3-SAT, that is, the input is a 3-CNF boolean function, and the output is a satisfying assignment if one exists (and simply "no" otherwise) We will refer to this problem as "F3-SAT". In this case, we are dealing with the class known as FNP (function problems associated with NP). Note this this is deifferent from NP... NP deals with decision problems. Now, FACTORING is clearly in FNP. F3-SAT is complete for FNP, so, FACTORING can be reduced to F3-SAT in log space, and, therefore, in polynomial time. See Chapter 10 of COMPUTATIONAL COMPLEXITY by Papadimitriou for more information on FNP. In particular, Example 10.5 talks specifically about the FACTORING problem. This is also a good book for gerenal complexity stuff, including background to what I wrote in #1 above. I hope that this clarifies things, Keith ============================================================================== From: David desJardins Subject: Re: Factoring and 3-SAT Date: 20 Oct 2001 16:37:45 -0700 Newsgroups: sci.math.research Keith Ellul writes: > 1. Consider the decision-problem version of FACTORING. This is known > as COMPOSITES, that is, a number is input, and YES is output if the > number is composite The usual way to convert what you call a "function problem" into a "decision problem" is to ask the question, "Is the i-th bit of the result equal to 1?" This decision problem ("Is the i-th bit of the smallest nontrivial factor of N equal to 1?") is the problem that would be (and easily is) reduced to 3-SAT. Since you only have to ask a polynomial (actually, linear) number of such questions in order to determine the entire factor, clearly the question of whether a single bit can be determined in polynomial time is equivalent to the question of whether all of the bits can be determined in linear time. Simply testing whether a number is composite is (believed to be) much easier than actually determining the bits of the factor, so changing a factoring problem into just compositeness-testing loses the essence of the problem. David desJardins ============================================================================== From: tchow@lsa.umich.edu Subject: Re: Factoring and 3-SAT Date: 22 Oct 2001 21:16:09 GMT Newsgroups: sci.math.research In article , Gerry Nagel wrote: >Can anyone provide an algorithm for converting the problem of finding >the factorization of a number into a 3-SAT problem? This looks rather >daunting and since I'm not a researcher myself, I don't have the time >to work this out. In Cook and Mitchell's paper, "Finding hard instances of the satisfiability problem: A survey," they state a "SAT challenge:" Report the largest n for which your SAT solver can consistently factor a product of two n-bit primes. This paper is available on Stephen A. Cook's web page at the University of Toronto. I don't know what progress has been made on this SAT challenge, but you could try emailing one of the authors. May I ask why you want such a reduction? It's certainly not a good way to factor large integers (methods based on elliptic curves or sieves are much better). Cook and Mitchell's SAT challenge is intended as a benchmarking tool for evaluating general-purpose SAT algorithms, not as a practical method for factoring. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences