scientific article; zbMATH DE number 6395196

DOI10.4086/toc.2014.v010a012zbMath1319.68094arXiv1108.2385OpenAlexW2099856971MaRDI QIDQ5497123

Periklis A. Papakonstantinou, Bang-Sheng Tang, Shiteng Chen, Tiancheng Lou, Eric W. Allender

Publication date: 3 February 2015

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.2385

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algorithmscompletenesstreewidthpathwidthcircuit complexitytime-space tradeoffnondeterminismcomplexity theorycomplexity classesparametrized complexityBoolean formulasCNF-DNF formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

On the Satisfiability of Quantum Circuits of Small Treewidth ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ Satisfiability, branch-width and Tseitin tautologies ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ On treewidth, separators and Yao's garbling ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

Cites Work

• The relative efficiency of propositional proof systems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• A full derandomization of schöning's k-SAT algorithm
• Unnamed Item

This page was built for publication: