Concepedia

Approximation Properties of NP Minimization Classes

Phokion G. Kolaitis, M.N. Thakur

Journal of Computer and System Sciences · 1995 · 61 citations · 12 references

DOI

Concepts

References

12

Approximation algorithms for combinatorial problems

David S. Johnson · Journal of Computer and System Sciences · 1974 · 2.2K citations

, , +12

Generalized first-order spectra and polynomial-time recognizable sets

Ronald Fagin · Medical Entomology and Zoology · 1974 · 834 citations

, , +9

Proof verification and hardness of approximation problems

Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations

, , +16

Relational queries computable in polynomial time

Neil Immerman · Information and Control · 1986 · 648 citations

, , +14

Structure and complexity of relational queries

Ashok K. Chandra, David Harel · Journal of Computer and System Sciences · 1982 · 537 citations

, , +12