The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Abstract
This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Principles of database and knowledge-base systems
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5107 · Cited by 2,683
The complexity of satisfiability problems
Schaefer, T. J. (1978) · Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 · doi:10.1145/800133.804350 · Cited by 1,737
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Graph minors. II. Algorithmic aspects of tree-width
Robertson, N., & Seymour, P. D. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90023-4 · Cited by 1,542
(1988) · Computer Science Press, Inc. eBooks · Cited by 1,435
Generalized first-order spectra and polynomial-time recognizable sets
Fagin, R. (1974) · Medical Entomology and Zoology · Cited by 828
On the Structure of Polynomial Time Reducibility
Ladner, R. E. (1975) · Journal of the ACM · doi:10.1145/321864.321877 · Cited by 781
On the complexity of H-coloring
Hell, P., & Nešetřil, J. (1990) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(90)90132-j · Cited by 665
Erdös, P. (2009) · Classic Papers in Combinatorics · doi:10.1007/978-0-8176-4842-8_19 · Cited by 611
Group-Theoretic Algorithms and Graph Isomorphism
(1982) · Lecture Notes in Computer Science · doi:10.1007/3-540-11493-9 · Cited by 196
Cited by
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
Conjunctive-query containment and constraint satisfaction
Kolaitis, P. G., & Vardi, M. Y. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275511 · Cited by 387
Self-citation
Metadata
- Authors
- Feder, T., & Vardi, M. Y.
- Venue
- SIAM Journal on Computing
- Published
- 1998-01
- Volume
- 28
- Issue
- 1
- Pages
- 57-104
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2150339067
- Cited by
- 1,030
- References
- 19
- FWCI
- 13.06
- Type
- journal article
- Language
- en
- Open access
- closed
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: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. https://app.cochat.ai/papers/10.1137/s0097539794266766
- The paper
- Feder, T., & Vardi, M. Y. (1998). The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing. https://doi.org/10.1137/s0097539794266766
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.