Complexity Theory Basics: NP and NL

DOI10.1007/978-3-319-05446-9_1zbMath1345.68143OpenAlexW92597067MaRDI QIDQ2821692

V. Arvind

Publication date: 22 September 2016

Published in: Perspectives in Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-05446-9_1

zbMATH Keywords

NP-completenessnondeterministic logarithmic spacenondeterministic polynomial time

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• The complexity of computing the permanent
• Some consequences of non-uniform conditions on uniform classes
• The method of forced enumeration for nondeterministic automata
• Which problems have strongly exponential complexity?
• Nondeterministic Space is Closed under Complementation
• Structure and importance of logspace-MOD class
• Making Nondeterminism Unambiguous
• On the Computational Complexity of Algorithms
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs

This page was built for publication: Complexity Theory Basics: NP and NL