Power indices and easier hard problems.

*(English)*Zbl 0719.68025For a computational problem A let I(A) be the set of real numbers \(\{\alpha| A\in DTIME(2^{n\alpha})\}\). Define power-index(A) to be the greatest lower bound of I(A). The authors make the following satisfiability hypothesis: power-index(SAT)\(=1\), and use it to characterize the power index of many other NP-complete problems. For instance, it is shown that power index of CLIQUE and PARTITION is 1/2.

In addition, the authors introduce the notion of structure tree for a given CNF formula. They use the structure tree, together with separator arguments, to show that a 3CNF formula F can be tested for satisfiability in time \(| F| \cdot v^{o(\sqrt{v+c})}\), where v is the number of variables in F and c is the maximum number of crossovers needed in a planar layout of F.

In addition, the authors introduce the notion of structure tree for a given CNF formula. They use the structure tree, together with separator arguments, to show that a 3CNF formula F can be tested for satisfiability in time \(| F| \cdot v^{o(\sqrt{v+c})}\), where v is the number of variables in F and c is the maximum number of crossovers needed in a planar layout of F.

Reviewer: G.Slutzki (Ames)

##### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

##### Software:

PARTITION
PDF
BibTeX
Cite

\textit{R. E. Stearns} and \textit{H. B. Hunt III}, Math. Syst. Theory 23, No. 4, 209--225 (1990; Zbl 0719.68025)

Full Text:
DOI

##### References:

[1] | S. Arnborg, J. Lagergren, and D. Seese, Which problems are easy for tree-decomposable graphs?, unpublished manuscript, 1987. · Zbl 0662.03030 |

[2] | H. L. Bodlaender, Dynamic programming on graphs with bounded tree width, Technical Report RUU-CS-87-22, Dept. of Computer Science, University of Utrecht, Utrecht, The Netherlands, 1987. |

[3] | S. A. Cook, The complexity of theorem-proving procedures,Proc. Third Annl. ACM Symp. on Theory of Computing, pp. 151–158, 1971. · Zbl 0253.68020 |

[4] | S. A. Cook, Short propositional formulas represent nondeterministic computations,Inform. Process. Lett., vol. 26, pp. 269–270, 1988. · Zbl 0633.68034 |

[5] | A. K. Dewdney, Linear time transformations between combinatorial problems,Internat. J. Comput. Math., vol. 11, pp. 91–110, 1982. · Zbl 0478.68071 |

[6] | A. K. Dewdney, Generic reduction computers, Report No. 141, Dept. of Computer Science, University of Western Ontario, 1985. · Zbl 0636.68022 |

[7] | M. R. Garey, R. L. Graham, and D. S. Johnson, SomeNP-complete geometric problems,Proc. 8th Ann. ACM Symp. on Theory of Computing, pp. 10–22, 1976. |

[8] | M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979. · Zbl 0411.68039 |

[9] | H. B. Hunt III, On the time and tape complexity of languages, Ph.D. dissertation, Dept. of Computer Science, Cornell University, Ithaca, NY, 1973. |

[10] | H. B. Hunt III, S. S. Ravi, and R. E. Stearns, Separators, graphical homomorphisms, chromatic polynomials (extended Abstract),Proc. 26th Ann. Allerton Conf. on Communications, Control, and Computing, pp. 788–797, 1988. |

[11] | H. B. Hunt III and R. E. Stearns, Nonlinear algebra and optimization on rings are ”hard”,SICOMP, vol. 16, pp. 910–929, 1987. · Zbl 0686.68037 |

[12] | H. B. Hunt III and R. E. Stearns, The complexity of very simple Boolean formulas with applications,SICOMP, vol. 19, pp. 44–70, 1990. Also appears as Technical Report TR 87-23, Dept. of Computer Science, SUNY at Albany, Albany, NY, 1987. · Zbl 0696.68060 |

[13] | D. S. Johnson and C. H. Papadimitriou, Computational complexity, inThe Traveling Salesman Problem, ed. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, pp. 37–86, Wiley, New York, 1985. |

[14] | R. M. Karp, reducibility among combinatorial problems, inComplexity and Computer Computations, ed. R. E. Miller and J. W. Thatcher, pp. 85–103, Plenum, New York, 1972. |

[15] | R. L. Lipton and R. E. Tarjan, Applications of a planar separator theorem,SICOMP, vol. 9, pp. 615–629, 1980. · Zbl 0456.68077 |

[16] | B. Monien and I. H. Sudborough,Bounding the Bandwidth of NP-Complete Problems, Lecture Notes in Computer Science, vol. 100, pp. 279–292, Springer Verlag, Berlin, 1981. · Zbl 0454.68072 |

[17] | C. H. Papadimitriou, The Euclidean traveling salesman problem isNP-complete,Theoret. Comput. Sci., vol. 4, pp. 237–244, 1977. · Zbl 0386.90057 |

[18] | S. S. Ravi and H.B. Hunt III, Application of planar separator theorem to counting problems,Inform. Process. Lett., vol. 25, pp. 317–321, 1987. · Zbl 0653.68064 |

[19] | N. Robertson and P. D. Seymour, Graph minors II, algorithmic aspects of tree-width,J. Algorithms, vol. 7, pp. 309–322, 1986. · Zbl 0611.05017 |

[20] | J. M. Robson, A new proof of theNP completeness of satisfiability,Proc. 2nd Australian Computer Science Conf. pp. 62–69, 1979. |

[21] | J. M. Robson, Subexponential algorithms for someNP-complete problems, unpublished manuscript, 1985. |

[22] | A. Rosenthal, Dynamic programming is optimal for nonserial optimization problems,SICOMP, vol. 11, pp. 47–59, 1982. · Zbl 0479.90081 |

[23] | S. K. Sahni, Some subexponentially recognizableNP-complete languages, Technical Report 74-14, Computer Science Dept., University of Minnesota, 1974. |

[24] | T. J. Schaefer, The complexity of satisfiability problems,Proc. 10th Ann. ACM Symp. on Theory of Computing, pp. 216–226, 1978. · Zbl 1282.68143 |

[25] | C. P. Schnorr, Satisfiability is quasi-linear complete in NQL,J. Assoc. Comput. Mach., vol. 25, pp. 136–145, 1978. · Zbl 0364.68056 |

[26] | R. E. Stearns and H. B. Hunt III, On the complexity of the satisfiability problem and the structure ofNP, Technical Report 86-21, Dept. of Computer Science, SUNY at Albany, Albany, NY, 1986. |

[27] | R. E. Stearns and H. B. Hunt III, Power indices and easierNP-complete problems, Technical Report 88-27, Dept. of Computer Science, SUNY at Albany, Albany, NY, 1988. |

[28] | R. E. Stearns and H. B. Hunt III, Structure trees and their application, Technical Report 90-2, Dept. of Computer Science, SUNY at Albany, Albany, NY, 1990. · Zbl 0719.68025 |

[29] | L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time,Proc. 5th Ann. ACM Symp. on Theory of Computing, pp. 1–9, 1973. · Zbl 0359.68050 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.