國立虎尾科技大學 |

Tropical circuit complexity = limits of pure dynamic programming /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Tropical circuit complexity/ by Stasys Jukna.
Reminder of title:	limits of pure dynamic programming /
Author:	Jukna, Stasys.
Published:	Cham :Springer International Publishing : : 2023.,
Description:	ix, 129 p. :ill., digital ; : 24 cm.;
Contained By:	Springer Nature eBook
Subject:	Dynamic programming. -
Online resource:	https://doi.org/10.1007/978-3-031-42354-3
ISBN:	9783031423543

Tropical circuit complexity = limits of pure dynamic programming /
Jukna, Stasys.

Tropical circuit complexitylimits of pure dynamic programming /[electronic resource] :by Stasys Jukna. - Cham :Springer International Publishing :2023. - ix, 129 p. :ill., digital ;24 cm. - SpringerBriefs in mathematics,2191-8201. - SpringerBriefs in mathematics..

Chapter. 1. Basics -- Chapter. 2. Combinatorial Bounds -- Chapter. 3. Rectangle Bounds -- Chapter. 4. Bounds for Approximating Circuits -- Chapter. 5. Tropical Branching Programs -- Chapter. 6. Extended Tropical Circuits.

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.

ISBN: 9783031423543

Standard No.: 10.1007/978-3-031-42354-3doiSubjects--Topical Terms:

528343
Dynamic programming.

LC Class. No.: T57.83

Dewey Class. No.: 519.703

Tropical circuit complexity = limits of pure dynamic programming /
LDR:02480nam a2200337 a 4500 001 1117843
003 DE-He213
005 20231106213708.0
006 m d
007 cr nn 008maaau
008 240126s2023 sz s 0 eng d
020 $a 9783031423543 $q (electronic bk.)
020 $a 9783031423536 $q (paper)
024 7 $a 10.1007/978-3-031-42354-3 $2 doi
035 $a 978-3-031-42354-3
040 $a GP $c GP
041 0 $a eng
050 4 $a T57.83
072 7 $a PBD $2 bicssc
072 7 $a MAT008000 $2 bisacsh
072 7 $a PBD $2 thema
082 0 4 $a 519.703 $2 23
090 $a T57.83 $b .J93 2023
100 1 $a Jukna, Stasys. $3 796141
245 1 0 $a Tropical circuit complexity $h [electronic resource] : $b limits of pure dynamic programming / $c by Stasys Jukna.
260 $a Cham : $c 2023. $b Springer International Publishing : $b Imprint: Springer,
300 $a ix, 129 p. : $b ill., digital ; $c 24 cm.
490 1 $a SpringerBriefs in mathematics, $x 2191-8201
505 0 $a Chapter. 1. Basics -- Chapter. 2. Combinatorial Bounds -- Chapter. 3. Rectangle Bounds -- Chapter. 4. Bounds for Approximating Circuits -- Chapter. 5. Tropical Branching Programs -- Chapter. 6. Extended Tropical Circuits.
520 $a 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.
650 0 $a Dynamic programming. $3 528343
650 0 $a Logic circuits. $3 598467
650 1 4 $a Discrete Mathematics. $3 796600
650 2 4 $a Computational Complexity. $3 1366362
650 2 4 $a Discrete Optimization. $3 1019327
650 2 4 $a Mathematical Applications in Computer Science. $3 815331
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer Nature eBook
830 0 $a SpringerBriefs in mathematics. $3 883715
856 4 0 $u https://doi.org/10.1007/978-3-031-42354-3
950 $a Mathematics and Statistics (SpringerNature-11649)