Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
| Autor: | Nathan Grosshans, Pierre McKenzie, Luc Segoufin, Paul Beame |
|---|---|
| Přispěvatelé: | University of Washington [Seattle], École normale supérieure - Cachan (ENS Cachan), Université de Montréal (UdeM), Verification in databases (DAHU), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), NSF grants CCF-1217099 and CCF-1524246., Grants from Digiteo France., NSERC of Canada., 'Chaire DIGITEO, ENS Cachan - École Polytechnique'. |
| Rok vydání: | 2016 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Discrete mathematics Branching programs Sublinear function Computation 1. No poverty binary formulas 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds Theoretical Computer Science Nondeterministic algorithm Computer Science - Computational Complexity Computational Theory and Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.5: Unbounded-action devices (e.g. cellular automata circuits networks of machines) limited nondeterminism 020201 artificial intelligence & image processing Parity (mathematics) Mathematics |
| Zdroj: | ACM Transactions on Computation Theory ACM Transactions on Computation Theory, ACM, 2016, 9 (1), pp.1-34. ⟨10.1145/3013516⟩ ACM Transactions on Computation Theory, 2016, 9 (1), pp.1-34. ⟨10.1145/3013516⟩ |
| ISSN: | 1942-3462 1942-3454 |
| DOI: | 10.1145/3013516 |
| Popis: | A formulation of Nečiporuk’s lower bound method slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method are obtained for several computation models, such as branching programs and Boolean formulas having access to a sublinear number of nondeterministic bits. In particular, it is shown that any lower bound achievable by the method of Nečiporuk for the size of nondeterministic and parity branching programs is at most O ( n 3/2 /log n ). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|