Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method

DOI10.1145/3013516zbMath1427.68103arXiv1608.01932OpenAlexW3103022282MaRDI QIDQ4973868

Luc Segoufin, Pierre McKenzie, Nathan Grosshans, P. W. Beame

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

branching programslimited nondeterminismbinary formulas

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Unnamed Item

This page was built for publication: Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method