Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
1,072
result(s) for
"Computational complexity (Machine theory)"
Sort by:
Turing's legacy : developments from Turing's ideas in logic
\"Alan Turing was an inspirational figure who is now recognised as a genius of modern mathematics. In addition to leading the Allied forces' code-breaking effort at Bletchley Park in World War II, he proposed the theoretical foundations of modern computing and anticipated developments in areas from information theory to computer chess. His ideas have been extraordinarily influential in modern mathematics and this book traces such developments by bringing together essays by leading experts in logic, artificial intelligence, computability theory and related areas. Together, they give insight into this fascinating man, the development of modern logic, and the history of ideas. The articles within cover a diverse selection of topics, such as the development of formal proof, differing views on the Church-Turing thesis, the development of combinatorial group theory, and Turing's work on randomness which foresaw the ideas of algorithmic randomness that would emerge many years later\"-- Provided by publisher.
Book
The Golden Ticket
The P-NP problem is the most important open problem in computer science, if not all of mathematics.The Golden Ticketprovides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives.
The Golden Ticketexplores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of the P-NP problem.
eBook
Analysis of Experimental Data in Science and Technology
This textbook presents methods of data analysis and uncertainty estimation based on classical statistics whilst including the use of robust statistics, Monte Carlo modelling, informational criteria, and non-statistical methods. Related computer programs and their creative use are also discussed, without reference to specific packages. The book contains one hundred illustrations and numerous examples using real-world data, from a student lab to the latest scientific results. It will appeal to students, scientists, engineers, metrologists, and everyone interested in processing measurement results.
eBook
Logic, Automata, and Computational Complexity
Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for his advancement of our understanding of the complexity of computation in a significant and profound way. This volume includes a selection of seminal papers embodying the work that led to this award, exemplifying Cook's synthesis of ideas and techniques from logic and the theory of computation including NP-completeness, proof complexity, bounded arithmetic, and parallel and space-bounded computation. These papers are accompanied by contributed articles by leading researchers in these areas, which convey to a general reader the importance of Cook's ideas and their enduring impact on the research community. The book also contains biographical material, Cook's Turing Award lecture, and an interview. Together these provide a portrait of Cook as a recognized leader and innovator in mathematics and computer science, as well as a gentle mentor and colleague.
eBook
Local activity principle
The principle of local activity explains the emergence of complex patterns in a homogeneous medium. At first defined in the theory of nonlinear electronic circuits in a mathematically rigorous way, it can be generalized and proven at least for the class of nonlinear reaction. This book argues that the principle of local activity is really fundamental in science, and can even be identified in quantum cosmology as symmetry breaking of local gauge symmetries generating the complexity of matter and forces in our universe.
eBook
Measuring the complexity of directed graphs: A polynomial-based approach
In this paper, we define novel graph measures for directed networks. The measures are based on graph polynomials utilizing the out- and in-degrees of directed graphs. Based on these polynomial, we define another polynomial and use their positive zeros as graph measures. The measures have meaningful properties that we investigate based on analytical and numerical results. As the computational complexity to compute the measures is polynomial, our approach is efficient and can be applied to large networks. We emphasize that our approach clearly complements the literature in this field as, to the best of our knowledge, existing complexity measures for directed graphs have never been applied on a large scale.
Journal Article
Foundations of complex systems
Complexity is emerging as a post-Newtonian paradigm for approaching a large body of phenomena of concern at the crossroads of physical, engineering, environmental, life and human sciences from a unifying point of view.
eBook
Distributed Control of Robotic Networks
This self-contained introduction to the distributed control of robotic networks offers a distinctive blend of computer science and control theory. The book presents a broad set of tools for understanding coordination algorithms, determining their correctness, and assessing their complexity; and it analyzes various cooperative strategies for tasks such as consensus, rendezvous, connectivity maintenance, deployment, and boundary estimation. The unifying theme is a formal model for robotic networks that explicitly incorporates their communication, sensing, control, and processing capabilities--a model that in turn leads to a common formal language to describe and analyze coordination algorithms. Written for first- and second-year graduate students in control and robotics, the book will also be useful to researchers in control theory, robotics, distributed algorithms, and automata theory. The book provides explanations of the basic concepts and main results, as well as numerous examples and exercises. Self-contained exposition of graph-theoretic concepts, distributed algorithms, and complexity measures for processor networks with fixed interconnection topology and for robotic networks with position-dependent interconnection topology Detailed treatment of averaging and consensus algorithms interpreted as linear iterations on synchronous networks Introduction of geometric notions such as partitions, proximity graphs, and multicenter functions Detailed treatment of motion coordination algorithms for deployment, rendezvous, connectivity maintenance, and boundary estimation
eBook
Thermodynamics of complex systems
This text provides a concise introduction to non-equilibrium thermodynamics of open, complex systems using a first-principles approach. In the first chapters, the principles of thermodynamics of complex systems are discussed. The subsequent chapters apply the principles to the dynamics of chemical reactions and complex fluids, growth and development of biological organisms, and the dynamics of social structures and institutes. The final chapter discusses the principles of science as an artificial system.The book is a valuable reference text for researchers interested in thermodynamics and complex systems, and useful supplementary reading for graduate courses on advanced thermodynamics, thermodynamics of non-equilibrium systems and thermodynamics of complex/open systems.
eBook
Path-planning with waiting in spatiotemporally-varying threat fields
We address the problem of finding an optimal path for a vehicle in a planar environment where traversal costs are based on a time-varying spatial field defined over the environment. The resulting optimal path may contain instances of waiting, where the vehicle hovers, parks, or loiters. First, we consider path-planning on a uniform grid over the workspace. It is known that the computational complexity of the problem is significantly higher when waiting is allowed. We study the trade-off between the increased computational complexity and potential cost reductions in the resultant path with allowance for waiting. The results of numerical studies in this work identify characteristics of the threat fields in which optimal paths can involve waiting. Furthermore, we provide a local condition on the threat field that precludes waiting from providing any cost reductions in the resultant path. We show that this condition can be used in the path-planning algorithm to prune search trees and provide significant reductions in computation time without significant suboptimality. Next, we consider path-planning on a vehicle-centric multiresolution grid. We use a wavelet-based multiresolution decomposition to evaluate the multiresolution path planner and compare against the uniform resolution grid using the same family of threat fields. We show that with a vehicle-centric multiresolution map and an appropriate path-planning algorithm, the added computational effort of allowance for waiting is negligible.
Journal Article