Computability and complexity theory.

DOI10.1007/978-1-4614-0682-2MaRDI QIDQ640476zbMATH OpenOpenAlexFDO

Authors S. Homer, Alan L. Selman

Publication date 18 October 2011

Published in Texts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4614-0682-2

zbMATH Keywords

computational complexitydecidabilitycounting complexityTuring machinerandomnesscomputabilityinteractive proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of computing (68Q01)

Recommendations

• Computability and complexity theory
• scientific article; zbMATH DE number 3909745
• Elements of computation theory
• Basic course theoretical computer science with exercises and test questions.
• scientific article; zbMATH DE number 3965406
• scientific article; zbMATH DE number 738396
• scientific article; zbMATH DE number 578252
• scientific article; zbMATH DE number 225477
• scientific article; zbMATH DE number 1033441
• Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.

Cited in

(30)

• scientific article; zbMATH DE number 2161249 (Why is no real title available?)
• Computer science. The hardware, software and heart of it
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• scientific article; zbMATH DE number 826291 (Why is no real title available?)
• Splitting NP-complete sets infinitely
• Computational Complexity
• Schema mapping coverage
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Further results on an abstract model for branching and its application to mixed integer programming
• scientific article; zbMATH DE number 2167361 (Why is no real title available?)
• scientific article; zbMATH DE number 47306 (Why is no real title available?)
• A note on the complexity of \textbf{S4.2}
• Algorithmic complexity
• The complexity of the \(K\)th largest subset problem and related problems
• Analyzing fractional Horn constraint systems
• Theory of semi-feasible algorithms
• The nature of computation
• Effective guessing has unlikely consequences
• On the termination and structural termination problems for counter machines with incrementing errors
• A theory of complexity, condition, and roundoff
• scientific article; zbMATH DE number 1220163 (Why is no real title available?)
• Theory of computation.
• Computational Complexity
• Limits of computation. An introduction to the undecidable and the intractable
• scientific article; zbMATH DE number 1453451 (Why is no real title available?)
• \textsc{Hanano} puzzle is \textsf{NP}-hard
• scientific article; zbMATH DE number 738396 (Why is no real title available?)
• Machines that perform measurements
• Computability and complexity theory
• Assortment optimization: a systematic literature review

This page was built for publication: Computability and complexity theory.

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