Language:
English
繁體中文
Help
回圖書館首頁
手機版館藏查詢
Login
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 complexity
limits 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)
based on 0 review(s)
Location:
ALL
電子資源
Year:
Volume Number:
Items
1 records • Pages 1 •
1
Inventory Number
Location Name
Item Class
Material type
Call number
Usage Class
Loan Status
No. of reservations
Opac note
Attachments
W9461820
電子資源
11.線上閱覽_V
電子書
EB T57.83
一般使用(Normal)
On shelf
0
1 records • Pages 1 •
1
Multimedia
Reviews
Add a review
and share your thoughts with other readers
Export
pickup library
Processing
...
Change password
Login