No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth

被引：4
|
作者：
Razgon, Igor [1 ]
机构：
[1] Univ London, Dept Comp Sci & Informat Syst, London, England
来源：
PARAMETERIZED AND EXACT COMPUTATION, IPEC 2014 | 2014年 / 8894卷
关键词：
D O I：
10.1007/978-3-319-13524-3_27
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, given a parameter k, we demonstrate an infinite class of CNFS of treewidth at most k of their primal graphs such that equivalent nondeterministic read-once branching programs (NROBPS) are of size at least n(ck) for some universal constant c. Thus we rule out the possibility of fixed-parameter tractable space complexity of NROBPS parameterized by the smallest treewidth of equivalent CNFS.
引用
收藏
页码：319 / 331
页数：13
相关论文
共 50 条
  • [31] On the complexity of integer multiplication in branching programs with multiple tests and in Read-Once Branching Programs with limited nondeterminism
    Woelfel, P
    17TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2002, : 80 - 89
  • [32] Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
    Razborov, A
    Wigderson, A
    Yao, A
    COMBINATORICA, 2002, 22 (04) : 555 - 574
  • [33] Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs
    Gurjar, Rohit
    Korwar, Arpita
    Saxena, Nitin
    Thierauf, Thomas
    30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 : 323 - 346
  • [34] Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
    Gurjar, Rohit
    Korwar, Arpita
    Saxena, Nitin
    Thierauf, Thomas
    COMPUTATIONAL COMPLEXITY, 2017, 26 (04) : 835 - 880
  • [35] Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
    Rohit Gurjar
    Arpita Korwar
    Nitin Saxena
    Thomas Thierauf
    computational complexity, 2017, 26 : 835 - 880
  • [36] Functions that have read-once branching programs of quadratic size are not necessarily testable
    Bollig, B
    Wegener, I
    INFORMATION PROCESSING LETTERS, 2003, 87 (01) : 25 - 29
  • [37] Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
    Alexander Razborov*
    Avi Wigderson†
    Andrew Yao‡
    Combinatorica, 2002, 22 : 555 - 574
  • [38] Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order
    Forbes, Michael A.
    Saptharishi, Ramprasad
    Shpilka, Amir
    STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 867 - 875
  • [39] A lower bound for integer multiplication on randomized ordered read-once branching programs
    Ablayev, F
    Karpinski, M
    INFORMATION AND COMPUTATION, 2003, 186 (01) : 78 - 89
  • [40] A very simple function that requires exponential size read-once branching programs
    Bollig, B
    Wegener, I
    INFORMATION PROCESSING LETTERS, 1998, 66 (02) : 53 - 57
12345