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 条
  • [1] The interface between P and NP: COL, XOR, NAE, 1-in-k, and horn SAT
    Walsh, T
    EIGHTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-02)/FOURTEENTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE (IAAI-02), PROCEEDINGS, 2002, : 695 - 700
  • [2] On the Empirical Time Complexity of Random 3-SAT at the Phase Transition
    Mu, Zongxu
    Hoos, Holger H.
    PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 367 - 373
  • [3] On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition
    Blaesius, Thomas
    Friedrich, Tobias
    Sutton, Andrew M.
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, PT I, 2019, 11427 : 117 - 134
  • [4] Geometric properties of satisfying assignments of random ε-1-in-k SAT
    Istrate, Gabriel
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2009, 86 (12) : 2029 - 2039
  • [5] The complexity of making unique choices:: Approximating 1-in-k SAT
    Guruswami, V
    Trevisan, L
    APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2005, 3624 : 99 - 110
  • [6] THE NUMBER OF 3-SAT FUNCTIONS
    Ilinca, L.
    Kahn, J.
    ISRAEL JOURNAL OF MATHEMATICS, 2012, 192 (02) : 869 - 919
  • [7] The number of 3-SAT functions
    L. Ilinca
    J. Kahn
    Israel Journal of Mathematics, 2012, 192 : 869 - 919
  • [8] Randomized Algorithms for 3-SAT
    Thomas Hofmeister
    Uwe Schoning
    Rainer Schuler
    Osamu Watanabe
    Theory of Computing Systems, 2007, 40 : 249 - 262
  • [9] A randomized algorithm for 3-SAT
    Ghosh S.K.
    Misra J.
    Mathematics in Computer Science, 2010, 3 (4) : 421 - 431
  • [10] Randomized algorithms for 3-SAT
    Hofmeister, Thomas
    Schoening, Uwe
    Schuler, Rainer
    Watanabe, Osamu
    THEORY OF COMPUTING SYSTEMS, 2007, 40 (03) : 249 - 262
12345