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 条

[21] Perspective on complexity measures targeting read-once branching programs
Li, Yaqiao
McKenzie, Pierre
INFORMATION AND COMPUTATION, 2024, 301
[22] Randomness versus nondeterminism for read-once and read-k branching programs
Sauerhoff, M
STACS 2003, PROCEEDINGS, 2003, 2607 : 307 - 318
[23] Randomization and nondeterminism are comparable for ordered read-once branching programs
Ablayev, F
AUTOMATA, LANGUAGES AND PROGRAMMING, 1997, 1256 : 195 - 202
[24] A lower bound for integer multiplication with read-once branching programs
Ponzio, S
SIAM JOURNAL ON COMPUTING, 1998, 28 (03) : 798 - 815
[25] A read-once lower bound and a (1,+k)-hierarchy for branching programs
Savicky, P
Zák, S
THEORETICAL COMPUTER SCIENCE, 2000, 238 (1-2) : 347 - 362
[26] A hierarchy result for read-once branching programs with restricted parity nondeterminism
Savicky, P
Sieling, D
THEORETICAL COMPUTER SCIENCE, 2005, 340 (03) : 594 - 605
[27] Linear codes are hard for oblivious read-once parity branching programs
Jukna, S
INFORMATION PROCESSING LETTERS, 1999, 69 (06) : 267 - 269
[28] On BPP versus NP ∨ coNP for ordered read-once branching programs
Ablayev, F
Karpinski, M
Mubarakzjanov, R
THEORETICAL COMPUTER SCIENCE, 2001, 264 (01) : 127 - 137
[29] Linear codes are hard for oblivious read-once parity branching programs
Department of Computer Science, University of Trier, D-54286 Trier, Germany
不详
Inf. Process. Lett., 6 (267-269):
[30] A simple function that requires exponential size read-once branching programs
Gal, A
INFORMATION PROCESSING LETTERS, 1997, 62 (01) : 13 - 16

← 1 2 3 4 5 →