Atjaunināt sīkdatņu piekrišanu

E-grāmata: Structural Complexity I

5.00/5 (1 ratings by Goodreads)
, ,
Citas grāmatas par šo tēmu:
  • Formāts - PDF+DRM
  • Cena: 53,52 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Ielikt grozā
  • Pievienot vēlmju sarakstam
  • Šī e-grāmata paredzēta tikai personīgai lietošanai. E-grāmatas nav iespējams atgriezt un nauda par iegādātajām e-grāmatām netiek atmaksāta.
Structural Complexity IPalielināt
Citas grāmatas par šo tēmu:

DRM restrictions

  • Kopēšana (kopēt/ievietot):

    nav atļauts

  • Drukāšana:

    nav atļauts

  • Lietošana:

    Digitālo tiesību pārvaldība (Digital Rights Management (DRM))
    Izdevējs ir piegādājis šo grāmatu šifrētā veidā, kas nozīmē, ka jums ir jāinstalē bezmaksas programmatūra, lai to atbloķētu un lasītu. Lai lasītu šo e-grāmatu, jums ir jāizveido Adobe ID. Vairāk informācijas šeit. E-grāmatu var lasīt un lejupielādēt līdz 6 ierīcēm (vienam lietotājam ar vienu un to pašu Adobe ID).

    Nepieciešamā programmatūra
    Lai lasītu šo e-grāmatu mobilajā ierīcē (tālrunī vai planšetdatorā), jums būs jāinstalē šī bezmaksas lietotne: PocketBook Reader (iOS / Android)

    Lai lejupielādētu un lasītu šo e-grāmatu datorā vai Mac datorā, jums ir nepieciešamid Adobe Digital Editions (šī ir bezmaksas lietotne, kas īpaši izstrādāta e-grāmatām. Tā nav tas pats, kas Adobe Reader, kas, iespējams, jau ir jūsu datorā.)

    Jūs nevarat lasīt šo e-grāmatu, izmantojot Amazon Kindle.

In the six years since the first edition of this book was published, the field of Structural Complexity has grown quite a bit. However, we are keeping this volume at the same basic level that it had in the first edition, and the only new result incorporated as an appendix is the closure under complementation of nondeterministic space classes, which in the previous edition was posed as an open problem. This result was already included in our Volume II, but we feel that due to the basic nature of the result, it belongs to this volume. There are of course other important results obtained during these last six years. However, as they belong to new areas opened in the field they are outside the scope of this fundamental volume. Other changes in this second edition are the update of some Bibliograph­ ical Remarks and references, correction of many mistakes and typos, and a renumbering of the definitions and results. Experience has shown us that this new numbering is a lot more friendly, and several readers have confirmed this opinion. For the sake of the reader of Volume II, where all references to Volume I follow the old numbering, we have included here a table indicating the new number corresponding to each of the old ones.

Papildus informācija

Springer Book Archives
1 Introduction.- 2 Basic Notions About Models of Computation.- 1.1
Introduction.- 1.2 Alphabets, Words, Sets, and Classes.- 1.3 Inclusion Modulo
Finite Variants.- 1.4 Boolean Formulas.- 1.5 Models of Computation: Finite
Automata.- 1.6 Models of Computation: Taring Machines.- 1.7 Models of
Computation: Nondeterministic Turing Machines.- 1.8 Models of Computation:
Oracle Turing Machines.- 1.9 Bibliographical Remarks.- 3 Time and Space
Bounded Computations.- 2.1 Introduction.- 2.2 Orders of Magnitude.- 2.3
Running Time and Work Space of Turing Machines.- 2.4 Time and Space
Constructibility.- 2.5 Bounding Resources: Basic Definitions and
Relationships.- 2.6 Bibliographical Remarks.- 4 Central Complexity Classes.-
3.1 Introduction.- 3.2 Definitions, Properties, and Examples.- 3.3 Computing
Functions: Invertibility and Honesty.- 3.4 Polynomial Time Many-one
Reducibility.- 3.5 Natural NP-complete Sets.- 3.6 Natural PSPACE-complete
Sets.- 3.7 Padding Arguments.- 3.8 Space Bounded Reducibility.- 3.9
Exercises.- 3.10 Bibliographical Remarks.- 5 Time Bounded Turing
Reducibilities.- 4.1 Introduction.- 4.2 Polynomial Time Turing Reducibility:
Relativized Classes.- 4.3 Tally and Sparse Sets in NP.- 4.4 Strong
Nondeterministic Polynomial Time Reducibility.- 4.5 Self-Reducibility.- 4.6
Exercises.- 4.7 Bibliographical Remarks.- 6 Nonuniform Complexity.- 5.1
Introduction.- 5.2 Classes Defined by Advice Functions.- 5.3 Boolean Circuit
Complexity.- 5.4 Turing Machines and Boolean Circuits.- 5.5 Polynomial
Advice.- 5.6 Logarithmic Advice.- 5.7 Self-Producible Circuits.- 5.8 A Lower
Bound to the Circuit Size of Boolean Functions.- 5.9 Other Nonuniform
Complexity Measures.- 5.10 Exercises.- 5.11 Bibliographical Remarks.- 7
Probabilistic Algorithms.- 6.1 Introduction.- 6.2 TheProbabilistic
Computational Model.- 6.3 Polynomial Time Probabilistic Classes.- 6.4 Bounded
Error Probability.- 6.5 Nonuniform Properties of BPP.- 6.6 Zero Error
Probability.- 6.7 Exercises.- 6.8 Bibliographical Remarks.- 8 Uniform
Diagonalization.- 7.1 Introduction.- 7.2 Presentability and Other
Properties.- 7.3 The Main Theorem.- 7.4 Applications.- 7.5 Exercises.- 7.6
Bibliographical Remarks.- 9 The Polynomial Time Hierarchy.- 8.1
Introduction.- 8.2 Definition and Properties.- 8.3 Characterization and
Consequences.- 8.4 Complete Sets and Presentability.- 8.5 BPP and the
Polynomial Time Hierarchy.- 8.6 Exercises.- 8.7 Bibliographical Remarks.-
References.- Appendix Complementation via Inductive Counting.- Author Index.-
Symbol Index.
Biežāk uzdotie jautājumi par e-grāmatām Biežāk uzdotie jautājumi par e-grāmatām
Permanent link: https://www.kriso.lv/db/97836427923592e.html
Keywords: