The phase transition in 1-in-k SAT and NAE 3-SAT

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The phase transition in 1-in-k SAT and NAE 3-SAT

Full text

Pdf (139 KB)

Source

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

Washington, D.C., United States

Pages: 721 - 722

Year of Publication: 2001

ISBN:0-89871-490-7

Authors

Dimitris Achlioptas	Microsoft Research, Redmond, WA
Arthur Chtcherba	Computer Science Department, University of New Mexico, Albuquerque, NM
Gabriel Istrate	Center for Nonlinear Sciences, Los Alamos National Laboratory, MS B258, Los Alamos, NM
Cristopher Moore	Computer Science Department and Department of Physics and Astronomy, University of New Mexico, Albuquerque, NM and The Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM

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): 3, Downloads (12 Months): 21, Citation Count: 7

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.

	1	Dimitris Achlioptas, Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.28-37, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335309]
	2	B. Bollobas et al., "The scaling window of the 2-SAT transition" Microsoft Research TR-99-41.
	3	Olivier Dubois , Yacine Boufkhad , Jacques Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 09-11, 2000, San Francisco, California, United States
	4	Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Yannis C. Stamatiou, Approximating the unsatisfiability threshold of random formulas, Random Structures & Algorithms, v.12 n.3, p.253-269, May 1998 [doi>10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U]
	5	R. Monasson et al. "Determining computational complexity from characteristic phase transitions", Nature 400 (1999) 133-137.
	6	Rémi Monasson , Riccardo Zecchina , Scott Kirkpatrick , Bart Selman , Lidror Troyansky, 2+p-SAT: relation of typical-case complexity to the nature of the phase transition, Random Structures & Algorithms, v.15 n.3-4, p.414-435, Oct.-Dec. 1999 [doi>10.1002/(SICI)1098-2418(199910/12)15:3/4<414::AID-RSA10>3.0.CO;2-G]

CITED BY 7

	Dimitris Achlioptas , Paul Beame , Michael Molloy, A sharp threshold in proof complexity, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.337-346, July 2001, Hersonissos, Greece
	Nadia Creignou , Hervé Daudé, Generalized satisfiability problems: minimal elements and phase transitions, Theoretical Computer Science, v.302 n.1-3, p.417-430, 13 June 2003
	Toby Walsh, The interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT, Eighteenth national conference on Artificial intelligence, p.695-700, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Adam Beacham , Joseph Culberson, On the complexity of unfrozen problems, Discrete Applied Mathematics, v.153 n.1, p.3-24, 1 December 2005
	Gabriel Istrate , Stefan Boettcher , Allon G. Percus, Spines of random constraint satisfaction problems: definition and connection with computational complexity, Annals of Mathematics and Artificial Intelligence, v.44 n.4, p.353-372, August 2005
	Cristopher Moore , Gabriel Istrate , Demetrios Demopoulos , Moshe Y. Vardi, A continuous–discontinuous second-order transition in the satisfiability of random Horn-SAT formulas, Random Structures & Algorithms, v.31 n.2, p.173-185, September 2007
	Andreas Goerdt , Tomasz Jurdziński, Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures, Combinatorics, Probability and Computing, v.12 n.3, p.245-267, May 2003