Monographs inTheoreticaIComputerScience An EATCS Series Editors:W.Brauer G.Rozenberg A.Salomaa Onbehalfofthe EuropeanAssocîation forTheoreticalComputerScîence(EATCS) Advisory Board: G.Ausiello M. Broy C.Calude S.Even J. Hartmanis N.Iones T.Leighton M.Nivat C.Papadimitriou D.Scott Springer-Verlag Berlin Heidelberg GmbH Lane A.Hemaspaandra • Leen Torenvliet Theoryof Semi-Feasible Algorithms With 6 Figures , Springer Authors SeriesEditors Prof.Dr.LaneA.Hemaspaandra Prof.Dr.WilfriedBrauer DepartmentofComputerScience InstitutfürInformatik UniversityofRochester TechnischeUniversitätMünchen Areisstrasse21,80333München,Germany Rochester, NY 14627 [email protected] USA [email protected] Prof.Dr.GrzegorzRozenberg LeidenInstituteofAdvancedComputerScience Dr,LeenTorenvliet UniversityofLeiden DepartmentofComputerScience NielsBohrweg1,2333CALeiden,TheNetherlands [email protected] UniversityofAmsterdarn PlantageMuidergracht24 Prof.Dr.ArtoSalomaa 1018TVAmsterdam DataCity TheNetherlands Turku CentreforComputerScience [email protected] 20500Turku,Finland [email protected] LibraryofCongressCataloging-in-PublicationData Hemaspaandra,LaneA. Theoryofsemi-feasiblealgorithms/LaneA.Hernaspaandra,LeenTorenvliet. p. cm. lncludesbibliographicalreferencesandindex. 1.Computeralgorithms.2.Computationalcomplexity.1.Torenvliet,Leen.I!.Tille. QA76.9.A43H462002 005.1-dc21 2002029158 ACMComputingClassification(1998):si.i,El.2,El.3,E2.2,E2.3,1.2.8 ISBN978-3-642-07581-0 ISBN978-3-662-05080-4(eBook) DOI10.1007/978-3-662-05080-4 This workissubjectto copyright.Allrightsare reserved,whetherthe whole or partofthe materialisconcerned,specificallytherightsoftranslation,reprinting,reuse ofillustrations, recitation,broadcasting,reproductionon microfilmorinanyotherway,and storageindata banks. Duplication of this publication or parts thereof is permitted only under the provisionsof the German CopyrightLawofSeptember9,1965,in its currentversion,and permissionfor use mustalwaysbe obtainedfrom Springer-Verlag.Violationsare liable for prosecutionundertheGermanCopyrightLaw. e Springer-VerlagBerlinHeidelberg2003 OriginallypublishedbySpringer-VerlagBerlinHeidelbergNew Yorkin2003. Softcoverreprintofthehardcover1stedition2003 The use ofgeneraldescriptive narnes,trademarks,etc.in this publicationdoes not imply, even in the absenceofa specificstatement,that such names are exemptfrom the relevant protectivelawsand regulationsandthereforefreeforgeneraluse. Cover Design:KünkelLopka,Heidelberg Typesetting:Camera-readybytheauthors Printedonacid-freepaper SPIN10797235 4513142SR- 543210 Preface An Invitation to the Dance It is an underappreciated fact that sets may have various types of complex ity, and not all types are in harmony with each other. The primary goal of this book is to unify and make more widely accessible a vibrant stream of research-the theory of semi-feasible computation-that perfectly showcases the richness of, and contrasts between, the central types of complexity. The semi-feasible sets, which are most commonly referred to as the P selective sets, are those sets L for which there is a deterministic polynornial time algorithmthat, whengivenasinput any two stringsofwhichat leastone belongsto L, will outputoneofthemthat isin L.The reason wesaythat the semi-feasiblesetsshowcase the contrasts among types ofcomplexityisthat it iswell-knownthat manysemi-feasiblesetshave no recursivealgorithms (thus theirtimecomplexitycannot be upper-boundedby standardtime-complexity classes),yet all semi-feasible sets are simple in a wide range of other natural senses. In particular, thesemi-feasiblesetshave smallcircuits, they are in the extended low hierarchy, and they cannot be NP-complete unless P = NP. The semi-feasible sets are fascinating for many reasons. First, as men tioned above, they showcase the fact that mere deterministic time complex ity is not the only potential type ofcomplexity in the world of computation. Sets that are complex in terms of deterministic time-such as nonrecursive P-selective sets-may nonetheless be simple in many other computationally natural senses. A second reason that the semi-feasible sets are interesting is that they crisply capture the complexity of (standard left cuts of) real numbers, and a recent refinement ofthe semi-feasible sets has been shown to capture the complexity of complexity-bounded real numbers. A third and more historical reason for interest in the semi-feasible sets is that they form the complexity-theoretic analog of a key class from re cursive function theory; the semi-feasible sets are exactly what one gets if one alters the definition of the semi-recursive sets by changing the selec tor function from "recursive" to "polynomial-time computable." In the late 1960s, the semi-recursive sets yielded great insights into distinguishing the power of reductions in the recursion-theoretic context. In 1979, Alan Selman launched a program that used-successfully, in the context ofstructural con- VI Preface nections to exponential time-semi-feasible sets to understand the structure of polynomial-time reductions. A fourth and somewhat surprising reason to study semi-feasible sets is that the semi-feasible sets (in their nondeterministic version) conditionally resolve the important issue of whether NP machines can cull down to one the large number of potential solutions of satisfiable formulas. In particular, the study of the semi-feasible sets has established (see Section 2.4) that NP lacks such "unique solutions" unless the polynomial hierarchy collapses. A fifth reason to study the semi-feasible sets is that the notion of semi feasibility is both natural and attractive, and fits wellinto two related broad themes of computer science: making computers "smarter" even on problems that may be too complex to solve exactly, and aUowing computers to make decisions even when they lack absolute "knowledge" of the goodness of the choices involved. For computers to be able to act and interact more intelli gentlywith users, thus helping make computingmore intuitiveto those users, it would be nice for the computersthemselves to show some "intuition" when making decisions, i.e., to act more boldly and intuitively-perhaps making membership claims that they might not "know" to be absolutely right or wrong, but that merely skate on intuition. Selectivity theory studies the sets for which a polynomial-time algorithm given two inputs-viewed as options, and potentially even as actions toward some goal-can intuit one to try, i.e., one for which to say "yes, if I had to take a flier and deelare one of those options to be a good one, I'd go with this one." Algorithms satisfying the rulesofselectivitywill have thepropertythatifthereisany good choice-one havingwhatever propertiesare possessedbytheoptionsintheset-offeredto them, they will make a good choice. Curiouslyenough, due to the possibility of there being no good choice among the options being considered, or there being no bad choice among the options being considered, the algorithms will not necessarily "know" whether their choice is good or whether any option they pass up is bad. Nonetheless, weknow that they are acting inteUigently: Ifthere wasa good optionamongtheinputs, a good optionwaschosen.Thus, by studying selectivitytheory,westudythe extent to which polynomial-time decision-making can be made "smart." Speaking more broadly, one may say that selectivity theory formalizes a natural notion of intuition and intuitive computing. We feel that this is the right time for such a book as this. Research into semi-feasible computation has already developed a rich set of tools, yet is youngenoughto have an abundanceoffresh openissues. Thoughthe primary goal of this book is to unify semi-feasibility research and make it accessible, another major goal is to lay out a path along which the reader can meet and engagetheopen problemsinthisresearcharea.Andwonderfulopenproblems do remain. Though during the past fifteen years many long-standing issues were resolved, and the semi-feasible sets were shown to be deeply connected to issues of uniqueness, self-reducibility, and nondeterminism, these very ad- Preface vii vances themselves motivated new questions.The confiuence ofexciting open issues and a rich and expanding set of technical tools with which to study the semi-feasible sets make this perhaps the best of times to join the search for knowledge about semi-feasible computation.Wehope this book will serve as both an invitation and a pathway. Logistics No previous knowledge of semi-feasible computation is required to read this book. Westartwith the definitionofsemi-feasibilityand moveon from there. However, thoughweincludein the textor theappendixfulldefinitionsofeach complexity-theoretic notion the book uses, wedo assume that the reader has the basic comfort with computational complexity concepts-and the ability to grasp new definitions-that one would gain from a typical first course on computational complexity theory. (Among the textbooks, at various levels of difficulty, on computational complexity are those of Balcázar, Diaz, and Gabarró [BDG95,BDG90], Bovet and Crescenzi [BC93],Du and Ko [DKOO], Hemaspaandra and Ogihara [H002], Homer and Selman [HS01], Papadimi triou [Pap94], and Sipser [Sip97,Part Three]). Thistextcan be thefocusofasecondcourseon computational complexity theory. In particular,wefeelthat this material is very appropriate as a semi nar course forfirst- or second-yeargraduatestudentswho have alreadytaken afirst computational complexitycourse. Wehave found that boththeoryand non-theory students value and much enjoy the concreteness and "tour of the cutting edge" aspects of a course devoted to semi-feasible computation. In virtually all of Chapters 1 through 6, the text contains no cita tions. The citations in these sections can be found in the Bibliographic Notes sections that end each chapter. The "we" used in this book (e.g., "we define," "we prove") refers to the reader and the authors as we to gether explore the theory of semi-feasible computation. Nonetheless, some of the research this book covers was done by the authors and their coau thors, and we sincerely thank those coauthors with whom we have explored semi-feasible computation: E. Allender, H. Buhrman, P. van Emde Boas, E. Hemaspaandra, H. Hempel, A. Hoene, Z. Jiang, A. Naik, C. Nasipak, A. Nickelsen, M. Ogihara, K. Parkins, J. Rothe, A. Selman, T. Thierauf, J. Wang, O. Watanabe, M. Zaki, and M. Zimand. Such research was gener ously funded by the following grants, whose support we gratefully acknowl edge: HC&M-ERB4050PL93-0516, NSF-CCR-8957604, NSF-INT-9116781j JSPS-ENGR-207, NSF-CCR-9322513, NSF-INT-9513368jDAAD-315-PRO fo-ab, NSF-INT-9815095jDAAD-315-PPP-gü-ab, and NWO-R-62-561. We are extremely grateful to C. Homan, T. Tantau, and M. Thakur for proofreading the entire book, and to W. Gasarch, M. de Graaf, S. Homer, K. Regan, J. Rothe, D. Sivakumar, M. Stol, and J. Verbeek, each of whom did a detailed proofreading ofone or more chapters ofan earlier draft of this viii Preface book. This book benefited greatly from their suggestions and insights. We also thank the many other people who helped us with advice, discussions, suggestions, most-recent-version-of-paper information, or literature pointers, including E. Allender, H. Buhrman, J. Cai, 1. Fortnow, E. Hemaspaandra, G. Magklis, A. Nickelsen, M. Ogihara, and F. Veltman. We are grateful to the Springer series editors-Wo Brauer, G.Rozenberg, and A. Salomaa-and staff-A. Hofmann, F. Holzwarth, U. Stricker, T. Toomey, H. Wössner, and especially 1.Mayer-for their advice and help. Above all, we thank our families for their love and encouragement. Rochester, New York, September 2002 Lane A. Hemaspaandm Amsterdam, September 2002 Leen Torenvliet Contents Preface v 1. Introduetion to Semi-Feasible Computation............... 1 1.1 P-Selectivity .. ..................... ... ...... .... ....... 1 1.1.1 Background and Definitions 1 1.1.2 Basic Properties.................................. 3 1.2 Nondeterministic Selectivity .................. 9 1.2.1 Background and Definitions 9 1.2.2 Basic Properties.................................. 10 1.3 Bibliographic Notes ..................................... 15 2. Advice.... ... ... .... .... .... ... ... ..... .......... .. .. .. ... 17 2.1 Advice Strings and Circuits 17 2.2 Advice for P-Selective Sets 20 2.2.1 Upper Bounds on the Amount of Advice for P-Selective Sets. ................................. 21 2.2.2 Are There P-Selective Sets Other Than Standard Left Cuts? ........... .... ........ ..... .. .......... 28 2.2.3 Lower Bounds 31 2.3 Advice for Nondeterministically Selective Sets .............. 32 2.4 Are There Unique Solutions for NP? ...................... 35 2.4.1 Small Circuits and the Polynomial Hierarchy......... 35 2.4.2 NP Lacks Unique Solutions Unless the Polynomial Hierarchy Collapses ... ................. 38 2.5 Bibliographic Notes ..................................... 39 3. Lowness ...... ...... .. .... .... .. ........ ... .. ..... ....... . 41 3.1 Lowness Basics ......................................... 41 3.1.1 Basic Lowness Theory 41 3.1.2 Extended Lowness and Refined Lowness............. 43 3.2 Lowness of P-Selective Sets. ............................. 46 3.2.1 Upper Bounds .... 47 3.2.2 Lower Bounds 48 3.3 Lowness of Nondeterministically Selective Sets ............. 49 x Contents 3.3.1 Upper Bounds ............................ 49 3.3.2 Lower Bounds 58 3.4 Bibliographic Notes ..................................... 58 4. Hardness for Complexity Classes ....... 61 4.1 Can P-Selective Sets Be Hard for Complexity Classes? 61 4.2 Can P-Selective Sets Be Truth-Table-Hard for UP, .6.~, PSPACE, or EXP? 62 4.3 Can P-Selective Sets Be Truth-Table-Hard or Turing-Hard for NP? 67 4.4 Can Nondeterministically Selective Sets Be NP-Hard or coNP-Hard? ......................................... 73 4.5 Bibliographic Notes ..................................... 75 5. Closures ......... ... .... .. ...... ..... ..... ............ .... 79 5.1 Connectives and Reductions ...................... 80 5.2 Boolean Closures " 81 5.3 Reductions Under Which P-sel Is Closed Downward 85 5.4 Self-Reducible Sets and Selectivity........................ 88 5.5 Reduction and Equivalence Classes ... .................... 94 5.5.1 Equalities ...... .. ... .. .... ... ........ .. ... .. .. .. 94 5.5.2 Inequalities .... ... ... .. ... .......... ......... ... . 95 5.& Bibliographic Notes 102 6. Generalizations and Related Notions 105 6.1 Generalizations of Selectivity 105 6.1.1 Weak Selectivity 105 6.1.2 Multiselectivity:The S(k) Hierarchy 106 6.1.3 Membership Comparable Sets 107 6.1.4 Probabilistic Selector Functions 109 6.2 P-Semi-Rankability: A Provable Refinement of P-Selectivity . 110 6.3 Associative P-Selectivity:A Potential Refinement of P-Selectivity 111 6.4 Bibliographic Notes , 112 A. Definitions ofReductions and Complexity Classes, and Notation List 115 A.1 Reductions 115 A.2 Complexity Classes 116 A.3 Some Other Notation , 123 References 125 Index 133