Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-26T07:53:10.488Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE

Published online by Cambridge University Press:  12 September 2008

Oleg Verbitsky
Oleg Verbitsky
Affiliation:
Department of Mathematical Logic, Mechanical and Mathematical Faculty, Moscow State University, Moscow, Russia 119899
Get access Rights & Permissions [Opens in a new window]

Abstract

We focus our attention on the class RMAX(2) of NP optimization problems. Owing to recent developments in interactive proof techniques, RMAX(2) was shown to be the lowest class of logical classification that contains problems hard to approximate. Namely, the RMAX(2)-complete problem MAX CLIQUE (of finding the size of the largest clique in a graph) is not approximable in polynomial time within any constant factor unless NP=P.

We are interested in problems inside RMAX(2) that are not known to be complete but are still hard to approximate. We point out that one such problem is MAXlog n, n, considered by Berman and Schnitger: given m conjunctions, each of them consisting of log m propositional variables or their negations, find the maximal number of simultaneously satisfiable conjunctions. We also obtain the approximation hardness results for some other problems in RMAX(2). Finally, we discuss the question of whether or not the problems under consideration are RMAX(2)-complete.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 2 , June 1995 , pp. 167 - 180
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Arora, S., Lund, C, Motwani, R., Sudan, M. and Szegedy, M. (1992) Proof verification and hardness of approximation problems. In: Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, 14–23.CrossRefGoogle Scholar
[2]Arora, S. and Safra, S. (1992) Probabilistic checking of proofs; a new characterization of NP. In: Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science 2–13.Google Scholar
[3]Azar, Y. (1992) Personal communication cited in [1].Google Scholar
[4]Babai, L. (1985) Trading group theory for randomness. In: Proceedings of the llth ACM STOC 421–429.CrossRefGoogle Scholar
[5]Babai, L. and Luks, E.M. (1983) Canonical labeling of graphs. In: Proceedings of the 15th ACM STOC 171–183.CrossRefGoogle Scholar
[6]Babai, L., Fortnow, L. and Lund, C. (1991) Non-deterministic exponential time has two-prover interactive protocols. Computational complexity 1(1) 3–40.CrossRefGoogle Scholar
[7]Bellare, M. (1992) Interactive proofs and approximation. IBM Research Report RC 17969.Google Scholar
[8]Bellare, M., Goldwasser, S. and Russell, A. (1992) Low complexity multi-prover proofs with applications to approximation, (manuscript) The expanded version: Bellare M., Goldwasser S., Lund C. and Russell A. Efficient probabilistically checkable proofs and applications to approximation. In: 25th ACM STOC 294–304.Google Scholar
[9]Bellare, M. and Rogaway, P. (1992) The complexity of approximating a nonlinear program. IBM Research Report RC 17831.Google Scholar
[10]Ben-Or, M., Goldwasser, S., Kilian, J. and Wigderson, A. (1988) Multi-prover interactive proofs: how to remove intractability assumption. In: Proceedings of the 20th ACM STOC 113–131.Google Scholar
[11]Berman, P. and Schnitger, G. (1989) On the complexity of approximating the Independent Set problem. In: Proceedings of the STACS'89, Lecture Notes in Computer Science, 349, 256–268, Springer-Verlag.Google Scholar
[12]Boppana, R.B., Håstad, J. and Zachos, S. (1987) Does co-NP have short interactive proofs? Information Processing Letters 25 127–132.CrossRefGoogle Scholar
[13]Crescenzi, P. and Panconesi, A. (1989) Completeness in approximation classes. In: Proceedings of the FCT'89, Lecture Notes in Computer Science, 380 116–126, Springer-Verlag, New York/Berlin.Google Scholar
[14]Erdös, P. and Spenser, J. (1974) Probabilistic methods in combinatorics, Akademiai Kiado, Budapest.Google Scholar
[15]Feige, U. (1991) On the success probability of the two prover in one round proof systems. In: Proceedings of the 6th Structure in Complexity Theory Annual Conference 116–123.Google Scholar
[16]Feige, U., Goldwasser, S., Lovász, L., Safra, S. and Szegedy, M. (1991) Approximating clique is almost JVP-complete. In: Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science 2–12.Google Scholar
[17]Feige, U. and Lovász, L. (1992) Two-prover one-round proof systems: their power and their problems. In: Proceedings of the 24th ACM STOC 733–744.Google Scholar
[18]Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability. A guide to the theory of NP-completeness, W. H. Freeman.Google Scholar
[19]Goldwasser, S., Micali, S. and Rackoff, C. (1989) The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1) 186–208.CrossRefGoogle Scholar
[20]Karger, D., Motwani, R. and Ramkumar, G.D.S. (1992) On approximating the longest path in a graph. (Manuscript, cited in [1]).CrossRefGoogle Scholar
[21]Kilian, J. (1990) Strong separation models of multi-prover interactive proofs. DIM ACS Workshop on Cryptography.Google Scholar
[22]Kolaitis, Ph. G. and Thakur, M.N. (1991) Approximation properties of NP minimization classes. In: Proceedings of the 6th Structure in Complexity Theory Annual Conference353–366.CrossRefGoogle Scholar
[23]Kolaitis, Ph. G. and Thakur, M.N. (1990) Logical definability of NP optimization problems. Technical Report UCSC-CRL-90–48, Computer and Information Sciences, University of California, Santa Cruz.Google Scholar
[24]Ladner, R.E. (1975) On the structure of polynimial-time reducibility. Journal of ACM 22(1) 155–171.CrossRefGoogle Scholar
[25]Lapidot, D. and Shamir, A. (1991) Fully parallelized multi-prover protocol for NEXP-time. In: Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science 13–18.Google Scholar
[26]Lund, C., Fortnow, L., Karloff, H. and Nisan, N. (1992) Algebraic methods for interactive proof systems. J. Assoc. Comput. Mach. 39 859–868.CrossRefGoogle Scholar
[27]Lund, C. and Yannakakis, M. (1993) On the hardness of approximating minimization problems. In: Proceedings of the 25th ACM STOC 286–293.Google Scholar
[28]Panconesi, A. and Ranjan, D. (1993) Quantifiers and approximation. Theoretical Computer Science 107 145–163.CrossRefGoogle Scholar
[29]Papadimitriou, C. and Steiglitz, K. (1982) Combinatorial optimization: algorithm and complexity, Prentice-Hall.Google Scholar
[30]Papadimitriou, C.H. and Yannakakis, M. (1991) Optimization, approximation and complexity classes. Journal of Computer and System Sciences 43 425–440.CrossRefGoogle Scholar
[31]Schöning, U. (1987) Graph isomorphism is in the low hierarchy. In: Proceedings of the STACS'87. Springer-Verlag. Lecture Notes in Computer Science 247 114–124.CrossRefGoogle Scholar
[32]Shamir, A. (1992) IP = PSPACE. J. Assoc. Comput. Mach. 39 869–877.CrossRefGoogle Scholar
[33]Verbitsky, O. (1993) MIP is recognizable in constantly many rounds. (Manuscript – full version:) Izvestiya RAN, seriya matematicheskaya 57(3) 152–178.Google Scholar