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

被引：0
|
作者：
Achlioptas, D [1 ]
Chtcherba, A [1 ]
Istrate, G [1 ]
Moore, C [1 ]
机构：
[1] Microsoft Res, Redmond, WA 98052 USA
来源：
PROCEEDINGS OF THE TWELFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2001年
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：721 / 722
页数：2
相关论文
共 50 条
  • [21] Quantum 3-SAT is QMA1-complete
    Gosset, David
    Nagaj, Daniel
    2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 756 - 765
  • [22] An evolutionary framework for 3-SAT problems
    Borgulya, I
    ITI 2003: PROCEEDINGS OF THE 25TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2003, : 471 - 476
  • [23] Derandomizing the HSSW Algorithm for 3-SAT
    Makino, Kazuhisa
    Tamaki, Suguru
    Yamamoto, Masaki
    ALGORITHMICA, 2013, 67 (02) : 112 - 124
  • [24] Random 3-SAT: The plot thickens
    Coarfa, C
    Demopoulos, DD
    Aguirre, AS
    Subramanian, D
    Vardi, MY
    CONSTRAINTS, 2003, 8 (03) : 243 - 261
  • [25] Observed lower bounds for random 3-SAT phase transition density using linear programming
    Heule, M
    van Maaren, H
    THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, PROCEEDINGS, 2005, 3569 : 122 - 134
  • [26] The SAT phase transition
    Ke Xu
    Wei Li
    Science in China Series E: Technological Sciences, 1999, 42 : 494 - 501
  • [27] The SAT phase transition
    Xu, K
    Li, W
    SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES, 1999, 42 (05): : 494 - 501
  • [28] The SAT phase transition
    许可
    李未
    Science in China(Series E:Technological Sciences), 1999, (05) : 494 - 501
  • [29] Heuristics for Quantum Computing Dealing with 3-SAT
    Paulet, Jose J.
    LLana, Luis F.
    Calvo, Hernan Indibil
    Mezzini, Mauro
    Cuartero, Fernando
    Pelayo, Fernando L.
    MATHEMATICS, 2023, 11 (08)
  • [30] Improving WalkSAT for Random 3-SAT Problems
    Fu, Huimin
    Xu, Yang
    Chen, Shuwei
    Liu, Jun
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2020, 26 (02) : 220 - 243
12345