Complexity theory basics: NP and NL

DOI10.1007/978-3-319-05446-9_1MaRDI QIDQ2821692zbMATH OpenOpenAlexFDO

Authors Vikraman 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

nondeterministic logarithmic spacenondeterministic polynomial timeNP-completeness

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 218387
• An overview of computational complexity
• scientific article; zbMATH DE number 1072533
• P, NP, and NP-completeness. The basics of computational complexity.
• scientific article; zbMATH DE number 610968

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 1072533 (Why is no real title available?)
• scientific article; zbMATH DE number 2040898 (Why is no real title available?)
• Computational complexity on the blackboard
• scientific article; zbMATH DE number 2150283 (Why is no real title available?)
• scientific article; zbMATH DE number 218387 (Why is no real title available?)

This page was built for publication: Complexity theory basics: NP and NL

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821692)