From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: NP-complete problems & algorithms to solve them Date: 8 Mar 2000 08:52:43 -0800 Newsgroups: sci.math Summary: [missing] David Bernier writes: > Suppose we consider the NP-complete problem SAT ( cf. [1] ) . > Clearly, no polynomial-time deterministic algorithm is known for > SAT, else I think that would imply P=NP. So I was wondering what > the time growth-rate of the fastest known algorithms for SAT > (or any other NP-complete problem) look like; how far are > the fastest known algorithms from being polynomial-time ? They are generally of the form 2^(f(n)) for some polynomially bounded function f, but the function (or the base of exponent) can vary considerably from problem to problem. I think for SAT itself the best algorithm is the obvious O(m 2^n), but 3-SAT is much smaller, I forget the exact bound but I think it's somewhere around 1.3^n. The obvious algorithm for TSP takes time O(n!) but there is a simple dynamic program that improves this to O(n^2 2^n). Problems on planar graphs, or two-dimensional geometric problems, such as the planar or geometric TSP problems, can often be solved in time exponential in O(sqrt n) or O(sqrt n log n) instead of exponential in n by using a separator-based divide and conquer. You might find interesting the program of the recent DIMACS workshop on exact algorithms for NP-hard problems, http://1013seopc.eecs.uic.edu/eecs361//beigel/FESNP/ -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: haoyuep@aol.com (Dan Hoey) Subject: Re: NP-complete problems & algorithms to solve them Date: 09 Mar 2000 05:17:29 GMT Newsgroups: sci.math David Eppstein writes: >David Bernier asks: >> ... the time growth-rate of the fastest known algorithms for SAT >> (or any other NP-complete problem).... >They are generally of the form 2^(f(n)) for some polynomially bounded >function f, but the function (or the base of exponent) can vary >considerably from problem to problem. I'd say that for just about all the NP-complete problems I've seen there is an algorithm for time O(exp(k n)) = O(alpha ^ n) for some constants alpha=exp(k). It is hard to pin down more closely, because the encoding of the problem affects the parameter--if we can compress the input by a factor of b, we effectively multiply k by b (or raise alpha to the b'th power) using the same algorithm (plus a subexponential-time decompression step). >I think for SAT itself the best algorithm is the obvious O(m 2^n), but >3-SAT is much smaller.... I'm pretty sure SAT is one of the NP-complete problems with the more bloated natural representations, which makes k (or alpha) relatively small. Algorithms reported in 1993 had alpha down to 1.04 or so (k=ln(2)/17) if we measure problem size by the number of variables. I seem to recall there were some people who thought the number of literals was a better measure, and had a fairly small alpha. There's some work on determining the ratio of literals to clauses that makes for hard SAT problems. You may be able to find pointers to these results at ftp://dimacs.rutgers.edu/pub/challenge/; if you can't find anything let me know and I'll see what I can find in my files. Dan Hoey posted and e-mailed ============================================================================== From: David Bernier Subject: Re: NP-complete problems & algorithms to solve them Date: Thu, 09 Mar 2000 06:39:05 GMT Newsgroups: sci.math In article <8a60gr$4sj@euclid.ics.uci.edu>, eppstein@euclid.ics.uci.edu (David Eppstein) wrote: [...] > > SAT, else I think that would imply P=NP. So I was wondering what > > the time growth-rate of the fastest known algorithms for SAT > > (or any other NP-complete problem) look like; how far are > > the fastest known algorithms from being polynomial-time ? > > They are generally of the form 2^(f(n)) for some polynomially bounded > function f, but the function (or the base of exponent) can vary > considerably from problem to problem. > > I think for SAT itself the best algorithm is the obvious O(m 2^n), but > 3-SAT is much smaller, I forget the exact bound but I think it's > somewhere around 1.3^n. The obvious algorithm for TSP takes time O(n!) > but there is a simple dynamic program that improves this to O(n^2 2^n). > > Problems on planar graphs, or two-dimensional geometric problems, such > as the planar or geometric TSP problems, can often be solved in time > exponential in O(sqrt n) or O(sqrt n log n) instead of exponential in n > by using a separator-based divide and conquer. There have been about five replies to my post, which I appreciate. I am wondering to what extent the raw input to a given type of problem might be able to be polynomially compressed and polynomially decompressed. Say we have an NP-complete problem XYZ whose raw input typically is quite compressible in polynomial time by a function f, and where the decompression is polynomial time in the number of bits in the compressed string for the function (algorithm) g. [ Note: Suppose the compression went from x bits to sqrt(x) bits roughly; I think polynomial in x and polynomial in sqrt(x) are equivalent when expressed as functions of x.] By using a strong polynomial-time compression/decompression algorithm, maybe XYZ would change from being exp(sqrt(x)) in the uncompressed x-bit representation of an instance of XYZ, but it might look like exp(y) in the y bits obtained from applying the compression algorithm f to the original x bits coding an instance of XYZ. I'd be interested in knowing if this scenario occurs, i.e. if a best known algorithm would run O(sqrt(n)) when the input is not compressed polynomially, and maybe O(n) when the input is presented in polynomially compressed format. David Bernier Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: NP-complete problems & algorithms to solve them Date: 9 Mar 2000 09:13:30 -0800 Newsgroups: sci.math David Bernier writes: > By using a strong polynomial-time compression/decompression > algorithm, maybe XYZ would change from being exp(sqrt(x)) in > the uncompressed x-bit representation of an instance of XYZ, but > it might look like exp(y) in the y bits obtained from applying > the compression algorithm f to the original x bits coding an > instance of XYZ. Actually, the time for a naive exponential search is not so much generally 2^(input size) as 2^(witness size). It is easy to confuse this because for many problems the two are within a constant factor of each other. So compressing the input is not really so relevant, you want to compress the witnesses (by witness I mean e.g. a truth assignment for SAT, or a tour of the input cities for TSP). Many of the algorithms with better worst-case or expected-case time bounds (such as some the ones for SAT that Hoey and I were discussing) can be interpreted as performing some sort of compression on the witnesses, and then searching the smaller compressed space. As an aside, this same compression would also be useful in applying quantum computing to NP-complete problems -- Grover's algorithm takes time 2^(witness size / 2). However, some algorithms, in particular the ones for TSP (the general O(n^2 2^n) one as well as the 2^O(sqrt n log n) geometric or planar graph ones) do not simply search the space of witnesses. Rather, they use dynamic programming to build up the solutions to larger subproblems from smaller ones, where the same subproblem may be used multiple times throughout the problem. I don't think it's really possible to interpret these as having anything to do with compression. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: djimenez@cs.utexas.edu (Daniel A. Jimenez) Subject: Re: NP-complete problems & algorithms to solve them Date: 9 Mar 2000 11:30:42 -0600 Newsgroups: sci.math In article <8a7gu9$u4g$1@nnrp1.deja.com>, David Bernier wrote: >Say we have an NP-complete problem XYZ whose raw input typically >is quite compressible in polynomial time by a function f, and >where the decompression is polynomial time in the number of bits >in the compressed string for the function (algorithm) g. >[ Note: Suppose the compression went from x bits to sqrt(x) bits > roughly; I think polynomial in x and polynomial in > sqrt(x) are equivalent when expressed as functions of x.] > >[ some stuff deleted ] > >I'd be interested in knowing if this scenario occurs, i.e. >if a best known algorithm would run O(sqrt(n)) when the input >is not compressed polynomially, and maybe O(n) when the input >is presented in polynomially compressed format. For an upper bound like this, you would have to assume that every instance of XYZ were compressible by your compression algorithm. With a sufficiently concise representation, you would only be able to achieve a constant compression ratio over all strings because of the incompressibility counting argument. -- Daniel Jimenez djimenez@cs.utexas.edu "I've so much music in my head" -- Maurice Ravel, shortly before his death. " " -- John Cage ============================================================================== From: David Eppstein Subject: Re: NP-complete problems & algorithms to solve them Date: Wed, 08 Mar 2000 21:41:33 -0800 Newsgroups: sci.math To: Dan Hoey On 3/9/2000 5:17 AM +0000, Dan Hoey wrote: > I'd say that for just about all the NP-complete problems I've seen there > is an algorithm for time O(exp(k n)) = O(alpha ^ n) for some constants > alpha=exp(k). Perhaps you didn't read the part of my message where I noted that planar and geometric TSP could be solved faster than that, in time O(alpha ^ sqrt(n)) or O(alpha ^ {sqrt(n) log(n)})? It's not a matter of them being encoded inefficiently, it's unreasonable to want to code the coordinates of n cities in fewer than n bits. > I'm pretty sure SAT is one of the NP-complete problems with the > more bloated natural representations, which makes k (or alpha) relatively > small. Algorithms reported in 1993 had alpha down to 1.04 or so > (k=ln(2)/17) if we measure problem size by the number of variables. I seem to recall (but could be mistaken) that this exp(n ln(2)/17)=2^{n/17} is actually for 3-SAT. Anyway, it indicates an interesting difference between theory and practice. In theory, the best worst-case bounds for 3-SAT we can prove are, as I said, more like 1.3^n, which is much better than naively trying all truth assignments but much worse than 2^{n/17}. In practice, on the other hand, some of the worst examples we know how to find are formed by taking a randomly chosen set of cn clauses for some carefully chosen constant c. There is a threshhold effect here -- if c is too small, the examples are easy to satisfy, and if c is too big, they are easy to prove unsatisfiable. The hardest examples happen when c is somewhere around 3 or 4, at the boundary between the satisfiable and unsatisfiable instances. The 2^{n/17} bound is not a proven worst-case bound, it is simply the experimentally observed behavior of a particular good 3-SAT algorithm on these particular examples. Similarly, when I said I didn't know anything better than 2^n for SAT, again I meant worst-case bounds, but one can do better "in practice", whatever that means. What this all means for theoreticians like myself is that there's still plenty of work to do proving better bounds and/or coming up with harder classes of examples, in order to narrow the gap between these two kinds of bounds. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: David Bernier Subject: Re: Status of 'Is P=NP?' Date: Tue, 03 Oct 2000 06:14:23 GMT Newsgroups: sci.math In article , "Larry Shultis" wrote: > > "David Bernier" wrote in message > news:8r9839$um3$1@nnrp1.deja.com... > > In article <9FUB5.109$qR3.54459@homer.alpha.net>, > > "Larry Shultis" wrote: > > > With regard to the SAT boolean circuit approach > > > to proving P=NP, it appears that an algorithm > > > that runs in <= k^2 time is possible, where k is the > > > number of inputs of the variables to the gates > > > making up the circuit. If the number of distinct variables > > [...] > > > > If the number of input variables to the Boolean circuit is k, > > then the number of variable settings is: > > 2*2*2 ... *2 [k times] = 2^k . > > 2^k grows faster than polynomial. > > But the time to calculate the output from a particular set of > values for the variables need not grow at that rate. And it > does not when an actual circuit is giving a set of inputs > currents. > > I was under the impression that the requirement for SAT > was that given an arbitrary boolean logic circuit with v > variables, one would have to show that, for any particular set of > values for those variables, the output value of true or false > could be found in polynomial time. It had nothing to do with > all possible sets of values at the same time being shown > to produce either a true or false output. As I understand it, you are talking about efficient ways of deciding what the output of a boolean circuit is given a set of binary values as input. My understanding of SAT (short for "satisfiability") is consistent with the description at: http://www.isis.ecs.soton.ac.uk/isystems/evolutionary/notes/evol/Decisi on_Problems.html An example of a boolean function is given there: F(x1,x2,x3)=(x1 or x2 or x3)and((not x1) or (not x2))and x3 and x1 "F is satisfiable" means that the truth table of F has at least one "true". For this F, I find that the truth-value is "true" in just one case: x1 TRUE, x2 FALSE, x3 TRUE. If G was another boolean function with zero "trues" in the truth-table, then I think G would be called non-satisfiable. So SAT is a decision problem whose question is: "does the truth-table of F have any "true" in it?" David > When I said "where k is the number of inputs of the variables > to the gates", I meant only those inputs to the gates that are > directly input from the input variable set. For example, input b > may go to several different gates. I do not mean to count > an output from a gate as an input variable to another gate. > When the circuit is seen as just containing only "not" and "or" > gates, it can be represented as an ordered string of variable values > intermixed with values which represent the local depth that a > variable has in that part of the circuit. > For example: The circuit ((a and b) or (not-c and (a and not-b))) > which is not(not-a or not-b) or c or not(not-a or b) > (note that there are three variables (a,b,c) and 5 total inputs of > the variables to parts of the circuit, two not-a and two not-b and > c which actualy is straight through to the output for a total of > five not-gates. In general when all not-not-not... not constructs are > reduced there will be a maximum of k not-gates, where k is > the total number of inputs of the variables to the gates.) > > can be represented by a string [a,2,b,2,3,a,2,b,3,c] for which > there is a linear algorithm composed of a block of conditionals > which works on the string from the left and has a maximum > runing time for all such strings with regard to the time it takes > to process each element of the string. > > When a set of values for the varibles a, b, c are substituted in > the string, the result is similar to a reduction of a set of nested > parentheses with the rules that ()() = () and (())= , i.e.,cancel out > of the string. the numbers in the string keep the arithmetic straight > by giving the relationships between the variable values and > the the parentheses. > In the above string, if the variables have values a=1, b=0, c=0, > the substitution gives [1,2,0,2,3,1,2,0,3,0] where 0 represents > no parenthesis and 1, 2, 3, ... represent nested parentheses. > > 1,2 cancel out, so [0,2,3,1,2,0,3,0] remains > 0,2 is just the 2 so [2,3,1,2,0,3,0] remains > 2,3 cancel out so [1,2,0,3,0] remains > 1,2 cancel out so [0,3,0] remains > 0,3 is just the 3 so [3,0) remains > 3,0 is just the 3 so [3] remains which is same as true. > > since the algorithm, as far as I can see, has a maximum > running time t per reduction step for any of the steps and > t is at least <= k , the running time would be t*k <= k^2. > > I must say that it is quite hard to convey how this works > without G. S. B.'s notation from the book "Laws of Form" > which simplifies things tremendously. > Larry Sent via Deja.com http://www.deja.com/ Before you buy.