article

Free access

Proof verification and the hardness of approximation problems

Authors:

Rajeev Motwani,

Mario SzegedyAuthors Info & Claims

Journal of the ACM (JACM), Volume 45, Issue 3

Pages 501 - 555

https://doi.org/10.1145/278298.278306

Published: 01 May 1998 Publication History

Abstract

We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided “proof” with probability at least 1/2. Our result builds upon and improves a recent result of Arora and Safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length).

As a consequence, we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP = P. The class MAX SNP was defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an N-vertex graph to within a factor of N^ε is NP-hard.

References

[1]

ARORA, S. 1994. Probabilistic checking of proofs and hardness of approximation problems. Ph.D dissertation. Univ. California, Berkeley, Berkeley, Calif. Available from http://www.cs.princeton. edu/-arora.

[2]

ARORA, S. 1996. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Sciences. IEEE, New York, pp. 2-12.

[3]

ARORA, S., BABAI, L., STERN, J., AND SWEEDYK, Z. 1997. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54, 2 (Apr.), 317-331.

Digital Library

[4]

ARORA, S., AND LUND, C. 1996. Hardness of approximations. In Approximation Algorithms for NP-Hard Problems, D. Hochbaum, ed. PWS Publishing, Boston, Mass., pp. 339-446.

[5]

ARORA, S., MOTWANI, R., SAFRA, S., SUDAN, M., AND SZEGEDY, M. 1992. PCP and approximation problems. Unpublished note.

[6]

ARORA, S., AND SAFRA, S. 1998. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1 (Jan.), 70-122.

Digital Library

[7]

ARORA, S., AND SUDAN, M. 1997. Improved low degree testing and its applications. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 485-495.

[8]

AUSIELLO, G., D'ATRI, A., AND PROTASI, M. 1980a. Structure preserving reductions among convex optimization problems. J. Comput. Syst. Sci. 21, 136-153.

[9]

AUSIELLO, G., MARCHETTI-SPACCAMELA, A., AND PROTASI, M. 1980b. Towards a unified approach for the classification of NP-complete optimization problems. Theoret. Comput. Sci. 12, 83-96.

[10]

BABAI, L. 1985. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, pp. 421-429.

[11]

BABAI, L. 1993. Transparent (holographic) proofs. In Proceedings of the lOth Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 665. Springer-Verlag, New York, pp. 525-534.

[12]

BABAI, L., AND FORTNOW, L. 1991. Arithmetization: a new methods in structural complexity theory. Computat. Complex. 1, 41-66.

[13]

BABAI, L., FORTNOW, L., LEVIN, L., AND SZEGEDY, M. 1991a. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 21-31.

[14]

BABAI, L., FORTNOW, L., AND LUND, C. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Comptat. Complex. 1, 3-40.

[15]

BABAI, L., AND FRIEDL, K. 1993. On slightly superlinear transparaent proofs. Univ. Chicago Tech. Rep. CS-93-13.

[16]

BABAI, L., AND MORAN, S. 1988. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 254-276.

Digital Library

[17]

BEAVER, D., AND FEIGENBAUM, J. 1990. Hiding instances in multioracle queries. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 415. Springer-Verlag, New York.

[18]

BELLARE, M. 1993. Interactive proofs and approximation: Reductions from two provers in one round. In Proceedings of the 2nd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 266-274.

[19]

BELLARE, M., COPPERSMITH, D., HASTAD, J., Kiwi, M., AND SUDAN, M. 1996. Linearity testing in characteristic two. IEEE Trans. Inf. Theory 42, 6 (Nov.), 1781-1795.

[20]

BELLARE, M., GOLDREICH, O., AND SUDAN, M. 1995/1998. Free bits, PCPs and non-approximability--towards tight results. SIAM J. Comput., to appear. (Preliminary version in Proceedings of the 36th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1995, pp. 422-431. Full version available as TR95-024 of ECCC, the Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier.de/eccc/.)

[21]

BELLARE, M., GOLDWASSER, S., LUND, C., AND RUSSELL, A. 1993/1994. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, 1993, pp. 294-304. (See also errata sheet in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. ACM, New York, 1994, p. 820.)

[22]

BELLARE, M., AND ROGAWAY, P. 1993/1995. The complexity of approximating a nonlinear program. J. Math. Prog. B 69, 3 (Sept. 1995), 429-441. Also in Complexity of Numerical Optimization, P. M. Pardalos, ed. World Scientific, 1993.

[23]

BELLARE, M., AND SUDAN, M. 1994. Improved non-approximability results. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 184-193.

[24]

BEN-OR, M., GOLDWASSER, S., KILIAN, J., AND WIGDERSON, A. 1988. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, pp. 113-131.

[25]

BERMAN, P., AND SCHNITGER, G. 1992. On the complexity of approximating the independent set problem. Inf. Comput. 96, 77-94.

Digital Library

[26]

BERN, M., AND PLASSMANN, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 171-176.

[27]

BLUM, M. 1991. Program checking. In Proceedings of FST&TCS. Lecture Notes in Computer Science, vol. 560. Springer-Verlag, New York, pp. 1-9.

[28]

BLUM, A., JIANG, T., LI, M., TROMP, J., AND YANNAKAKIS, M. 1994. Linear approximation of shortest superstrings. J. ACM 41, 4 (July), 630-647.

Digital Library

[29]

BLUM, M., AND KANNAN, S. 1989. Designing programs that check their work. In Proceedings of the 21st Annual Symposium on the Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, pp. 86-97.

[30]

BLUM, M., LUBY, M., AND RUBINFELD, R. 1993. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 3 (Dec.), 549-595.

Digital Library

[31]

CAI, J., CONDON, A., AND LIPTON, R. 1994. PSPACE is provable by two provers in one round. J. Comput. Syst. Sci. 48, 1 (Feb.), 183-193.

Digital Library

[32]

COHEN, A., AND WIGDERSON, A. 1989. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE, New York.

[33]

CONDON, A. 1991. The complexity of the max word problem, or the power of one-way interactive proof systems. In Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 480. Springer-Verlag, New York.

[34]

CONDON, A., FEIGENBAUM, J., LUND, C., AND SHOR, P. 1993. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 305-314.

[35]

CONDON, A., FEIGENBAUM, J., LUND, C., AND SHOR, P. 1996. Random debaters and the hardness of approximating stochastic functions. SIAM J. Comput. 26, 2 (Apr.), 369-400.

[36]

CooK, S. A. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, May 3-5). ACM, New York, pp. 151-158.

[37]

CRESCENZI, P., AND KANN, V. 1995. A compendium of NP optimization problems. Tech. Rep. SI/RR-95/02, Dipartimento di Scienze dell'Informazione, Uinversita di Roma "La Sapienza". The list is updated continuously. (The latest version is available by anonymous ftp from nada.kth.se, as Theory/Viggo-Kann/compendium.ps.Z.)

[38]

DAHLHAUS, E., JOHNSON, D., PAPADIMITRIOU, C., SEYMOUR, P., AND YANNAKAKIS, M. 1994. The complexity of multiway cuts. SIAM J. Comput. 23, 4, 864-894.

Digital Library

[39]

DE LA VEGA, W., AND LUEKER, G. 1981. Bin packing can be solved within 1 + # in linear time. Combinatorica 1, 349-355.

[40]

FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Com-plexity of Computation, Richard Karp, ed. American Mathematical Society, Providence, R.I.

[41]

FEIGE, U. 1996. A threshold of In n for set cover. In Proceedings of the 28th Annual Symposium on the Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 314-318.

[42]

FEIGE, U., GOLDWASSER, S., LOVASZ, L., SAFRA, S., AND SZEGEDY, M. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2 (Mar.), 268-292.

Digital Library

[43]

FEIGE, U., AND KILIAN, J. 1994. Two prover protocols--Low error at affordable rates. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 172-183.

[44]

FEIGE, U., AND KILIAN, J. 1996. Zero knowledge and chromatic number. In Proceedings of the llth Annual Conference on Complexity Theory. IEEE, New York.

[45]

FEIGE, U., AND LOVASZ, L. 1992. Two-prover one-round proof systems: Their power and their problems. In Proceedings of the 24th Annual Symposium on the Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 733-744.

[46]

FORTNOW, L., ROMPEL, J., AND SIPSER, M. 1994. On the power of multi-prover interactive protocols. Theoret. Comput. Sci. 134, 2 (Nov.), 545-557.

Digital Library

[47]

FRIEVALDS, R. 1979. Fast probabilistic algorithms. In Proceedings of Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 74. Springer-Verlag, New York, pp. 57-69.

[48]

FRIEDL, K., HATSAGI, ZS., AND SHEN, A. 1994. Low-degree testing. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York.

[49]

FRIEDL, K., AND SUDAN, M. 1995. Some improvements to low-degree tests. In Proceedings of the 3rd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 250-260.

[50]

FURER, M. 1995. Improved hardness results for approximating the chromatic number. In Proceed-ings of the 36th Annual Symposium on the Foundations of Computer Science. IEEE, New York.

[51]

GAREY, M., AND JOHNSON, D. 1976. The complexity of near-optimal graph coloring. J. ACM 23, 1 (Jan.), 43-49.

Digital Library

[52]

GAREY, M., AND JOHNSON, D. 1978. "Strong" NP-completeness results: Motivation, examples and implications. J. ACM 25, 499-508.

Digital Library

[53]

GAREY, M., AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York.

[54]

GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1,237-267.

[55]

GEMMELL, P., AND SUDAN, M. 1992. Highly resilient correctors for polynomials. Inf. Proc. Lett. 43, 4 (Sept.), 169-174.

Digital Library

[56]

GEMMELL, P., LIPTON, R., RUBINFELD, R., SUDAN, M., AND WIGDERSON, A. 1991. Self-testing/ correcting for polynomials and for approximate functions. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 32-42.

[57]

GOEMANS, M., AND WILLIAMSON, D. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6 (Nov.), 1115-1145.

Digital Library

[58]

GOLDREICH, O. 1997. A taxonomy of proof systems. In Complexity Theory Retrospective H, L. A. Hemaspaandra and A. Selman, eds. Springer-Verlag, New York.

[59]

GOLDWASSER, S., MICALI, S., AND RACKOFF, C. 1989. The knowledge complexity of interactive proof-systems. SIAM J. Comput. 18, 1 (Feb.), 186-208.

Digital Library

[60]

GRAHAM, R. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.

[61]

H/#kSTAD, J. 1996a. Testing of the long code and hardness for clique. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 11-19.

[62]

H/#kSTAD, J. 1996b. Clique is hard to approximate within n1-E In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science. IEEE, New York.

[63]

H/#kSTAD, J. 1997. Some optimal inapproximability results. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 1-10.

[64]

IBARRA, O., AND KIM, C. 1975. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463-468.

Digital Library

[65]

IMPAGLIAZZO, R., AND ZUCKERMAN, D. 1989. How to recycle random bits. In Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE, New York.

[66]

JOHNSON, D. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256-278.

Digital Library

[67]

KANN, V. 1991. Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Proc. Lett. 37, 27-35.

Digital Library

[68]

KARGER, D., MOTWANI, R., AND RAMKUMAR, G. 1997. On approximating the longest path in a graph. Algorithmica 18, 1 (May), 82-98.

Digital Library

[69]

KARMAKAR, N., AND KARP, R. 1982. An efficient approximation scheme for the one-dimensional bin packing problem. In Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science. IEEE. New York.

[70]

KARP, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, ed. Advances in Computing Research. Plenum Press, New York, pp. 85-103.

[71]

KHANNA, S., LINIAL, N., AND SAFRA, S. 1993. On the hardness of approximating the chromatic number. In Proceedings of the 2nd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 250-260.

[72]

KHANNA, S., MOTWANI, R., SUDAN, M., AND VAZIRANI, U. 1994/1998. On syntactic versus computational views of approximability. In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1994, pp. 819-830. (Also, SIAM J. Comput., to appear.)

Digital Library

[73]

KOLAITIS, P., AND VARDI, M. 1987. The decision problem for the probabilities of higher-order properties. In Proceedings of the 19th Annual Symposium on the Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 425-435.

[74]

LAPIDOT, D., AND SHAMIR, A. 1997. Fully parallelized multi-prover protocols for NEXP-tie. J. Comput. Syst. Sci. 54, 2 (Apr.), 215-220.

Digital Library

[75]

LEVIN, L. 1973. Universarnyie perebornyie zadachi (Universal Search Problems: in Russian). Problemy Peredachi Informatsii 9, 3, 265-266. (A corrected English translation appears in an appendix to Trakhtenbrot {1984}.)

[76]

LIPTON, R. 1991. New directions in testing. In Distributed Computing and Cryptography, vol. 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, J. Feigenbaum and M. Merritt, eds. American Mathematical Society, Providence, R. I., pp. 191-202.

[77]

LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. 1992. Algebraic methods for interactive proof systems. J. ACM 39, 859-868.

Digital Library

[78]

LUND, C., AND YANNAKAKIS, M. 1993. The approximation of maximum subgraph problems. In Proceedings of ICALP 93, Lecture Notes in Computer Science, vol. 700. Springer-Verlag, New York.

[79]

LUND, C., AND YANNAKAKIS, M. 1994. On the hardness of approximating minimization problems. J. ACM 41, 5 (Sept.), 960-981.

Digital Library

[80]

MITCHELL, J. 1998. Guillotine subdivisions approximate polygonal subdivision: Part II - A simple PTAS for geometric k-MST, TSP, and related problems. SIAM J. Comput., to appear.

[81]

MOTWANI, R. 1992. Tech. Rep. Department of Computer Science, Stanford Univ., Stanford, Calif. In Lecture Notes on Approximation Algorithms, Springer-Verlag, New York.

[82]

PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1991. Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, 425-440.

[83]

PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1993. The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1-11.

[84]

PAZ, A., AND MORAN, S. 1981. Non-deterministic polynomial optimization problems and their approximation. Theoret. Comput. Sci. 15, 251-277.

[85]

PHILLIPS, S., AND SAFRA, S. 1992. PCP and tighter bounds for approximating MAXSNP. Manuscript. Stanford Univ., Stanford, Calif.

[86]

POLISHCHUK, A., AND SPIELMAN, D.A. 1994. Nearly linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 194-203.

[87]

RAZ, R. 1995. A parallel repetition theorem. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 447-456.

[88]

RAZ, R., AND SAFRA, S. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 475-484.

[89]

RUBINFELD, R. 1990. A mathematical theory of self-checking, self-testing and self-correcting programs. Ph.D. dissertation. Univ. California, Berkeley, Berkeley, Calif.

[90]

RUBINFELD, R., AND SUDAN, M. 1996. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25, 2 (Apr.), 252-271.

Digital Library

[91]

SAHNI, S. 1975. Approximate algorithms for the 0/1 knapsack problem. J. ACM 22, 115-124.

Digital Library

[92]

SAHNI, S., AND GONZALEZ, T. 1976. P-complete approximation problems. J. ACM 23, 555-565.

Digital Library

[93]

SCHWARTZ, J. 1980. Probabilistic algorithms for verification of polynomial identities. J. ACM 27, 701-717.

Digital Library

[94]

SHAMIR, A. 1992. IP = PSPACE. J. ACM 39, 4 (Oct.), 869-877.

Digital Library

[95]

SUDAN, M. 1992/1996. Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. dissertation. Univ. California, Berkeley, Berkeley, Calif., 1992. Also appears as ACM Distinguished Theses. In Lecture Notes in Computer Science, vol. 1001. Springer- Verlag, New York, 1996.

[96]

TARDOS, G. 1994. Multi-prover encoding schemes and three prover proof systems. In Proceedings of the 9th Annual Conference on Structure in Complexity Theory. IEEE, New York.

[97]

TRAKHTENBROT, B. 1984. A survey of Russian approaches to Perebor (brute-force search) algorithms. Ann. Hist. Comput. 6, 384-400.

Digital Library

[98]

WELCH, L., AND BERLEKAMP, E. 1986. Error correction of algebraic block codes. US Patent Number 4,633,470.

[99]

YANNAKAKIS, M. 1994. On the approximation of maximum satisfiability. J. Algorithms 17, 3 (Nov.), 475-502.

Digital Library

[100]

ZUCKERMAN, D. 1996. On unapproximable versions of NP-complete problems. SIAM J. Comput. 25, 6 (Dec.), 1293-1304.

Digital Library

Cited By

Hong JTsai RChen XLin DYu YLin YLi R(2024)U*Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-23213746:1(837-850)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.3233/JIFS-232137
Cross AHe ZNatarajan ASzegedy MZhu G(2024)Quantum Locally Testable Code with Constant SoundnessQuantum10.22331/q-2024-10-18-15018(1501)Online publication date: 18-Oct-2024
https://doi.org/10.22331/q-2024-10-18-1501
Papadimitriou CPollner TSaberi AWajc D(2024)Online Stochastic Max-Weight Bipartite MatchingMathematics of Operations Research10.1287/moor.2023.138949:3(1607-1628)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2023.1389
Show More Cited By

Index Terms

Proof verification and the hardness of approximation problems
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation

Recommendations

Proof verification and hardness of approximation problems
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science

The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y ...
Efficient checking of polynomials and proofs and the hardness of approximation problems
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 45, Issue 3

May 1998

177 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/278298

Editor:
F. T. Leighton
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Copyright © 1998 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1998

Published in JACM Volume 45, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,079
Total Citations
View Citations
5,059
Total Downloads

Downloads (Last 12 months)695
Downloads (Last 6 weeks)161

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hong JTsai RChen XLin DYu YLin YLi R(2024)U*Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-23213746:1(837-850)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.3233/JIFS-232137
Cross AHe ZNatarajan ASzegedy MZhu G(2024)Quantum Locally Testable Code with Constant SoundnessQuantum10.22331/q-2024-10-18-15018(1501)Online publication date: 18-Oct-2024
https://doi.org/10.22331/q-2024-10-18-1501
Papadimitriou CPollner TSaberi AWajc D(2024)Online Stochastic Max-Weight Bipartite MatchingMathematics of Operations Research10.1287/moor.2023.138949:3(1607-1628)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2023.1389
Barto LButti SKazda AViola CŽivný SSobocinski PLago UEsparza J(2024)Algebraic Approach to ApproximationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662076(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662076
Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
Guruswami VLin BRen XSun YWu KMohar BShinkar IO'Donnell R(2024)Parameterized Inapproximability Hypothesis under Exponential Time HypothesisProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649771(24-35)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649771
Hirahara SOhsaka NMohar BShinkar IO'Donnell R(2024)Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649667(1435-1445)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649667
Kothari PManohar PMohar BShinkar IO'Donnell R(2024)An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649640(776-787)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649640
Bhangale AHarsha PParadise OTal A(2024)Rigid Matrices from Rectangular PCPsSIAM Journal on Computing10.1137/22M149559753:2(480-523)Online publication date: 3-Apr-2024
https://doi.org/10.1137/22M1495597
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents