The Computational Complexity of Abduction

高三现代科技前沿探索英语阅读理解20题1<背景文章>Artificial intelligence (AI) is rapidly transforming the field of healthcare. In recent years, AI has made significant progress in various aspects of medical care, bringing new opportunities and challenges.One of the major applications of AI in healthcare is in disease diagnosis. AI-powered systems can analyze large amounts of medical data, such as medical images and patient records, to detect diseases at an early stage. For example, deep learning algorithms can accurately identify tumors in medical images, helping doctors make more accurate diagnoses.Another area where AI is making a big impact is in drug discovery. By analyzing vast amounts of biological data, AI can help researchers identify potential drug targets and design new drugs more efficiently. This can significantly shorten the time and cost of drug development.AI also has the potential to improve patient care by providing personalized treatment plans. Based on a patient's genetic information, medical history, and other factors, AI can recommend the most appropriate treatment options.However, the application of AI in healthcare also faces some challenges. One of the main concerns is data privacy and security. Medicaldata is highly sensitive, and ensuring its protection is crucial. Another challenge is the lack of transparency in AI algorithms. Doctors and patients need to understand how AI makes decisions in order to trust its recommendations.In conclusion, while AI holds great promise for improving healthcare, it also poses significant challenges that need to be addressed.1. What is one of the major applications of AI in healthcare?A. Disease prevention.B. Disease diagnosis.C. Health maintenance.D. Medical education.答案：B。

1An Introduction to Description LogicsDaniele NardiRonald J.BrachmanAbstractThis introduction presents the main motivations for the development of Description Logics(DL)as a formalism for representing knowledge,as well as some important basic notions underlying all systems that have been created in the DL tradition. In addition,we provide the reader with an overview of the entire book and some guidelines for reading it.Wefirst address the relationship between Description Logics and earlier seman-tic network and frame systems,which represent the original heritage of thefield. We delve into some of the key problems encountered with the older efforts.Subse-quently,we introduce the basic features of Description Logic languages and related reasoning techniques.Description Logic languages are then viewed as the core of knowledge represen-tation systems,considering both the structure of a DL knowledge base and its associated reasoning services.The development of some implemented knowledge representation systems based on Description Logics and thefirst applications built with such systems are then reviewed.Finally,we address the relationship of Description Logics to otherfields of Com-puter Science.We also discuss some extensions of the basic representation language machinery;these include features proposed for incorporation in the formalism that originally arose in implemented systems,and features proposed to cope with the needs of certain application domains.1.1IntroductionResearch in thefield of knowledge representation and reasoning is usually focused on methods for providing high-level descriptions of the world that can be effectively used to build intelligent applications.In this context,“intelligent”refers to the abil-56 D.Nardi,R.J.Brachmanity of a system tofind implicit consequences of its explicitly represented knowledge. Such systems are therefore characterized as knowledge-based systems. Approaches to knowledge representation developed in the1970’s—when thefield enjoyed great popularity—are sometimes divided roughly into two categories:logic-based formalisms,which evolved out of the intuition that predicate calculus could be used unambiguously to capture facts about the world;and other,non-logic-based representations.The latter were often developed by building on more cognitive notions—for example,network structures and rule-based representations derived from experiments on recall from human memory and human execution of tasks like mathematical puzzle solving.Even though such approaches were often developed for specific representational chores,the resulting formalisms were usually expected to serve in general use.In other words,the non-logical systems created from very specific lines of thinking(e.g.,early Production Systems)evolved to be treated as general purpose tools,expected to be applicable in different domains and on different types of problems.On the other hand,sincefirst-order logic provides very powerful and general ma-chinery,logic-based approaches were more general-purpose from the very start.In a logic-based approach,the representation language is usually a variant offirst-order predicate calculus,and reasoning amounts to verifying logical consequence.In the non-logical approaches,often based on the use of graphical interfaces,knowledge is represented by means of some ad hoc data structures,and reasoning is accomplished by similarly ad hoc procedures that manipulate the structures.Among these spe-cialized representations wefind semantic networks and frames.Semantic Networks were developed after the work of Quillian[1967],with the goal of characterizing by means of network-shaped cognitive structures the knowledge and the reasoning of the system.Similar goals were shared by later frame systems[Minsky,1981],which rely upon the notion of a“frame”as a prototype and on the capability of expressing relationships between frames.Although there are significant differences between se-mantic networks and frames,both in their motivating cognitive intuitions and in their features,they have a strong common basis.In fact,they can both be regarded as network structures,where the structure of the network aims at representing sets of individuals and their relationships.Consequently,we use the term network-based structures to refer to the representation networks underlying semantic networks and frames(see[Lehmann,1992]for a collection of papers concerning various families of network-based structures).Owing to their more human-centered origins,the network-based systems were often considered more appealing and more effective from a practical viewpoint than the logical systems.Unfortunately they were not fully satisfactory because of their usual lack of precise semantic characterization.The end result of this was that every system behaved differently from the others,in many cases despite virtually identical-An Introduction to Description Logics7 looking components and even identical relationship names.The question then arose as to how to provide semantics to representation structures,in particular to semantic networks and frames,which carried the intuition that,by exploiting the notion of hierarchical structure,one could gain both in terms of ease of representation and in terms of the efficiency of reasoning.One important step in this direction was the recognition that frames(at least their core features)could be given a semantics by relying onfirst-order logic[Hayes, 1979].The basic elements of the representation are characterized as unary pred-icates,denoting sets of individuals,and binary predicates,denoting relationships between individuals.However,such a characterization does not capture the con-straints of semantic networks and frames with respect to logic.Indeed,although logic is the natural basis for specifying a meaning for these structures,it turns out that frames and semantic networks(for the most part)did not require all the ma-chinery offirst-order logic,but could be regarded as fragments of it[Brachman and Levesque,1985].In addition,different features of the representation language would lead to different fragments offirst-order logic.The most important consequence of this fact is the recognition that the typical forms of reasoning used in structure-based representations could be accomplished by specialized reasoning techniques, without necessarily requiringfirst-order logic theorem provers.Moreover,reason-ing in different fragments offirst-order logic leads to computational problems of differing complexity.Subsequent to this realization,research in the area of Description Logics began under the label terminological systems,to emphasize that the representation lan-guage was used to establish the basic terminology adopted in the modeled domain. Later,the emphasis was on the set of concept-forming constructs admitted in the language,giving rise to the name concept languages.In more recent years,after at-tention was further moved towards the properties of the underlying logical systems, the term Description Logics became popular.In this book we mainly use the term“Description Logics”(DL)for the represen-tation systems,but often use the word“concept”to refer to the expressions of a DL language,denoting sets of individuals;and the word“terminology”to denote a (hierarchical)structure built to provide an intensional representation of the domain of interest.Research on Description Logics has covered theoretical underpinnings as well as implementation of knowledge representation systems and the development of appli-cations in several areas.This kind of development has been quite successful.The key element has been the methodology of research,based on a very close interaction between theory and practice.On the one hand,there are various implemented sys-tems based on Description Logics,which offer a palette of description formalisms with differing expressive power,and which are employed in various application do-8 D.Nardi,R.J.Brachmanmains(such as natural language processing,configuration of technical products,or databases).On the other hand,the formal and computational properties of reason-ing(like decidability and complexity)of various description formalisms have been investigated in detail.The investigations are usually motivated by the use of cer-tain constructors in implemented systems or by the need for these constructors in specific applications—and the results have influenced the design of new systems. This book is meant to provide a thorough introduction to Description Logics, covering all the above-mentioned aspects of DL research—namely theory,imple-mentation,and applications.Consequently,the book is divided into three parts:•Part I introduces the theoretical foundations of Description Logics,addressing some of the most recent developments in theoretical research in the area;•Part II focuses on the implementation of knowledge representation systems based on Description Logics,describing the basic functionality of a DL system,survey-ing the most influential knowledge representation systems based on Description Logics,and addressing specialized implementation techniques;•Part III addresses the use of Description Logics and of DL-based systems in the design of several applications of practical interest.In the remainder of this introductory chapter,we review the main steps in the development of Description Logics,and introduce the main issues that are dealt with later in the book,providing pointers for its reading.In particular,in the next section we address the origins of Description Logics and then we review knowledge representation systems based on Description Logics,the main applications devel-oped with Description Logics,the main extensions to the basic DL framework and relationships with otherfields of Computer Science.1.2From networks to Description LogicsIn this section we begin by recalling approaches to representing knowledge that were developed before research on Description Logics began(i.e.,semantic networks and frames).We then provide a very brief introduction to the basic elements of these approaches,based on Tarski-style semantics.Finally,we discuss the importance of computational analyses of the reasoning methods developed for Description Logics, a major ingredient of research in thisfield.1.2.1Network-based representation structuresIn order to provide some intuition about the ideas behind representations of knowl-edge in network form,we here speak in terms of a generic network,avoiding ref-erences to any particular system.The elements of a network are nodes and links.An Introduction to Description Logics9Typically,nodes are used to characterize concepts,i.e.,sets or classes of individ-ual objects,and links are used to characterize relationships among them.In some cases,more complex relationships are themselves represented as nodes;these are carefully distinguished from nodes representing concepts.In addition,concepts can have simple properties,often called attributes,which are typically attached to the corresponding nodes.Finally,in many of the early networks both individual objects and concepts were represented by nodes.Here,however,we restrict our attention to knowledge about concepts and their relationships,deferring for now treatment of knowledge about specific individuals.Let us consider a simple example,whose pictorial representation is given in Fig-ure1.1,which represents knowledge concerning persons,parents,children,etc.The structure in thefigure is also referred to as a terminology,and it is indeed meant to represent the generality/specificity of the concepts involved.For example the link between Mother and Parent says that“mothers are parents”;this is sometimes called an“IS-A”relationship.The IS-A relationship defines a hierarchy over the concepts and provides the basis for the“inheritance of properties”:when a concept is more specific than some other concept,it inherits the properties of the more general one.For example,if a person has an age,then a mother has an age,too.This is the typical setting of the so-called (monotonic)inheritance networks(see[Brachman,1979]).A characteristic feature of Description Logics is their ability to represent other kinds of relationships that can hold between concepts,beyond IS-A relationships. For example,in Figure1.1,which follows the notation of[Brachman and Schmolze, 1985],the concept of Parent has a property that is usually called a“role,”expressed10 D.Nardi,R.J.Brachmanby a link from the concept to a node for the role labeled hasChild.The role has what is called a“value restriction,”denoted by the label v/r,which expresses a limitation on the range of types of objects that canfill that role.In addition,the node has a number restriction expressed as(1,NIL),where thefirst number is a lower bound on the number of children and the second element is the upper bound, and NIL denotes infinity.Overall,the representation of the concept of Parent here can be read as“A parent is a person having at least one child,and all of his/her children are persons.”Relationships of this kind are inherited from concepts to their subconcepts.For example,the concept Mother,i.e.,a female parent,is a more specific descendant of both the concepts Female and Parent,and as a result inherits from Parent the link to Person through the role hasChild;in other words,Mother inherits the restriction on its hasChild role from Parent.Observe that there may be implicit relationships between concepts.For example, if we define Woman as the concept of a female person,it is the case that every Mother is a Woman.It is the task of the knowledge representation system tofind implicit relationships such as these(many are more complex than this one).Typically,such inferences have been characterized in terms of properties of the network.In this case one might observe that both Mother and Woman are connected to both Female and Person,but the path from Mother to Person includes a node Parent,which is more specific then Person,thus enabling us to conclude that Mother is more specific than Person.However,the more complex the relationships established among concepts,the more difficult it becomes to give a precise characterization of what kind of relation-ships can be computed,and how this can be done without failing to recognize some of the relationships or without providing wrong answers.1.2.2A logical account of network-based representation structures Building on the above ideas,a number of systems were implemented and used in many kinds of applications.As a result,the need emerged for a precise character-ization of the meaning of the structures used in the representations and of the set of inferences that could be drawn from those structures.A precise characterization of the meaning of a network can be given by defining a language for the elements of the structure and by providing an interpretation for the strings of that language.While the syntax may have differentflavors in different settings,the semantics is typically given as a Tarski-style semantics.For the syntax we introduce a kind of abstract language,which resembles other logical formalisms.The basic step of the construction is provided by two disjoint alphabets of symbols that are used to denote atomic concepts,designated by unaryAn Introduction to Description Logics11 predicate symbols,and atomic roles,designated by binary predicate symbols;the latter are used to express relationships between concepts.Terms are then built from the basic symbols using several kinds of constructors. For example,intersection of concepts,which is denoted C D,is used to restrict the set of individuals under consideration to those that belong to both C and D.Notice that,in the syntax of Description Logics,concept expressions are variable-free.In fact,a concept expression denotes the set of all individuals satisfying the properties specified in the expression.Therefore,C D can be regarded as thefirst-order logic sentence,C(x)∧D(x),where the variable ranges over all individuals in the interpretation domain and C(x)is true for those individuals that belong to the concept C.In this book,we will present other syntactic notations that are more closely related to the concrete syntax adopted by implemented DL systems,and which are more suitable for the development of applications.One example of concrete syntax proposed in[Patel-Schneider and Swartout,1993]is based on a Lisp-like notation,where the concept of female persons,for example,is denoted by(and Person Female).The key characteristic features of Description Logics reside in the constructs for establishing relationships between concepts.The basic ones are value restrictions. For example,a value restriction,written∀R.C,requires that all the individuals that are in the relationship R with the concept being described belong to the concept C (technically,it is all individuals that are in the relationship R with an individual described by the concept in question that are themselves describable as C’s).As for the semantics,concepts are given a set-theoretic interpretation:a concept is interpreted as a set of individuals and roles are interpreted as sets of pairs of individuals.The domain of interpretation can be chosen arbitrarily,and it can be infinite.The non-finiteness of the domain and the open-world assumption are distinguishing features of Description Logics with respect to the modeling languages developed in the study of databases(see Chapters4,and16).Atomic concepts are thus interpreted as subsets of the intepretation domain, while the semantics of the other constructs is then specified by defining the set of individuals denoted by each construct.For example,the concept C D is the set of individuals obtained by intersecting the sets of individuals denoted by C and D, respectively.Similarly,the interpretation of∀R.C is the set of individuals that are in the relationship R with individuals belonging to the set denoted by the concept C. As an example,let us suppose that Female,Person,and Woman are atomic con-cepts and that hasChild and hasFemaleRelative are atomic ing the operators intersection,union and complement of concepts,interpreted as set operations,we can describe the concept of“persons that are not female”and the concept of“in-12 D.Nardi,R.J.Brachmandividuals that are female or male”by the expressionsPerson ¬Female and Female Male.It is worth mentioning that intersection,union,and complement of concepts havebeen also referred to as concept conjunction,concept disjunction and concept nega-tion,respectively,to emphasize the relationship to logic.Let us now turn our attention to role restrictions by lookingfirst at quantifiedrole restrictions and,subsequently,at what we call“number restrictions.”Mostlanguages provide(full)existential quantification and value restriction that allowone to describe,for example,the concept of“individuals having a female child”as∃hasChild.Female,and to describe the concept of“individuals all of whose children are female”by the concept expression∀hasChild.Female.In order to distinguish thefunction of each concept in the relationship,the individual object that correspondsto the second argument of the role viewed as a binary predicate is called a rolefiller.In the above expressions,which describe the properties of parents havingfemale children,individual objects belonging to the concept Female are thefillers ofthe role hasChild.Existential quantification and value restrictions are thus meant to characterizerelationships between concepts.In fact,the role link between Parent and Person inFigure1.1can be expressed by the concept expression∃hasChild.Person ∀hasChild.Person.Such an expression therefore characterizes the concept of Parent as the set of indi-viduals having at least onefiller of the role hasChild belonging to the concept Person;moreover,everyfiller of the role hasChild must be a person.Finally,notice that in quantified role restrictions the variable being quantifiedis not explicitly mentioned.The corresponding sentence infirst-order logic is∀y.R(x,y)⊃C(y),where x is again a free variable ranging over the interpreta-tion domain.Another important kind of role restriction is given by number restrictions,whichrestrict the cardinality of the sets offillers of roles.For instance,the concept( 3hasChild) ( 2hasFemaleRelative)represents the concept of“individuals having at least three children and at mosttwo female relatives.”Number restrictions are sometimes viewed as a distinguishingfeature of Description Logics,although one canfind some similar constructs in somedatabase modeling languages(notably Entity-Relationship models).Beyond the constructs to form concept expressions,Description Logics provideconstructs for roles,which can,for example,establish role hierarchies.However,An Introduction to Description Logics13 the use of role expressions is generally limited to expressing relationships between concepts.Intersection of roles is an example of a role-forming construct.Intuitively, hasChild hasFemaleRelative yields the role“has-daughter,”so that the concept expressionWoman 2(hasChild hasFemaleRelative)denotes the concept of“a woman having at most2daughters”.A more comprehensive view of the basic definitions of DL languages will be given in Chapter2.1.2.3ReasoningThe basic inference on concept expressions in Description Logics is subsumption, typically written as C D.Determining subsumption is the problem of checking whether the concept denoted by D(the subsumer)is considered more general than the one denoted by C(the subsumee).In other words,subsumption checks whether thefirst concept always denotes a subset of the set denoted by the second one. For example,one might be interested in knowing whether Woman Mother.In order to verify this kind of relationship one has in general to take into account the relationships defined in the terminology.As we explain in the next section, under appropriate restrictions,one can embody such knowledge directly in concept expressions,thus making subsumption over concept expressions the basic reason-ing task.Another typical inference on concept expressions is concept satisfiability, which is the problem of checking whether a concept expression does not necessarily denote the empty concept.In fact,concept satisfiability is a special case of sub-sumption,with the subsumer being the empty concept,meaning that a concept is not satisfiable.Although the meaning of concepts had already been specified with a logical se-mantics,the design of inference procedures in Description Logics was influenced for a long time by the tradition of semantic networks,where concepts were viewed as nodes and roles as links in a network.Subsumption between concept expressions was recognized as the key inference and the basic idea of the earliest subsumption al-gorithms was to transform two input concepts into labeled graphs and test whether one could be embedded into the other;the embedded graph would correspond to the more general concept(the subsumer)[Lipkis,1982].This method is called structural comparison,and the relation between concepts being computed is called structural subsumption.However,a careful analysis of the algorithms for structural subsumption shows that they are sound,but not always complete in terms of the logical semantics:whenever they return“yes”the answer is correct,but when they14 D.Nardi,R.J.Brachmanreport“no”the answer may be incorrect.In other words,structural subsumptionis in general weaker than logical subsumption.The need for complete subsumption algorithms is motivated by the fact that inthe usage of knowledge representation systems it is often necessary to have a guar-antee that the system has not failed in verifying subsumption.Consequently,newalgorithms for computing subsumption have been devised that are no longer basedon a network representation,and these can be proven to be complete.Such algo-rithms have been developed by specializing classical settings for deductive reasoningto the DL subsets offirst-order logics,as done for tableau calculi by Schmidt-Schaußand Smolka[1991],and also by more specialized methods.In the paper“The Tractability of Subsumption in Frame-Based Description Lan-guages,”Brachman and Levesque[1984]argued that there is a tradeoffbetweenthe expressiveness of a representation language and the difficulty of reasoning overthe representations built using that language.In other words,the more expressivethe language,the harder the reasoning.They also provided afirst example of thistradeoffby analyzing the language FL−(Frame Language),which included inter-section of concepts,value restrictions and a simple form of existential quantification.They showed that for such a language the subsumption problem could be solvedin polynomial time,while adding a construct called role restriction to the languagemakes subsumption a co np-hard problem(the extended language was called FL).The paper by Brachman and Levesque introduced at least two new ideas:(i)“efficiency of reasoning”over knowledge structures can be studied using thetools of computational complexity theory;(ii)different combinations of constructs can give rise to languages with differentcomputational properties.An immediate consequence of the above observations is that one can study for-mally and methodically the tradeoffbetween the computational complexity of rea-soning and the expressiveness of the language,which itself is defined in termsof the constructs that are admitted in the language.After the initial pa-per,a number of results on this tradeofffor concept languages were obtained(see Chapters2and3),and these results allow us to draw a fairly completepicture of the complexity of reasoning for a wide class of concept languages.Moreover,the problem offinding the optimal tradeoff,namely the most ex-pressive extensions of FL−with respect to a given set of constructs that still keep subsumption polynomial,has been studied extensively[Donini et al.,1991b; 1999].One of the assumptions underlying this line of research is to use worst-case com-plexity as a measure of the efficiency of reasoning in Description Logics(and moregenerally in knowledge representation formalisms).Such an assumption has some-An Introduction to Description Logics15 times been criticized(see for example[Doyle and Patil,1991])as not adequately characterizing system performance or accounting for more average-case behavior. While this observation suggests that computational complexity alone may not be sufficient for addressing performance issues,research on the computational com-plexity of reasoning in Description Logics has most definitely led to a much deeper understanding of the problems arising in implementing reasoning tools.Let us briefly address some of the contributions of this body of work.First of all,the study of the computational complexity of reasoning in Description Logics has led to a clear understanding of the properties of the language constructs and their interaction.This is not only valuable from a theoretical viewpoint,but gives insight to the designer of deduction procedures,with clear indications of the language constructs and their combinations that are difficult to deal with,as well as general methods to cope with them.Secondly,the complexity results have been obtained by exploiting a general tech-nique for satisfiability-checking in concept languages,which relies on a form of tableau calculus[Schmidt-Schaußand Smolka,1991].Such a technique has proved extremely useful for studying both the correctness and the complexity of the algo-rithms.More specifically,it provides an algorithmic framework that is parametric with respect to the language constructs.The algorithms for concept satisfiability and subsumption obtained in this way have also led directly to practical implemen-tations by application of clever control strategies and optimization techniques.The most recent knowledge representation systems based on Description Logics adopt tableau calculi[Horrocks,1998b].Thirdly,the analysis of pathological cases in this formal framework has led to the discovery of incompleteness in the algorithms developed for implemented systems. This has also consequently proven useful in the definition of suitable test sets for verifying implementations.For example,the comparison of implemented systems (see for example[Baader et al.,1992b;Heinsohn et al.,1992])has greatly benefitted from the results of the complexity analysis.The basic reasoning techniques for Description Logics are presented in Chapter2, while a detailed analysis of the complexity of reasoning problems in several languages is developed in Chapter3.After the tradeoffbetween expressiveness and tractability of reasoning was thor-oughly analyzed and the range of applicability of the corresponding inference tech-niques had been experimented with,there was a shift of focus in the theoretical research on reasoning in Description Logics.Interest grew in relating Description Logics to the modeling languages used in database management.In addition,the discovery of strict relationships with expressive modal logics stimulated the study of so-called very expressive Description Logics.These languages,besides admit-ting very general mechanisms for defining concepts(for example cyclic definitions,。

The Computational Complexity ColumnbyLance FORTNOWNEC Laboratories America4Independence Way,Princeton,NJ08540,USAfortnow@/homepages/fortnow/beatcs Every third year the Conference on Computational Complexity is held in Europe and this summer the University of Aarhus(Denmark)will host the meeting July7-10.More details at the conference web pageThis month we present a historical view of computational complexity written by Steve Homer and myself.This is a preliminary version of a chapter to be included in an upcoming North-Holland Handbook of the History of Mathematical Logic edited by Dirk van Dalen,John Dawson and Aki Kanamori.A Short History of Computational ComplexityLance Fortnow1Steve Homer2NEC Research Institute Computer Science Department4Independence Way Boston UniversityPrinceton,NJ08540111Cummington StreetBoston,MA022151IntroductionIt all started with a machine.In1936,Turing developed his theoretical com-putational model.He based his model on how he perceived mathematicians think.As digital computers were developed in the40’s and50’s,the Turing machine proved itself as the right theoretical model for computation.Quickly though we discovered that the basic Turing machine model fails to account for the amount of time or memory needed by a computer,a critical issue today but even more so in those early days of computing.The key idea to measure time and space as a function of the length of the input came in the early1960’s by Hartmanis and Stearns.And thus computational complexity was born.In the early days of complexity,researchers just tried understanding these new measures and how they related to each other.We saw thefirst notion of efficient computation by using time polynomial in the input size. This led to complexity’s most important concept,NP-completeness,and its most fundamental question,whether P=NP.The work of Cook and Karp in the early70’s showed a large number of combinatorial and logical problems were NP-complete,i.e.,as hard as any problem computable in nondeterministic polynomial time.The P=NP question is equivalent to an efficient solution of any of these problems.In the thirty years hence this problem has become one of the outstanding open questions in computer science and indeed all of mathematics.In the70’s we saw the growth of complexity classes as researchers tried to encompass different models of computations.One of those models,prob-abilistic computation,started with a probabilistic test for primality,led to probabilistic complexity classes and a new kind of interactive proof system that itself led to hardness results for approximating certain NP-complete problems.We have also seen strong evidence that we can remove the ran-domness from computations and most recently a deterministic algorithm for the original primality problem.In the80’s we saw the rise offinite models like circuits that capture computation in an inherently different way.A new approach to problems like P=NP arose from these circuits and though they have had limited success in separating complexity classes,this approach brought combinato-rial techniques into the area and led to a much better understanding of the limits of these devices.In the90’s we have seen the study of new models of computation like quantum computers and propositional proof systems.Tools from the past have greatly helped our understanding of these new areas.One cannot in the short space of this article mention all of the amazing research in computational complexity theory.We survey various areas in complexity choosing papers more for their historical value than necessarily the importance of the results.We hope that this gives an insight into the richness and depth of this still quite youngfield.2Early HistoryWhile we can trace the idea of“efficient algorithms”to the ancient Greeks, our story starts with the seminal1965paper of Hartmanis and Stearns,“On the Computational Complexity of Algorithms”[HS65].This paper laid out the definitions of quantified time and space complexity on multitape Turing machines and showed thefirst results of the form given more time(or space) one can compute more things.A multitape Turing machine consists of somefixed number of“tapes”each of which contains an infinite number of tape cells.The contents of a tape cell comes from afinite set of symbols called the tape alphabet of the Turing machine.All the tapes initially contain only a special“blank”character except for thefinite input written at the beginning of thefirst tape.Each tape has a tape head sitting on thefirst character on each tape. The Turing machine also has afinite state memory to control its operations. In each step,it can move each tape independently one character left or right, read and possibly change the characters under each head,change its current state and decide whether to halt and accept or reject the input.Time is measured by the number of steps before halting as a function of the length of the input.Space is measured as the number of different character locations touched by the various heads.The Hartmanis-Stearns paper did not develop in a vacuum.Turing[Tur36], of course,developed his notion of a computational device back in1936. This machine model did and still does form the basis for most of compu-tational complexity.Slightly earlier,Yamada[Yam62]studied“real-time computable functions”,Myhill[Myh60]looked at linear bounded automata and Smullyan[Smu61]considered rudimentary sets.These models looked at specific time and space-bounded machines but did not give a general approach to measuring complexity.After Hartmanis and Stearns developed the general method for mea-suring computational resources,one can ask how the different variations of Turing machines affect the complexity of problems.Rabin[Rab63]shows problems solvable faster by two-tape machine than by one-tape machines. Hennie and Stearns[HS66]show that a2-tape Turing machine can simulate any constant tape machine taking only a logarithmic factor more time.Hartmanis and Stearns show that given space functions s1and s2with a “constructibility”condition and s1(n)=o(s2(n)),i.e.,s1(n)/s2(n)goes to zero,then there are problems computable in space s2(n)but not space s1(n). The Hennie-Stearns result gives the best known time-hierarchy,getting a separation if t1(n)log t1(n)=o(t2(n)).These proofs use straightforwarddiagonalization arguments that go back to Cantor[Can74].Nondeterministic computation allows a Turing machine to make a choice of several possible transitions.We say the machine accepts if any collection of choices leads to an accepting state.Nondeterministic time and space hierarchies are much trickier to prove because one cannot do straightforward diagonalization on nondeterministic computations.Savitch[Sav70]showed that problems computable in nondeterministic space s(n)are computable in deterministic space s2(n).In1972,Ibarra[Iba72] using translational techniques of Ruby and Fischer[RF65]used Savitch’s theorem to show that there exist problems computable in nondeterministic space n a but not space n b for a>b≥1.Sixteen years later,Immer-man[Imm88]and Szelepcs´e nyi[Sze88]independently showed that nonde-terministic space is closed under complement.The Immerman-Szelepcs´e nyi result immediately gives a nondeterministic space hierarchy as tight as the the deterministic hierarchy.For nondeterministic time,Cook[Coo73]uses a more careful translation argument to show problems computable in nondeterministic time n a but not time n b for a>b≥1.Seiferas,Fischer and Meyer[SFM78]give the current best known nondeterministic time hierarchy,getting a separation if t1(n+1)=o(t2(n)).In1967,Blum[Blu67]had his speed-up theorem:For any computable unbounded function r(n)there exists a computable language L such that for any Turing machine accepting L in time t(n)there is another Turing machine accepting L in time r(t(n)).This seems to violate the time hi-erarchy mentioned earlier but one must realize t(n)will not necessarily be time-constructible.Blum’s speed-up theorem holds not only for time but also for space and any other measure fulfilling a small list of axioms,which we now call Blum complexity measures.Soon after we saw two other major results that we will state for time but also hold for all Blum complexity measures.Independently Borodin[Bor72] and Trakhtenbrot[Tra64]proved the gap theorem:For any computable un-bounded r(n)there exist a computable time bound t(n)such that any lan-guage computable in time t(n)is also computable in time r(t(n)).McCreight and Meyer[MM69]showed the union theorem:Given any computably pre-sentable list of computable time bounds t1,t2,...such that t i+1>t i for all i then there exist a time bound t such that a problem is computable in time t if and only if it is computable in time t i for some i.In1964,Cobham[Cob64]noted that the set of problems computable in polynomial time remains independent of the particular deterministic ma-chine model.He also showed that many common mathematical functions can be computed in polynomial time.In1965,Edmonds[Edm65b]in his paper showing that the matching problem has a polynomial-time algorithm,argues that polynomial-time gives a good formalization of efficient computation.He noted the wide range of problems computable in polynomial time and as well the fact that this class of problems remains the same under many different reasonable models of computation.In another paper,Edmonds[Edm65a]gave an informal description of nondeterministic polynomial-time.This set the stage for the P=NP question,the most famous problem in theoretical computer science that we discuss in Section3.Several Russians,notably Barzdin and Trakhtenbrot,independently de-veloped several of these notions of complexity during the sixties though their work was not known to the West until the seventies.3NP-completenessIt was in the early1970’s that complexity theoryfirstflowered,and came to play a central role in computer science.It did so by focusing on one fundamental concept and on the results and ideas stemming from it.This concept was NP-completeness and it has proved to be one of the most insightful and fundamental theories in the mathematics of the last half cen-tury.NP-completeness captures the combinatorial difficulty of a number of central problems which resisted efficient solution and provides a method for proving that a combinatorial problem is as intractable as any NP problem.By the late1960’s,a sizable class of very applicable and significant prob-lems which resisted polynomial time solution was widely recognized.These problems are largely optimization problems such as the traveling salesman problem,certain scheduling problems,or linear programming problems. They all have a very large number of possible solution where there is no obvious way tofind an optimal solution other than a brute force search.As time passed and much effort was expended on attempts at efficiently solving these problems,it began to be suspected that there was no such solution. However,there was no hard evidence that this was the case nor was there any reason to suspect that these problems were in any sense difficult for the same reasons or in the same ways.The theory of NP-completeness provided precisely this evidence.Proving a problem in NP to be NP-complete tells us that it is as hard to solve as any other NP problem.Said another way,if there is any NP-complete problem that admits an efficient solution then every NP problem does so.The question of whether every NP problem has an efficient solution has resisted the efforts of computer scientists since1970.It is known as the P versus NP problem and is among the most central open problems of mathematics.The fact that a very large number of fundamental problems have been shown to be NP-complete and that the problem of proving that P is not NP has proved to be so difficult has made this problem and the connected theory one of the most celebrated in contemporary mathematics. The P=NP problem is one of the seven Millennium Prize Problems and solving it brings a$1,000,000prize from the Clay Mathematics Institute [Cla00].Quite surprisingly,one of the earliest discussions of a particular NP-complete problem and the implications offinding an efficient solution came from Kurt G¨o del.In a1956letter to von Neumann[Har86,Sip83]G¨o del asks von Neumann about the complexity of what is now known to be an NP-complete problem concerning proofs infirst-order logic and asks if the problem can be solved in linear or quadratic time.In fact,G¨o del seemed quite optimistic aboutfinding an efficient solution.He fully realized that doing so would have significant consequences.It is worth noting that in about the same period there was considerable effort by Russian mathematicians working on similar combinatorial problems trying to prove that brute force was needed to solve them.Several of these problems eventually turned out to be NP-complete as well[Tra64].The existence of NP-complete problems was proved independently by Stephen Cook in the United States and Leonid Levin in the Soviet Union. Cook,then a graduate student at Harvard,proved that the satisfiabil-ity problem is NP-complete[Coo71].Levin,a student of Kolmogorov at Moscow State University,proved that a variant of the tiling problem is NP-complete[Lev73].Researchers strove to show other interesting,natural problems NP-complete.Richard Karp,in a tremendously influential paper[Kar72],proved that eight central combinatorial problems are all NP-complete.These prob-lems included the the clique problem,the independent set problem,the set cover problem,and the traveling salesman problem,among others.Karp’s paper presented several key methods to prove NP-completeness using reductions from problems previously shown to be NP-complete.It set up a general framework for proving NP-completeness results and established several useful techniques for such proofs.In the following years,and con-tinuing until today,literally thousands of problems have been shown to be NP-complete.A proof of NP-completeness has come to signify the(worstcase)intractability of a problem.Once proved NP-complete,researchers turn to other ways of trying to solve the problem,usually using approxima-tion algorithms to give an approximate solution or probabilistic methods to solve the problem in“most”cases.Another fundamental step was taken around1970by Meyer and Stock-meyer[MS72],[Sto76].They defined the polynomial hierarchy in analogy with the arithmetic hierarchy of Kleene.This hierarchy is defined by it-erating the notion of polynomial jump,in analogy with the Turing jump operator.This hierarchy has proven useful in classifying many hard combi-natorial problems which do not lie in NP.It is explored in more detail in Section4.2.Of course,all problems in the polynomial hierarchy are recursive and in fact very simple problems within the vast expanse of all recursive sets. So are there natural problems which are recursive and are not captured by the hierarchy?The answers is yes and results in the exploration of several important larger complexity classes which contain the polynomial hierarchy. One such class is PSPACE,those problems which can be solved using work space which is of polynomial length relative to the length of the problem’s input.Just as with P and NP,the full extent of PSPACE is not known. PSPACE contains P and NP.It is not known if either of these conclusions are proper.Settling these questions would again be significant steps forward in this theory.The notion of PSPACE-completeness is defined very similarly to NP-completeness,and has been studies alongside the the NP-completeness ly,a problem C is PSPACE-complete if it is in PSPACE and if any other PSPACE problem can be reduced to it in polynomial time.As is the case with NP-complete problems,PSPACE-complete problems are quite common and often arise quite naturally.Typical PSPACE-complete problems are or arise from generalized games such as hex or checkers played on boards of unboundedfinite size(see[GJ79]).Beyond PSPACE lie the exponential time(EXPTIME)and exponential space complexity classes.A small number of natural problems have been shown complete for these classes(see[GJ79]),and as well EXPTIME is the smallest deterministic class which has been proved to contain NP.4Structural ComplexityBy the early1970’s,the definitions of time and space-bounded complexity classes were precisely established and the import of the class NP and of NP-complete problems realized.At this point effort turned to understanding the relationships between complexity classes and the properties of problems within the principal classes.In particular,attention was focused on NP-complete problems and their properties and on the structure of complexity classes between LOGSPACE and PSPACE.We briefly survey some of these studies here.4.1The Isomorphism ConjectureIn the mid-70’s,building on earlier work on G¨o del numberings[HB75,Har82] and in analogy with the well-known result of Myhill from computability theory[Myh55],Berman and Hartmanis[BH77,HB78]formulated their iso-morphism conjecture.The conjecture stated that all NP-complete sets are P-isomorphic(that is,isomorphic via polynomial time computable and in-vertible isomorphisms).This conjecture served as a springboard for the further study of the structure of NP-complete sets.As evidence for their conjecture,Berman and Hartmanis and others[MY85,KMR87]were able to give simple,easily checkable properties of NP-complete sets which implied they were ing these,they proved that all of the known NP-complete sets were in fact P-isomorphic.This conjecture remains an open question today.A positive resolution of the conjecture would imply that P is not equal to NP.Much effort was focused on proving the converse,that assuming P is not NP then the isomorphism conjecture holds.This remains an open question today.As the number of known NP-complete problems grew during the1970’s, the structure and properties of these problems began to be examined.While very disparate,the NP-complete sets have certain common properties.For example,they are all rather dense sets.Density of a set is measured here simply in the sense of how many string of a given length are in the set.So (assuming a binary encoding of a set)there are2n different strings of length n.We say that set S is sparse if there is a polynomial p(n)which bounds the number of strings in S of length n,for every n.It is dense otherwise. All known NP-complete sets are dense.One consequence of the isomorphism conjecture is that no NP-complete set can be sparse.As with the isomorphism conjecture,this consequence im-plies that P is not NP and so it is unlikely that a proof of this consequence will soon be forthcoming.Berman and Hartmanis also conjectured that if P in not equal to NP there are no sparse NP-complete sets.This con-jecture was settled affirmatively by the famous result of Mahaney[Mah82]. Mahaney’s elegant proof used several new counting techniques and had alasting impact on work in structural complexity theory.4.2The Polynomial HierarchyWhile numerous hard decision problems have been proved NP-complete, a small number are outside NP and have escaped this classification.An extended classification,the polynomial time hierarchy(PH),was provided by Meyer and Stockmeyer[Sto76].They defined the hierarchy,a collection of classes between P and PSPACE,in analogy with Kleene’s arithmetic hierarchy.The polynomial time hierarchy(PH)consists of an infinite sequence of classes within PSPACE.The bottom(0th)level of the hierarchy is just the class P.Thefirst level is the class NP.The second level are all problems in NP relative to an NP oracle,etc.Iterating this idea to allfinite levels yields the full hierarchy.If P=PSPACE then the whole PH collapses to the class P.However, quite the opposite is believed to be the case,namely that the PH is strict in the sense that each level of the hierarchy is a proper subset of the next level.While every class in the PH is contained in PSPACE,the converse is not true if the hierarchy is strict.In this case,PSPACE contains many problems not in the PH and in fact has a very complex structure(see,for example,[AS89]).4.3AlternationAnother unifying and important thread of results which also originated dur-ing the1970’s was the work on alternation initiated out by Kozen,Chandra and Stockmeyer[CKS81].The idea behind alternation is to classify combi-natorial problems using an alternating Turing machine,a generalization of a nondeterministic Turing machine.Intuitively a nondeterministic Turing machine can be thought of as having an existential acceptance criterion. That is,an input to the TM is accepted if there exists a computation path of the machine which results in acceptance.Similarly,we could consider a universal acceptance criterion whereby a nondeterministic machine accepts of all computation paths lead to acceptance.Restricting ourselves to poly-nomial length alternation,we see that NP can be characterized as those problems accepted by nondeterministic TM running in polynomial time us-ing the existential acceptance criterion.Similarly,the universal acceptance criterion with the same type of machines defines the class co-NP consisting of problems whose complements are in NP.Furthermore,we can iteratethese two acceptance methods,for example asking that there exist an path of a TM such that for all paths extending that path there exists an exten-sion of that path which accepts.This idea gives a machine implementation of the notion of alternations of universal and existential quantifiers.It is not hard to see thatfinitely many alternations results in thefinite levels of the polynomial time hierarchy and that alternating polynomial time is the same thing as PSPACE.Other relationship between time and space classes defined using alternation can be found in[CKS81],for example,alternating log space=P and alternating PSPACE=EXPTIME.4.4LogspaceTo this point all the complexity classes we have considered contain the class P of polynomial time computable problems.For some interesting problems it is useful to consider classes within P and particularly the seemingly smaller space classes of deterministic log space,denoted L,and nondeterministic log space,denoted NL.These classes provide a measure with which to distin-guish between some interesting problems within P,and present interesting issues in their own right.Atfirst glance logarithmic space is a problematic notion at best.An input of length n takes n squares by itself,so how can a computation on such an input take only log n space?The answer lies in changing our computation model slightly to only count the space taken by the computation and not the space of the input.Formally,this is done by considering an“off-line Turing machine.”This is a(deterministic or nondeterministic)Turing machine whose input is written on a special read-only input putation is carried out on read-write work tapes which are initially blank.The space complexity of the computation is then taken to be the amount of space used on the work tapes.So in particular this space can be less than n,the length of the input to the computation.We define logspace,L,to be the class of languages decided by deterministic Turing machines which use at most O(log n)tape squares.Similarly,NL is defined using nondeterministic Turing machines with the same space bound.It is straightforward to check that L⊆NL⊆P,and these three classes are thought to be distinct.There are a number of nontrivial problems solv-able in L(for example see[LZ77])as well as problems known to be in NL which are not believed to be in L(for example see[Sav73,Jon75]).Nu-merous problems in P are thought to lie outside of L or NL.For example, one such problem is the circuit value problem,the problem of determining the value of a Boolean circuit,given inputs to the circuit.The circuit valueproblem is one of many problems in P which is known to be P complete. These are problems in P which are proved to be complete with respect to log-space bounded reductions,reductions defined analogously to polyno-mial time bounded reduction in the previous section.Proving a P-complete problem is in L would imply that L=P.4.5OraclesOracle results play a unique role in complexity theory.They are meta-mathematical results delineating the limitations of proof techniques and indicating what results might be possible to achieve and which are likely beyond our current reach.Oracle results concern relativized computations. We say that a computation is carried out“relative to an oracle set O”if the computation has access to the answers to membership queries of O.That is, the computation can query the oracle O about whether or not a string x is in O.The computation obtains the answer(in one step)and proceeds with the computation,which may depend on the answer to the oracle query.Thefirst,and still most fundamental oracle results in complexity were carried out by Baker,Gill and Solovay[BGS75].They proved that there is an oracle reactive to which P=NP and another oracle relative to which P and NP differ.What do these results say about the P vs NP question?They say little about the actual answer to this question.The existence of an oracle making a statement S true is simply a kind of consistency result about S.It says that the statement is true in one particular model or“world”(that is,the oracle set itself).As such,we can conclude that a proof of the negation of S will not itself relativize to any oracle.Thus,as many proof methods do relativize to every oracle,an oracle result provides a limitation to the possible methods used to prove S and hence are evidence that the result is,in this sense,hard.Oracle results have been most useful in delineating theorems which are difficult to prove(i.e.,those which do no relativize),from those which might more likely be settled by well-understood,relativizing proof techniques.In particular,the Baker,Gill and Solovay results concerning P and NP question indicate that a proof will be difficult to come by,as has indeed been the case.Since1978numerous other oracle results have been proved.Techniques used to achieve these results have become quite sophisticated and strong.For instance,Fenner,Fortnow and Kurtz[FFK94]gave a relativized world where the isomorphism conjecture holds where Kurtz,Mahaney and Royer[KMR89] had showed that it fails relative to most oracles.They were the culminationof a long series of partial results addressing this question.There are a few results in complexity that do not relativize,mostly relating to interactive proof systems(see Section6.1)but these tend to be the exception and not the rule.5Counting ClassesAnother way to study NP computations is to ask how many computations paths in the computation lead to acceptance.For example,consider the sat-isfiability problem.Given an instance of this problem,that is a propositional formula,instead of asking if the formula has a solution(a truth assignment making the formula true),ask how many such assignments there are.In 1979,Valiant[Val79]defined the complexity class#P as the class of func-tions computing the number of accepting paths of a nondeterministic Turing machine.Every#P function is computable in polynomial space.Valiant used this class to capture the complexity of the counting version of satisfia-bility as well as other interesting problems such as computing the permanent function.Counting complexity has since played an important role in computa-tional complexity theory and theoretical computer science.The techniques used in counting complexity have significant applications in circuit com-plexity and in the series of recent results on interactive proof systems.(See the next section.)The two most important counting function classes are #P,described above,and GapP.GapP consists of the class of functions which compute the difference between the number of accepting paths and the number of rejecting paths of a nondeterministic Turing machine.For example,the function which tells,for any propositional formula,computes the difference of the number of accepting and rejecting truth assignments is in the class GapP.Perhaps the two most important recent results in counting complexity are Toda’s theorem[Tod91]and the closure theorem of Beigel,Reingold and Spielman’s[BRS95].Toda’s theorem asserts that one can reduce any lan-guage in the polynomial-time hierarchy to a polynomial time computation which uses a#P function as an oracle.Hence,that in terms of complexity, hard functions in#P lie above any problem in the polynomial time hier-archy.In1994,Beigel,Reingold and Spielman[BRS95]proved that PP is closed under union.This result solved a longstanding open problem in this area,first posed by Gill in1977[Gil77]in the initial paper on probabilistic classes.It implies that PP is also closed under intersection Those interested。

BrochureMore information from /reports/2178437/Introduction to Abstract Algebra. Solutions Manual. 4th EditionDescription:Praise for the Third Edition". . . an expository masterpiece of the highest didactic value that has gained additional attractivity throughthe various improvements . . ." Zentralblatt MATHThe Fourth Edition of Introduction to Abstract Algebra continues to provide an accessible approach to thebasic structures of abstract algebra: groups, rings, and fields. The book's unique presentation helps readersadvance to abstract theory by presenting concrete examples of induction, number theory, integers modulon, and permutations before the abstract structures are defined. Readers can immediately begin to performcomputations using abstract concepts that are developed in greater detail later in the text.The Fourth Edition features important concepts as well as specialized topics, including:The treatment of nilpotent groups, including the Frattini and Fitting subgroupsSymmetric polynomialsThe proof of the fundamental theorem of algebra using symmetric polynomialsThe proof of Wedderburn's theorem on finite division ringsThe proof of the Wedderburn–Artin theoremThroughout the book, worked examples and real–world problems illustrate concepts and their applications,facilitating a complete understanding for readers regardless of their background in mathematics. A wealthof computational and theoretical exercises, ranging from basic to complex, allows readers to test theircomprehension of the material. In addition, detailed historical notes and biographies of mathematiciansprovide context for and illuminate the discussion of key topics. A solutions manual is also available forreaders who would like access to partial solutions to the book's exercises.Introduction to Abstract Algebra, Fourth Edition is an excellent book for courses on the topic at theupper–undergraduate and beginning–graduate levels. The book also serves as a valuable reference andself–study tool for practitioners in the fields of engineering, computer science, and applied mathematics.Contents:0 Preliminaries 10.1 Proofs 10.2 Sets 20.3 Mappings 30.4 Equivalences 41 Integers and Permutations 61.1 Induction 61.2 Divisors and Prime Factorization 81.3 Integers Modulo 111.4 Permutations 132 Groups 172.1 Binary Operations 172.2 Groups 192.3 Subgroups 212.4 Cyclic Groups and the Order of an Element 24 2.5 Homomorphisms and Isomorphisms 282.6 Cosets and Lagrange's Theorem 302.7 Groups of Motions and Symmetries 322.8 Normal Subgroups 342.9 Factor Groups 362.10 The Isomorphism Theorem 382.11 An Application to Binary Linear Codes 433 Rings 473.1 Examples and Basic Properties 473.2 Integral Domains and Fields 523.3 Ideals and Factor Rings 553.4 Homomorphisms 593.5 Ordered Integral Domains 624 Polynomials 644.1 Polynomials 644.2 Factorization of Polynomials over a Field 67 4.3 Factor Rings of Polynomials over a Field 70 4.4 Partial Fractions 764.5 Symmetric Polynomials 765 Factorization in Integral Domains 815.1 Irreducibles and Unique Factorization 815.2 Principal Ideal Domains 846 Fields 886.1 Vector Spaces 886.2 Algebraic Extensions 906.3 Splitting Fields 946.4 Finite Fields 966.5 Geometric Constructions 986.7 An Application to Cyclic and BCH Codes 997 Modules over Principal Ideal Domains 1027.1 Modules 1027.2 Modules over a Principal Ideal Domain 1058 p–Groups and the Sylow Theorems 1088.1 Products and Factors 1088.2 Cauchy s Theorem 1118.3 Group Actions 1148.4 The Sylow Theorems 1168.5 Semidirect Products 1188.6 An Application to Combinatorics 1199 Series of Subgroups 1229.1 The Jordan–H¨older Theorem 1229.2 Solvable Groups 1249.3 Nilpotent Groups 12710 Galois Theory 13010.1 Galois Groups and Separability 13010.2 The Main Theorem of Galois Theory 13410.3 Insolvability of Polynomials 13810.4 Cyclotomic Polynomials and Wedderburn's Theorem 14011 Finiteness Conditions for Rings and Modules 14211.1 Wedderburn's Theorem 14211.2 The Wedderburn–Artin Theorem 143Appendices 147Appendix A: Complex Numbers 147Appendix B: Matrix Arithmetic 148Appendix C: Zorn's Lemma 149Ordering:Order Online - /reports/2178437/ Order by Fax - using the form belowOrder by Post - print the order form below and send to Research and Markets,Guinness Centre,Taylors Lane,Dublin 8,Ireland.Fax Order FormTo place an order via fax simply print this form, fill in the information below and fax the completed form to 646-607-1907 (from USA) or +353-1-481-1716 (from Rest of World). If you have any questions please visit/contact/Order Information Please verify that the product information is correct.Product Format Please select the product format and quantity you require:* Shipping/Handling is only charged once per order.* The price quoted above is only valid for 30 days. Please submit your order within that time frame to avail of this price as all prices are subject to change. Contact InformationPlease enter all the information below in BLOCK CAPITALSProduct Name:Introduction to Abstract Algebra. Solutions Manual. 4th Edition Web Address:/reports/2178437/Office Code:SCBRAUDB QuantityHard Copy(Paper back):USD 93 + USD 27 Shipping/Handling Title:MrMrsDrMissMsProf First Name:Last Name:Email Address: *Job Title:Organisation:Address:City:Postal / Zip Code:Country:Phone Number:Fax Number:* Please refrain from using free email accounts when ordering (e.g. Yahoo, Hotmail, AOL)Payment InformationPlease indicate the payment method you would like to use by selecting the appropriate box.Please fax this form to:(646) 607-1907 or (646) 964-6609 - From USA+353-1-481-1716 or +353-1-653-1571 - From Rest of World Pay by credit card:You will receive an email with a link to a secure webpage to enter yourcredit card details.Pay by check:Please post the check, accompanied by this form, to:Research and Markets,Guinness Center,Taylors Lane,Dublin 8,Ireland.Pay by wire transfer:Please transfer funds to:Account number833 130 83Sort code98-53-30Swift codeULSBIE2D IBAN numberIE78ULSB98533083313083Bank Address Ulster Bank,27-35 Main Street,Blackrock,Co. Dublin,Ireland.If you have a Marketing Code please enter it below:Marketing Code:Please note that by ordering from Research and Markets you are agreeing to our Terms and Conditions at /info/terms.asp。