Polynomial-Time Maximisation Classes: Syntactic Hierarchy

• Autorzy: Bueno O. , Manyem P.
• Języki publikacji: EN

Abstrakty

EN

In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as P, NP, L and NL. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [13], we characterised the optimisation versions of P via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound NP (not just P) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application - we show that the Bin Packing problem with online LIB constraints can be approximated to within a Q(logn) bound, by providing a syntactic characterisation for this problem.

Słowa kluczowe

EN

Descriptive Complexity; finite model theory; syntactic hierarchy; optimization; quantifier complexity; quantifier alternation; Existential Second Order Logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 111--133
• Opis fizyczny: bibliogr. 20 poz., tab.

Twórcy

autor

Bueno O.

autor

Manyem P.

• Centre for Informatics and Applied Optimisation, School of IT and mathematical Sciences, University of Ballarat, Mount Helen, VIC 3350, Australia,

Bibliografia

• [1] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and Intractability of Approximation Problems, Journal of the ACM, 45(3), 1998, 501-555.
• [2] E. Grädel: The expressive power of second order Horn logic, STACS 1991: Proceedings of the 8th annual symposium on Theoretical aspects of computer science - Lecture Notes in Computer Science 280, Springer-Verlag, 1991.
• [3] Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computations (R. Karp, Ed.), SIAM-AMS Proceedings (no.7), 1974, 43-73.
• [4] Finlay, L., Manyem, P.: Online LIB Problems: Heuristics for Bin Covering and Lower Bounds for Bin Packing, RAIRO - Operations Research, 39(3), 2005, 163-183.
• [5] Garey,M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman (New York), 1979.
• [6] Greenlaw, R., Hoover, H. J., Ruzzo, W.: Limits to Parallel Computation: P-Completeness Theory, Oxford University Press, 1995.
• [7] Håstad, J.: Some Optimal Inapproximability Results, ACM-STOC 1997: Proceedings of the 29th ACM Symposium on the Theory of Computing, 1997.
• [8] Immerman, N.: Descriptive Complexity, Springer-Verlag, 1999.
• [9] Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability, SIAM Journal of Computing, 28(1), 1998, 164-191.
• [10] Kohli, R., Krishnamurti, R.,Mirchandani, P.: TheMinimumSatisfiability Problem, SIAMJournal of Discrete Mathematics, 7, 1994, 275-283.
• [11] Kolaitis, P., Thakur, M.: Logical Definability of NP-Optimisation Problems, Information and Computation, 115(2), December 1994, 321-353.
• [12] Kolaitis, P., Thakur,M.: Approximation Properties of NP-Minimisation Problems, Journal of Computer and System Sciences, 50, 1995, 391-411.
• [13] Manyem, P.: Syntactic Characterisations of Polynomial Time Optimisation Classes, Technical report, Arxiv. Org at Cornell University library, 2006, Available at http://arxiv.org/pdf/cs.CC/0606050 (underjournal review).
• [14] Medina, J., Immerman, N.: A Syntactic Characterization of NP-Completeness, IEEE Symposium on Logic in Computer Science, 1994.
• [15] Manyem, P.: Bin Packing and CoveringWith Longest Items At The Bottom: OnLine Version, The ANZIAM Journal (formerly Journal of the Austral. Math. Soc., Series B), 43(E), June 2002, E186-E231.
• [16] Panconesi, A., Ranjan, D.: Quantifiers and Approximation, Theoretical Computer Science, 107, 1993, 145-163.
• [17] Papadimitriou, C.: Computational Complexity, Addison-Wesley (Reading, Massachusetts), 1994.
• [18] Papadimitriou, C., Yannakakis, M.: Optimization, Approximation, and Complexity Classes, Journal of Computer and System Sciences, 43(3), December 1991, 425-440.
• [19] Radhakrishnan, J.: Personal Communication, December 2005.
• [20] Zimand, M.: Weighted NP-Optimisation Problems: Logical Definability and Approximation Properties, SIAM Journal of Computing, 28(1), 1998, 36-56.