The phase transition in random Horn satisfiability and its algorithmic implications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The phase transition in random Horn satisfiability and its algorithmic implications

Full text

Pdf (202 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 925 - 926

Year of Publication: 1999

ISBN:0-89871-434-6

Author

Gabriel Istrate

Department of Computer Science, University of Rochester, Rochester, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 11, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

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

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.

	BT86	B. Bollobás , A. Thomason, Threshold functions, Combinatorica, v.7 n.1, p.35-38, Jan. 1987 [doi>10.1007/BF02579198]
	CD96	N. Creignou and H. Daud#. Satistiability threshold for random XOR-CNF formulae. Technical Report 96- 20, IML/UPR 9016, 1996.
	CKT91	P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proceedings of the 11 'th IJCAI, pages 331-337, 1991.
	CR92	V. Chv#tal and B. Reed. Mick gets some (the odds are on his side). In Proceedings of the 3#nd IEEE Symposium on Foundations of Computer Science, pages 620-626, 1992.
	ER60	P. ErdSs and A. Rdnyi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Science, 5:17-61, 1960.
	Goe96	Andreas Goerdt, A threshold for unsatisfiability, Journal of Computer and System Sciences, v.53 n.3, p.469-486, Dec. 1996 [doi>10.1006/jcss.1996.0081]
	IO98	G. Istrate and M. Ogihara. The phase transition in random Horn satis#bility. In Fifth International Syrnp. on AI and Ma#hematias, Fort Lauderdale, 1998. http://rutcor.rutgers.edu/- amai.
	Ist	G. Istrate. Critical behavior in the satisf#bility of random k-Horn formulae. (submitted to STOC'99).
	KS94	S. Kirkpatrick and B. Selman. Critical behavior in the satisfiability of random boolean expressions. Science, 264:1297-1301, 1994.
	Sch78	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]