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 条
  • [41] New upper bound for the #3-SAT problem
    Kutzkov, Konstantin
    INFORMATION PROCESSING LETTERS, 2007, 105 (01) : 1 - 5
  • [42] HyperSAT a new generator for 3-SAT instances
    Segura-Salazar, J
    Torres-Jiménez, J
    ICCIMA 2001: FOURTH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND MULTIMEDIA APPLICATIONS, PROCEEDINGS, 2001, : 323 - 327
  • [43] Quantum cooperative search algorithm for 3-SAT
    Cheng, Sheng-Tzong
    Tao, Ming-Hung
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2007, 73 (01) : 123 - 136
  • [44] EXPLORATION OF HARD TO SOLVE 3-SAT PROBLEMS
    Amador, Robert
    Chiang, Chen-Fu
    Hsieh, Chang-Yu
    INFORMATION TECHNOLOGY IN INDUSTRY, 2019, 7 (02): : 23 - 32
  • [45] 3-SAT FASTER AND SIMPLER-UNIQUE-SAT BOUNDS FOR PPSZ HOLD IN GENERAL
    Hertli, Timon
    SIAM JOURNAL ON COMPUTING, 2014, 43 (02) : 718 - 729
  • [46] Planar 3-SAT with a Clause/Variable Cycle
    Pilz, Alexander
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2019, 21 (03):
  • [47] An investigation of variable relationships in 3-SAT problems
    Kravchuk, O
    Pullan, W
    Thornton, J
    Sattar, A
    AL 2002: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2002, 2557 : 579 - 590
  • [48] PPSZ for General k-SAT and CSP-Making Hertli's Analysis Simpler and 3-SAT Faster
    Scheder, Dominik
    Steinberger, John
    COMPUTATIONAL COMPLEXITY, 2024, 33 (02)
  • [49] 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
    Hertli, Timon
    2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 277 - 284
  • [50] Computational complexity of some restricted instances of 3-SAT
    Berman, Piotr
    Karpinski, Marek
    Scott, Alexander D.
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (05) : 649 - 653
12345