Hardness of Approximation Between P and NP - Aviad Rubinstein ACM Books

Скачать книгу

      Copyright © 2019 by Association for Computing Machinery and Morgan & Claypool Publishers

      All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews—without the prior permission of the publisher.

      Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which the Association for Computing Machinery is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.

       Hardness of Approximation Between P and NP

      Aviad Rubinstein

       books.acm.org

       http://books.acm.org

      ISBN: 978-1-94748-723-9 hardcover

      ISBN: 978-1-94748-720-8 paperback

      ISBN: 978-1-94748-722-2 ePub

      ISBN: 978-1-94748-721-5 eBook

      Series ISSN: 2374-6769 print 2374-6777 electronic

      DOIs:

      10.1145/3241304 Book

      10.1145/3241304.3241305 Preface

      10.1145/3241304.3241306 Chapter 1

      10.1145/3241304.3241307 Chapter 2

      10.1145/3241304.3241308 Chapter 3

      10.1145/3241304.3241309 Chapter 4

      10.1145/3241304.3241310 Chapter 5

      10.1145/3241304.3241311 Chapter 6

      10.1145/3241304.3241312 Chapter 7

      10.1145/3241304.3241313 Chapter 8

      10.1145/3241304.3241314 Chapter 9

      10.1145/3241304.3241315 Chapter 10

      10.1145/3241304.3241316 Chapter 11

      10.1145/3241304.3241317 Chapter 12

      10.1145/3241304.3241318 Chapter 13

      10.1145/3241304.3241319 Chapter 14

      10.1145/3241304.3241320 Chapter 15

      10.1145/3241304.3241321 Chapter 16

      10.1145/3241304.3241322 References/Index/Bios

      A publication in the ACM Books series, #24

      Editor in Chief: M. Tamer Özsu, University of Waterloo

      This book was typeset in Arnhem Pro 10/14 and Flama using ZZTEX.

      First Edition

      10 9 8 7 6 5 4 3 2 1

       Contents

Preface
Acknowledgments
PART I OVERVIEW
Chapter 1 The Frontier of Intractability
1.1 PPAD: Finding a Needle You Know Is in the Haystack
1.2 Quasi-Polynomial Time and the Birthday Paradox
1.3 Approximate Nash Equilibrium
Chapter 2 Preliminaries
Notation
2.1 Nash Equilibrium and Relaxations
2.2 PPAD and END-OF-A-LINE
2.3 Exponential Time Hypotheses
2.4 PCP Theorems
2.5 Learning Theory
2.6 Information Theory
2.7 Useful Lemmata

Скачать книгу