Monotone monadic SNP and constraint satisfaction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Monotone monadic SNP and constraint satisfaction

Full text

Pdf (1.13 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 612 - 622

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Tomás Feder
Moshe Y. Vardi

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 38, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167245 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Aschbacher, personal communication.
	2	F. Afrati , S. S. Cosmadakis, Expressiveness of restricted recursive queries, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.113-126, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73018]
	3	Foto Afrati , Stavros S. Cosmadakis , Mihalis Yannakakis, On Datalog vs. polynomial time (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.13-25, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113415]
	4	L. Bahai, "Monte Carlo algorithms in graph isomorphism testing," (1979).
	5	J. Bang-Jensen , P. Hell, The effect of two cycles on the complexity of colouring by directed graphs, Discrete Applied Mathematics, v.26 n.1, p.1-23, Jan. 1990 [doi>10.1016/0166-218X(90)90017-7]
	6	R. Dechter, "Constraint networks," In Encyclopedia of Artificial Intelligence, 1992, 276- 285.
	7	P. Erd6s, "Graph theory and probability," Canadian J. of Math. 11 (1959), 34-38.
	8	R. Fagin, "Generalized first-order spectra, and polynomial-time recognizable sets," in R. Karp (ed.), Complexity of Computations, AMS, 1974.
	9	Tomás Feder , Donald E. Knuth, Stable networks and product graphs, Stanford University, Stanford, CA, 1992
	10	T. Feder, "Removing inequalities and negation for homomorphism-closed problems," in preparation.
	11	M. Furst, J. E. Hopcroft, and E. Luks, "Polynomial-time algorithms for permutation groups," Proc. 21st IEEE Symp. on Found. of Comp. Sci. (1980), 36-41.
	12	D. M. Goldschmidt, "2-fusion in finite groups," Annals of Math. 99 (1974), 70-117.
	13	Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
	14	Gerd G. Hillebrand , Paris C. Kanellakis , Harry G. Mairson , Moshe Y. Vardi, Tools for Datalog boundedness, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-12, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113414]
	15	C. M. Hoffmann, "Group-Theoretic Algorithms and Graph Isomorphism," Lecture Notes in Comp. Sci. 136 (1982), Springer- Verlag.
	16	P. Kolaitis , M. Vardi, The decision problem for the probabilities of higher-order properties, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.425-435, January 1987, New York, New York, United States [doi>10.1145/28395.28441]
	17	Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of datalog: tools and a case study, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.61-71, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298542]
	18	Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine, v.13 n.1, p.32-44, Spring 1992
	19	Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
	20	V. S. Lakshmanan , A. O. Mendelzon, Inductive pebble games and the expressive power of datalog, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.301-310, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73751]
	21	A. Lubiw, "Some NP-complete problems similar to graph isomorphism," SIAM J. Comput. 10 (1981), 11-21.
	22	P. Meseguer, "Constraint satisfaction problem: an overview," AICOM 2 (1989), 3-16.
	23	Ernst W. Mayr , Ashok Subramanian, The complexity of circuit value and network stability, Journal of Computer and System Sciences, v.44 n.2, p.302-323, April 1992 [doi>10.1016/0022-0000(92)90024-D]
	24	C. H. Papadimitriou and M. Yannakakis, "Optimization, approximation, and complexity classes," J. Comput. Syst. Sci. 43 (1991), 425- 440.
	25	A. A. Razborov, "Lower bounds on monotone complexity of the logical permanent," Math. Notes of the Academy of Sciences of the USSR 37 (1985), 485-493.
	26	Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
	27	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

CITED BY 17

	J. A. Makowsky, Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.487-495, January 07-09, 2001, Washington, D.C., United States
	Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-213, June 01-04, 1998, Seattle, Washington, United States
	Judit Büki , Csaba Szabó, Complexity of homomorphisms to direct products of graphs, Information Processing Letters, v.81 n.4, p.175-178, 28 February 2002
	Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States
	Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002
	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States
	Peter Jeavons , David Cohen , Marc Gyssens, Closure properties of constraints, Journal of the ACM (JACM), v.44 n.4, p.527-548, July 1997
	Wolfgang Thomas, Uniform and nonuniform recognizability, Theoretical Computer Science, v.292 n.1, p.299-316, January 2003
	J. A. Makowsky, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Applied Mathematics, v.145 n.2, p.276-290, 15 January 2005
	Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Narayan Vikas, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Journal of Computer and System Sciences, v.71 n.4, p.406-439, November 2005
	Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Composing schema mappings: Second-order dependencies to the rescue, ACM Transactions on Database Systems (TODS), v.30 n.4, p.994-1055, December 2005
	Hubie Chen, A rendezvous of logic, complexity, and algebra, ACM SIGACT News, v.37 n.4, December 2006
	Nilesh Dalvi , Dan Suciu, The dichotomy of conjunctive queries on probabilistic structures, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Jean-Françs Baget , Marie-Laure Mugnier, Extensions of simple conceptual graphs: the complexity of rules and constraints, Journal of Artificial Intelligence Research, v.16 n.1, p.425-465, January 2002
	Phokion G. Kolaitis, Constraint satisfaction, databases, and logic, Proceedings of the 18th international joint conference on Artificial intelligence, p.1587-1595, August 09-15, 2003, Acapulco, Mexico