東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Tropical circuit complexity = limits...

Jukna, Stasys.

Linked to FindBook

Google Book

Amazon

博客來

Tropical circuit complexity = limits of pure dynamic programming /

Record Type:	Electronic resources : 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.
[NT 15003449]:	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.
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:

641303
Dynamic programming.

LC Class. No.: T57.83

Dewey Class. No.: 519.703

Tropical circuit complexity = limits of pure dynamic programming /
LDR:02480nmm a2200337 a 4500 001 2335615
003 DE-He213
005 20231106213708.0
006 m d
007 cr nn 008maaau
008 240402s2023 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 3668163
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 641303
650 0 $a Logic circuits. $3 527270
650 1 4 $a Discrete Mathematics. $3 1569938
650 2 4 $a Computational Complexity. $3 3538876
650 2 4 $a Discrete Optimization. $3 2054320
650 2 4 $a Mathematical Applications in Computer Science. $3 1567978
710 2 $a SpringerLink (Online service) $3 836513
773 0 $t Springer Nature eBook
830 0 $a SpringerBriefs in mathematics. $3 1566700
856 4 0 $u https://doi.org/10.1007/978-3-031-42354-3
950 $a Mathematics and Statistics (SpringerNature-11649)