The DOI matches its Crossref record; 21 of the 22 references it cites were found in a registry or an index.
Optimization, approximation, and complexity classes
Open accessOverview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Fromtheproblemstested,MIS,BPP,TSP,Maxcut,WMaxcut,KP,PO, and Max-3-SAT are NP-hard 2,25 ,”
From Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems (2025) · cites this paper as [25]
In the citing paper
“The WMaxcut is both NP-Hard 24 and APX-Hard 25 problems.”
From Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems (2025) · cites this paper as [25]
Citations
Cites
(1979) · Cited by 43,841
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Complexity of Computer Computations
(1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,781
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Generalized first-order spectra and polynomial-time recognizable sets
Fagin, R. (1974) · Medical Entomology and Zoology · Cited by 911
The complexity of optimization problems
Krentel, M. W. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90039-6 · Cited by 441
The Traveling Salesman Problem with Distances One and Two
Papadimitriou, C. H., & Yannakakis, M. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.1.1 · Cited by 412
Self-citationThe Complexity of Near-Optimal Graph Coloring
Garey, M. R., & Johnson, D. S. (1976) · Journal of the ACM · doi:10.1145/321921.321926 · Cited by 326
Structure preserving reductions among convex optimization problems
Ausiello, G., D'Atri, A., & Protasi, M. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90046-x · Cited by 264
Cited by
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
A Tutorial on the Cross-Entropy Method
de Boer, P.-T., Kroese, D. P., Mannor, S., & Rubinstein, R. Y. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-5724-z · Cited by 3,024
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,376
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Metadata
- Authors
- Papadimitriou, C. H., & Yannakakis, M.
- Affiliations
- University of California San Diego (US)
- AT&T (United States) (US)
- Venue
- Journal of Computer and System Sciences
- Publisher
- Elsevier BV
- Published
- 1991-12
- Volume
- 43
- Issue
- 3
- Pages
- 425-440
- ISSN
- 0022-0000 (ISSN-L)
- OpenAlex
- W2038225707
- Cited by
- 1,653
- References
- 22
- Citations by year
- 2026: 16 · 2025: 27 · 2024: 34 · 2023: 28 · 2022: 42 · 2021: 46 · 2020: 35 · 2019: 42 · 2018: 42 · 2017: 28 · 2016: 41 · 2015: 41 · 2014: 53 · 2013: 71 · 2012: 59
- FWCI
- 33.43
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- www.elsevier.com/open-access/userlicense/1.0/ (vor, 7899 d)
- Locations
- Journal of Computer and System Sciences (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- optimization problems, approximation algorithms, polynomial-time approximation scheme, complexity classes, NP-completeness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Optimization, approximation, and complexity classes. https://app.cochat.ai/papers/10.1016/0022-0000(91)90023-x
- The paper
- Papadimitriou, C. H., & Yannakakis, M. (1991). Optimization, approximation, and complexity classes. Journal of Computer and System Sciences. https://doi.org/10.1016/0022-0000(91)90023-x
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.