國立高雄大學圖資館 |

登入

回首頁 到查詢結果 [ subject:"Computational Complexity." ]

Tropical circuit complexitylimits of pure dynamic programming /

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Tropical circuit complexityby Stasys Jukna.
其他題名:	limits of pure dynamic programming /
作者:	Jukna, Stasys.
出版者:	Cham :Springer International Publishing :2023.
面頁冊數:	ix, 129 p. :ill., digital ;24 cm.
Contained By:	Springer Nature eBook
標題:	Dynamic programming.
電子資源:	https://doi.org/10.1007/978-3-031-42354-3
ISBN:	9783031423543$q(electronic bk.)

Tropical circuit complexitylimits 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$q(electronic bk.)

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

181912
Dynamic programming.

LC Class. No.: T57.83

Dewey Class. No.: 519.703

Tropical circuit complexitylimits of pure dynamic programming /
LDR:02480nmm a2200337 a 4500 001 652278
003 DE-He213
005 20231106213708.0
006 m d
007 cr nn 008maaau
008 240327s2023 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 524353
245 1 0 $a Tropical circuit complexity $h [electronic resource] : $b limits of pure dynamic programming / $c by Stasys Jukna.
260 $a Cham : $b Springer International Publishing : $b Imprint: Springer, $c 2023.
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 181912
650 0 $a Logic circuits. $3 182233
650 1 4 $a Discrete Mathematics. $3 524738
650 2 4 $a Computational Complexity. $3 913441
650 2 4 $a Discrete Optimization. $3 674481
650 2 4 $a Mathematical Applications in Computer Science. $3 530811
710 2 $a SpringerLink (Online service) $3 273601
773 0 $t Springer Nature eBook
830 0 $a SpringerBriefs in mathematics. $3 558795
856 4 0 $u https://doi.org/10.1007/978-3-031-42354-3
950 $a Mathematics and Statistics (SpringerNature-11649)