Tropical Circuit Complexity: Limits of Pure Dynamic Programming

· Springer Nature
电子书
129

关于此电子书

This book presents an enticing introduction to tropical circuits and their use as a rigorous mathematical model for dynamic programming (DP), which is one of the most fundamental algorithmic paradigms for solving combinatorial, discrete optimization problems.
In DP, an optimization problem is broken up into smaller subproblems that are solved recursively. Many classical DP algorithms are pure in that they only use the basic (min,+) or (max,+) operations in their recursion equations. In tropical circuits, these operations are used as gates. Thanks to the rigorous combinatorial nature of tropical circuits, elements from the Boolean and arithmetic circuit complexity can be used to obtain lower bounds for tropical circuits, which play a crucial role in understanding the limitations and capabilities of these computational models. This book aims to offer a toolbox for proving lower bounds on the size of tropical circuits.
In this work, the reader will find lower-bound ideas and methods that have emerged in the last few years, with detailed proofs. Largely self-contained, this book is meant to be approachable by graduate students in mathematics and computer science with a special interest in circuit complexity.

作者简介

Stasys Jukna is an Affiliated Researcher at Vilnius University, Lithuania. His research interests lie between mathematics and theoretical computer sciences, with a focus on proving lower bounds on circuit complexity. Dr. Jukna has authored numerous books, including "Extremal Combinatorics" and "Boolean Function Complexity," published by Springer.

为此电子书评分

欢迎向我们提供反馈意见。

如何阅读

智能手机和平板电脑
只要安装 AndroidiPad/iPhone 版的 Google Play 图书应用,不仅应用内容会自动与您的账号同步,还能让您随时随地在线或离线阅览图书。
笔记本电脑和台式机
您可以使用计算机的网络浏览器聆听您在 Google Play 购买的有声读物。
电子阅读器和其他设备
如果要在 Kobo 电子阅读器等电子墨水屏设备上阅读,您需要下载一个文件,并将其传输到相应设备上。若要将文件传输到受支持的电子阅读器上,请按帮助中心内的详细说明操作。