A Synthesis of Constraint Satisfaction and Constraint Solving

Classroom Assignment using Constraint Logic ProgrammingSlim Abdennadher,Matthias Saft and Sebastian WillComputer Science Department,University of MunichOettingenstr.67,80538Munich,Germanyabdennad,saft,wills@informatik.uni-muenchen.deAbstractThe Classroom Assignment problem consists of scheduling a set of courses into afixed number of rooms,given afixed timetable.At the University of Munich,a classroom planhas to be created each semester after collecting timetables of all departments and wishesof teachers.This planning is very complex since a lot of constraints have to be met,e.g.room size and ing constraint-based programming,we developed a prototype,called RoomPlan,that supports automatic creation of classroom plans.With RoomPlan aschedule can be created interactively within some minutes instead of some days.RoomPlanwas presented at the Systems’99Computer exhibition in Munich.1IntroductionUniversity course timetabling problems are combinatorial problems which consist in scheduling a set of courses within a given number of rooms and time periods.In most universities,the university course timetabling problem is solved in two phases.In thefirst phase timetables have to be created,one for each department.Since departments can share rooms,the availability of rooms is not taken into account in thefirst phase.In the second phase,rooms have to be assigned to courses.The assignment of rooms is done centrally for the whole university.The classroom assignment problem is a difficult and time-consuming expert task since a lot of requirements have to be met.For example,courses must be assigned to rooms based on the number of students taking the courses and capacities of rooms.Furthermore,some courses may require special equipments such as beamer or internet access.While for thefirst phase of the university course timetabling several systems have been developed[4,12,7],to our knowledge mainly theoretical work has been done on the topic of the classroom assignment problem[6,5].Recently,Constraint Logic Programming[14,20,11,18](CLP)has become a promising approach for solving scheduling problems.CLP combines the advantages of logic programming and constraint solving techniques.The use of CLP has the advantage that the solving procedure can easily be adapted to changing scheduling characteristics.The classroom assignment prob-lem can be elegantly formalized as a partial constraint satisfaction problem and implemented by means of specialized constraint solving techniques that are available in CLP languages.In this paper,the generation of classroom plans for universities is tackled using the CLP framework.The system is called RoomPlan and is currently tested at the University of Munich.Our prototype brought down the time necessary for creating a classroom plan from a few days by hand to a few minutes on a computer.Usually not all specified requirements can be fulfilled.We distinguish two kinds of con-straints.Hard constraints are conditions that must be satisfied,soft constraints may be violated, but should be satisfied as far as possible.The classical approach to deal with these requirements is based on a variant of branch-and-bound search.This approach starts with a solution and re-quires the next solution to be better.Quality is measured by a suitable cost function.The cost function depends on the set of satisfied soft ually,the computation of the cost function is incorporated into the labeling process.In this paper,we propose another approach computing the cost function during the constraint solving process independent of the labeling procedure.This requires to modify the constraint solving part.In the beginning,constraint solving was“hard-wired”in a built-in constraint solver written in a low-level language,termed the“black-box”approach.Since this approach makes it hard to modify a solver or build a solver over a new domain,our aim was to implement a solver for our problem using the“glass-box”approach Constraint Handling Rules(CHR)[9,10].CHR is a powerful special-purpose declarative programming language for writing application-oriented constraint solvers.For our need,we extended an existingfinite domain solver written in CHR[11]in a way that the cost for a solution is computed during the propagation of soft constraints.CHR allows to express the calculation of the cost in a very declarative and straightforward manner.In this paper,we describe the main features of the constraint solver that was used to generate a classroom plan for the University of Munich.Section2introduces our classroom assignment problem and the constraints that a solution of the problem had to satisfy.Section3shows how the problem can be modelled as a partial constraint satisfaction problem.Section4gives an overview of the implementation.Section5describes the user interface.Finally,we conclude with a summary.2Problem DescriptionIn universities,where each department is responsible for its own timetable and where rooms can be shared by different departments,timetables are usually generated in two phases.In thefirst phase an assignment of courses within a given number of periods is done without taking into account the availability of rooms.This task has to be performed separately for each department.For the Computer Science Department at the University of Munich,thefirst phase is solved automatically by a system that generates a new timetable based on a timetable of the previous year[2,3].For other departments the generation of timetables is still done by hand.In the second phase an assignment of courses within a given number of rooms has to be performed.After collecting timetables of all departments and wishes of teachers a classroom plan is generated centrally.In the following,we want to investigate the classroom assignment problem of the University of Munich.Since timetables for departments change every semester,a new classroom plan has to be created each semester.The University of Munich dispose of different buildings.Thebiggest building consists of40rooms where about1000courses have to be held.The generation of a classroom plan is a difficult and time-consuming task since different kinds of constraints have to be taken into account:The no-occupation overlap constraint tells that occupation time of a room by courses must not overlap.The seat requirement constraint tells how many seats a course requires.The teacher’s wishes:We distinguish three kinds of wishes.–A room constraint binds a course date to a room.–A building constraint assigns a course date to a certain building.–An equipment constraint constrains a course date to be assigned to a room withcertain technical equipment,e.g.beamer or video.Usually not all specified requirements can be fulfilled since the number of(special)rooms is obviously limited.Therefore we distinguish two kinds of constraints.Hard constraints must always be satisfied,soft constraints may be violated.Roughly speaking,no-occupation overlap constraints and seat requirement constraints determine hard constraints,wishes may be hard or soft constraints.3A Constraint Model for Classroom AssignmentA constraint satisfaction problem(CSP)[16]is a pair,where isfinite set of variables, each associated with afinite domain,and is afinite set of constraints on these variables.A solution of a CSP maps each variable to a value of its domain such that all the constraints are satisfied.Since we have to address quality of a room plan and therefore,have to take into account wishes as well as exploitation of resources,CSP can not model our problem completely. Therefore,we use an extension of the CSP concept.A partial constraint satisfaction problem PCSP[8]is a triple,where is a CSP and is a total function, i.e.,maps constraints to weights.The weight of a constraint expresses its importance.Thus, one can describe hard constraints,which must be satisfied,as well as soft constraints,which should be satisfied.A hard constraint is given an infinite weight.Then,a solution of the PCSP is an assignment of the variables in to their domains,such that the total weight of all violated constraints is minimized.Now,the classroom assignment problem is modeled as a PCSP.Note,that it does not suffice to assign a room to each course,but instead we have to assign a room to each date,where a course is held.Therefore,we use one variable for each course date.For example,if a course consists of two lectures,the course is represented by two different course date variables.The initial domain of each course date variable is the set of all rooms in the university.Thus,the solution is an assignment of course dates to rooms.There are two constraints that occur only as hard constraints and thus have infinite weight: the no-occupation overlap constraint and the seat requirement constraint.Wishes may also be hard,i.e.have infinite weight.To ensure a good exploitation of resources by a solution,we evaluate assignments of a room to a course date.For this reason,we modify the weight for the constraint,that assigns a course date for a course to a room.This is done by adding a term to the user-defined evaluation,thus defining in the following way.seats requirement seatequipment(1) where seats is the number of seats in room,requirement seat is the number of seats required by course,equipment is a valuation of the technical equipment in and requirement equipment a value for the technical requirements of.and are negative constants weighting the exploitation of seats and equipment resources against each other and the violation of wishes. Since the equipment constraint can be soft,the value of the technical requirements can be greater than the value of the equipment.In this case,we have to avoid that the third term of the function is positive.4Solving the Problem using Constraint Handling RulesIn a PCSP,one has additionally to satisfying all hard constraints to take soft constraints into account.According to the PCSP model,we have to minimize the total weight of violated soft constraints.This is equivalent to maximize the total weight of satisfied constraints.We use a branch-and-bound approach to tackle this maximization problem.Branch-and-bound is a standard method to optimize a score that works by constraining the score during the search. Every time an assignment satisfying the hard constraints is found,the score is bound to be even better.Thus,the last assignment compatible to the hard constraints that is found will have an optimal score.Therefore,we incrementally compute a bound of the score,that an assignment compatible to the current hard constraints may have,during the enumeration.This way we prune the search tree every time the maximally achievable score is worse than the score of the previous solution.To prune the search tree efficiently in our branch-and-bound algorithm,we have to keep track of the upper bound of the score.The upper bound of the score may be affected each time the constraint store changes.This change may be done either by a constraint which is directly inserted by the labeling process or by constraint propagation.If only changes of thefirst kind could affect the upper bound,the calculation of the score could be easily incorporated into the labeling process.However,since we also have to take care of the second kind of constraint store changes,it is much more natural and intuitive to do this calculation concurrently to the labeling process and triggered by the alteration of the constraint store.Constraint Handling Rules(CHR) allows to express this in a very declarative and straightforward manner,where the calculation is formulated independently of the labeling.In the following,CHR is briefly introduced.Then,the core of the constraint solver,which performs hard and soft constraint propagation,is presented.Finally,a labeling strategy tofind good solutions is described.4.1Constraint Handling RulesCHR is a declarative high-level language extension especially designed for writing constraint solvers.With CHR,one can introduce user-defined constraints into a given host language.The main implementations of CHR are currently available in Prolog:Besides the library from1994, ECL PS 4.0now includes a new experimental prototype of CHR.An advanced optimizing CHR compiler was released for Sicstus3.7in1998[13].CHR has also been implemented in Common Lisp,OZ and Java.To implement the constraint solver for our classroom assignment problem we used the CHR library of Sicstus.Thus,code examples follow the syntax of CHR and Prolog.CHR is essentially a committed-choice language consisting of multi-headed guarded rules that rewrite constraints into simpler ones until they are solved.There are basically two kinds of CHR rules:Simplification rules replace constraints by simpler constraints while preserving log-ical equivalence.Propagation rules add new constraints which are logically redundant but may cause further simplification.Repeatedly applying the rules incrementally solves constraints. With multiple heads and propagation rules,CHR provides two features which are essential for non-trivial constraint handling.Due to space limitations,we cannot give a formal account of syntax and semantics of CHR in this paper.An overview on CHR can be found in[10].Detailed semantics results for CHR are available in[1].We introduce CHR by example.Let=<and=be built-in constraint symbols. We implement a user-defined constraint for max,where max(X,Y,Z)means that Z is the maximum of X and Y:max(X,Y,Z)<=>X=<YZ=X.max(X,Y,Z)==>X=<Z,Y=<Z.Thefirst rule states that max(X,Y,Z)is logically equivalent to Z=Y,provided it is the case that X=<Y.This test forms the guard of a rule,a precondition of the applicability of the rule. Hence,whenever we see the constraint max(X,Y,Z)in any goal where it holds that X=<Y we can simplify it to Z=Y.Analogously for the second rule.Thefirst and second rules are simplification rules.The third rule propagates constraints.It states that max(X,Y,Z)unconditionally implies X=<Z,Y=<Z.Operationally,we add these logical consequences as redundant constraints,the max constraint is kept.This kind of rule is called propagation rule.To the goal max(1,2,M)thefirst rule is applicable:max(1,2,M)will be simplified to M=2.Redundancy from the propagation rule is useful,as the goal max(A,3,3)shows:To this goal only the propagation rule is applicable,but then thefirst rule:max(A,3,3)cause thepropagation rule tofire and adds A=<3,3=3to the goal.Now,thefirst rule is applicable and simplifies the constraint max(A,3,3)to3=3.The constraint33is simplified to true by the built-in constraint solver.The constraint solver for max solved max(A,3,3)and produced the answer A=<3.4.2The Core of the Constraint Solver4.2.1Handling Hard ConstraintsRegarding just the hard constraints,our solver is essentially afinite domain solver,i.e.a course date variable is bound to a list of rooms and constraints may eliminate rooms from the domain list of the constrained variable.Constraint solving forfinite domains constraints is based on consistency techniques[17,15]. For example,the constraints X::[2,3,4]and X::[3,4,5]may be replaced by the new constraint X::[3,4](The constraint X::[2,3,4]means that X has to take a value from the list[2,3,4]).Implementing this technique with CHR is straightforward[11].Thefirst rule ensures that the domain for X is non-empty,the second rule intersects two domains for the same variable:X::[]<=>false.X::L1,X::L2<=>intersection(L1,L2,L),X::L.To solve our classroom assignment problem,the no-occupation overlap constraint can be expressed using the global constraint all distinct(Xs) tells that all variables in the list Xs must be bound to different values.The no-occupation overlap constraint is propagated to constraints allbuilding or equipment.CourseDate holds a course date identifier,the variable Wished further specifies the instance of the wish and Weight holds the weight of the wish.We use further the constraint assignment(CDate,CDateVar)which tells that CDateVar is the course date variable corresponding to the course date CDate.The constraint scoreWish(Up) tells that Up is the upper bound of the sub-score ScoreWish.In the following,we introduce simplification rules to update the sub-score ScoreWish, whenever a wish is satisfied or violated.In the following,we will discuss the rules for handling room constraints.The rules handling building and equipment constraints are analogous. assignment(CDate,CDateVar),CDateVar::Dom,wish(room,CDate,RoomWish,infinite)<=>assignment(CDate,CDateVar),CDateVar::Dom,CDateVar::[RoomWish].assignment(CDate,CDateVar),CDateVar::[RoomWish],wish(room,CDate,RoomWish,Weight)<=>Weight\==infinite|assignment(CDate,CDateVar),CDateVar::[RoomWish]. assignment(CDate,CDateVar),CDateVar::Dom,wish(room,CDate,RoomWish,Weight),scoreWish(Up)<=>Weight\==infinite,\+member(RoomWish,Dom)| assignment(CDate,CDateVar),CDateVar::Dom,scoreWish(Up-Weight).Thefirst rule propagates a hard wish,i.e.a wish with infinite weight,in such a way that an assignment of the course date variable to the wished room is performed.Therefore,the sim-plification rule tests whether constraints of the form assignment(CDate,CDateVar), CDateVar::Dom and wish(room,CDate,RoomWish,infinite)can be found in the constraint store.In this case,the rulefires and the constraint CDateVar::[RoomWish], that binds the room to the wished room,is added to the store.Furthermore,the wish constraint is removed from the constraint store.The application of this rule leads to the occurrence of two domains for the same variable.These constraints can be simplified by the intersection rule presented above.The second rule handles already satisfied soft constraints.If the constraints assign-ment(CDate,CDateVar),CDateVar::[RoomWish]and wish(room,CDate, RoomWish,Weight)are found in the constraint store,then the wish is obviously satisfied and the rule consequently removes the wish.The guard ensures that only soft constraints,i.e. wishes withfinite weight,are handled by this rule,since hard wish constraints are already han-dled by thefirst rule.Note that the upper bound of the score is unaffected if a wish is satisfied. In contrast,if a wish is violated,the upper bound of the score has to be decreased.The updating of the bound is done by the third rule.The guard ensures that only soft constraints which are violated lead to a change of the score.A room constraint is violatedif the wished room is not contained in the domain of the course date variable.If the rule fires,the upper bound is recomputed as Up-Weight and the constraint scoreWish(Up -Weight)replaces the constraint scoreWish(Up).The evaluation of resource exploitation is handled by a single rule.assignment(CDate,CDateVar),CDateVar::[RoomNr],scoreSeatsRes(UpS),scoreEquipmentRes(UpT)<=>assignment(CDate,CDateVar),CDateVar::[RoomNr],scoreSeatsRes_diff(CDate,RoomNr,SSD),scoreEquipmentRes_diff(CDate,RoomNr,TSD),scoreSeatsRes(UpS+SSD),scoreEquipmentRes(UpT+TSD).The rule updates the scores for seat resource and equipment resource exploitation,where the actual weight is calculated by the separate predicates scoreSeatsResdiff analogously to equation(1).The updating of the sub-scores is done by replacing the constraints scoreSeatsRes(UpS)and scoreEquipmentRes(UpT) by the recomputed constraints scoreSeatsRes(UpS+SSD)and scoreEquipmen-tRes(UpT+TSD)each time an assignment of a course date variable to a room was newly created,either by labeling or by constraint propagation.Each time a sub-score is recomputed,the total score has to be recalculated.This can be done by the following propagation rule.scoreWish(UpW),scoreSeatsRes(UpS),scoreEquipmentRes(UpT)==>score(UpC+UpS+UpT).The rulefires if a sub-score changes.Then,a constraint with the newly calculated upper bound of the total score is inserted.A further rule ensures that only the most restrictive score con-straint remains in the constraint store.score(A),score(B)<=>A=<B|score(A).This rule removes the larger of two upper bounds of the total score.Now,the upper bound can be used to prune the search tree,since we use a branch-and-bound algorithm.Every time an assignment of the course date variables that satisfies the hard constraints is found,we insert a constraint last4.3LabelingAfter stating the problem constraints,normally there are still many feasible solutions,so it is necessary to label the domain variables,i.e.assign them with values that remain on their domains.For the labeling one needs to apply a heuristic strategy that tends to enumerate high scoring solutions early in the search.In a branch-and-bound search this helps to prune the search tree.In practice also suboptimal solutions may be appropriate,which also emphasizes the use offinding good solutions early.We employed a leftmost variable,leftmost value strategy that selects for each assignment the leftmost course date variable and the leftmost value from the domain of the selected course date variable.Since we sort the list of variables as well as the values in the domains before the labeling as we describe below,this strategy prefers most constrained assignments.The sorting is done in the following way.We compute a weight for each course and a weight for each room with respect to a certain course,i.e.actually a weight for a certain assignment.The weights for courses respect seat and equipment requirements,such that courses with strong requirements get great weights.The weight of an assignment totals the weights of the soft constraints which are satisfied by the actual assignment.Then,the course date variables and the rooms in each domain are sorted in descending order by these weights.As a consequence the leftmost course date variables,which are selectedfirst by our strategy,belong to the courses with the strongest requirements.Further,the leftmost values in each domain lead to assignments,which satisfy the”best”soft constraints.5User InterfaceFor a classroom assignment system to be complete,aflexible user interface should be provided, so that the specific requirements of the problem can be stated easily.RoomPlan provides such an interface.The RoomPlan user interface was written in JAVA TM1.1using the Abstract Window Toolkit (AWT).It generates the data needed by the CHR solver in form of prolog facts and starts the CHR solver.Figure1shows the input form for the courses that have to be planned.The user has to type in the courses with title,first and last day and start-and endtime.Furthermore,the interface allows the user to define the system parameters as preferred.All parameters like the needed amount of seats and needed equipment,e.g.overhead projector are handled as soft constraints. In addition,the user can specify a wish for a special room.These wishes are given in four cat-egories:imperative,strong preferred,preferred and weakly preferred. Imperative wishes are hard constraints.If there is no wish for a special room,a building can be specified,which is considered by the classroom assignment.It may happen that there exists not even one classroom plan that complies with all the given hard constraints.Then the problem is called over-constrained.In case of a direct clash in form of two conflicting imperative room wishes,RoomPlan may detect this and then gives the user a variety of alternative rooms which satisfy the specified equipment wishes.Figure1:Classroom AssignmentFigure2shows a fragment of the generated classroom plan.In addition,the user can manu-ally alter a completely generated classroom plan and let it check by RoomPlan.An advantage of the interactive system is that the expert might assist the program to produce even better results.6ConclusionIn this paper,we have argued that Constraint Handling Rules(CHR)is a good vehicle for implementing a PCSP solver.We extended an existingfinite domain solver to deal with soft constraints.The idea was to compute the cost function during the propagation of constraints. This is much more natural and intuitive than the incorporation of the computation into the labeling process.Thus our approach is comparable in terms of declarativity to approaches embedding cost functions into a CLP(FD)system using reification.The solver is powerful enough to serve as the core of a classroom assignment system.Our system,RoomPlan,has been implemented using Sicstus Prolog.The CLP code is justabout700lines.RoomPlan assists a human planner in scheduling courses to rooms.Room-Plan was presented at the Systems’99Computer exhibition in Munich.It is currently tested at the University of Munich.Typically,for1000courses and40rooms,RoomPlan generates a satisfying schedule within a few minutes.Figure2:Fragment of a Classroom PlanRoomPlan has been designed to meet the specific requirements of the University of Munich. However,it can be applied to other universities,since the classroom assignment problem is already handled in a general way.However,if necessary,adaption can easily be done due to the the declarativity of constraint logic programming.In general problems a labeling strategy with previouslyfixed enumeration order is not suit-able,since a good order of variables or domain values often cannot befixed in advance.Only thespecial nature of our classroom assignment problem makes this strategy a suitable choice.Nev-ertheless,we are currently developing intelligent labeling strategies as quoted by Tsang[19]. AcknowledgementsWe would like to thank Thom Fr¨u hwirth and the anonymous referees for useful comments on a preliminary version of this paper.References[1]S.Abdennadher.Operational semantics and confluence of constraint propagation rules.InThird International Conference on Principles and Practice of Constraint Programming, CP’97,LNCS1330.Springer-Verlag,1997.[2]S.Abdennadher and M.Marte.University timetabling using constraint handling rules.InActes des Journ´e es Francophones de Programmation en Logique et Programmation par Contraintes,1998.[3]S.Abdennadher and M.Marte.University course timetabling using constraint handlingrules.Journal of Applied Artificial Intelligence,Special Issue on Constraint Handling Rules,to appear2000.[4]F.Azevedo and P.Barahona.Timetabling in constraint logic programming.In Proceedingsof2nd World Congress on Expert Systems,1994.[5]M.Carter and C.Tovey.When is the classroom assignment problem hard?OperationsResearch,40(1):28–39,1989.[6]J.Ferland and S.Roy.Timetabling problem for university as assignment of activity toputers and Operational Research,12(2):207–218,1985.[7]H.Frangouli,V.Harmandas,and P.Stamatopoulos.UTSE:Construction of optimumtimetables for university courses—A CLP based approach.In Proceedings of the Third International Conference on the Practical Applications of Prolog,pages225–243,1995.[8]E.C.Freuder and R.J.Wallace.Partial constraint satisfaction.Artificial Intelligence,58(1-3):21–70,December1992.[9]T.Fr¨u hwirth.Constraint handling rules.In A.Podelski,editor,Constraint Programming:Basics and Trends,LNCS910.Springer-Verlag,1995.[10]T.Fr¨u hwirth.Theory and practice of constraint handling rules,special issue on constraintlogic programming.Journal of Logic Programming,pages95–138,October1998.[11]T.Fr¨u hwirth and S.Abdennadher.Constraint-Programmierung:Grundlagen und Anwen-dungen.Springer-Verlag,September1997.[12]M.Henz and J.W¨u ing Oz for college time tabling.In Proceedings of the FirstInternational Conference on the Practice and Theory of Automated Timetabling,pages 283–296,1995.[13]C.Holzbaur and T.Fr¨u hwirth.A prolog constraint handling rules compiler and runtimesystem.Journal of Applied Artificial Intelligence,Special Issue on Constraint Handling Rules,to appear2000.[14]J.Jaffar and M.J.Maher.Constraint logic programming:A survey.Journal of LogicProgramming,20,1994.[15]V.Kumar.Algorithms for constraint-satisfaction problems:A survey.AI Magazine,13(1),1992.[16]A.K.Mackworth.Consistency in networks of relations.Artificial Intelligence,8:99–118,1977.[17]A.K.Mackworth.Constraint satisfaction.In S.C.Shapiro,editor,Encyclopedia ofArtificial Intelligence.Wiley,1992.V olume1,second edition.[18]K.Marriott and P.Stuckey.Programming with Constraints:An Introduction.The MITPress,1998.[19]E.Tsang.Foundations of Constraint Satisfaction.Academic Press,1993.[20]M.Wallace.Practical applications of constraint programming.Constraints Journal,1(1,2),September1996.。

Optimization ToolboxlinprogSolve a linear programming problemEquationwhere f, x, b, beq, lb, and ub are vectors and A and Aeq are matrices.Syntaxx = linprog(f,A,b)x = linprog(f,A,b,Aeq,beq)x = linprog(f,A,b,Aeq,beq,lb,ub)x = linprog(f,A,b,Aeq,beq,lb,ub,x0)x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval] = linprog(...)[x,lambda,exitflag] = linprog(...)[x,lambda,exitflag,output] = linprog(...)[x,fval,exitflag,output,lambda] = linprog(...)Descriptionlinprog solves linear programming problems.x = linprog(f,A,b) solves min f'*x such that A*x <= b.x = linprog(f,A,b,Aeq,beq) solves the problem above while additionally satisfying the equality constraints Aeq*x = beq. Set A=[] and b=[] if no inequalities exist.x = linprog(f,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that the solution is always in the range lb <= x <= ub. Set Aeq=[] and beq=[] if no equalities exist.x = linprog(f,A,b,Aeq,beq,lb,ub,x0) sets the starting point to x0. This option is only available with the medium-scale algorithm (the LargeScale option is set to 'off' using optimset). The default large-scale algorithm and the simplex algorithm ignore any starting point.x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) minimizes with the optimization options specified in the structure options. Use optimset to set these options.[x,fval] = linprog(...) returns the value of the objective function f un at the solution x: fval =f'*x.[x,lambda,exitflag] = linprog(...) returns a value exitflag that describes the exit condition.[x,lambda,exitflag,output] = linprog(...) returns a structure output that contains information about the optimization.[x,fval,exitflag,output,lambda] = linprog(...) returns a structure lambda whose fields contain the Lagrange multipliers at the solution x.Input ArgumentsFunction Arguments contains general descriptions of arguments passed in to linprog. Options provides the function-specific details for the options values.Output ArgumentsFunction Arguments contains general descriptions of arguments returned by linprog. This section provides function-specific details for exitflag, lambda, and output:exitflag Integer identifying the reason the algorithm terminated. Thefollowing lists the values of exitflag and the correspondingreasons the algorithm terminated.1Function converged to a solution x.0Number of iterations exceededoptions.MaxIter.-2No feasible point was found.-3Problem is unbounded.-4NaN value was encountered duringexecution of the algorithm.-5Both primal and dual problems areinfeasible.-7Search direction became too small. Nofurther progress could be made.lambda Structure containing the Lagrange multipliers at the solution x(separated by constraint type). The fields of the structure are:lower Lower bounds lbupper Upper bounds ubineqlin Linear inequalitieseqlin Linear equalitiesoutput Structure containing information about the optimization. Thefields of the structure are:algorithm Algorithm usedcgiterations The number of conjugate gradient iterations(large-scale algorithm only).iterations Number of iterationsmessage Exit messageOptionsOptimization options used by linprog. Some options apply to all algorithms, and others are only relevant when using the large-scale algorithm.You can use optimset to set or change the values of these fields in the options structure, options. See Optimization Options for detailed information.LargeScale Use large-scale algorithm when set to 'on'. Usemedium-scale algorithm when set to 'off'.Medium-Scale and Large-Scale AlgorithmsThese options are used by both the medium-scale and large-scale algorithms: Diagnostics Print diagnostic information about the function to be minimized.Display Level of display. 'off''iter' displays'final' (default) displays just thefinal output. At this time, the 'iter' level only works with thelarge-scale algorithm.MaxIter Maximum number of iterations allowed.Medium-Scale Algorithm OnlyThese options are used by the medium-scale algorithm:Simplex If 'on', linprog uses the simplex algorithm. The simplexalgorithm uses a built-in starting point, ignoring the startingpoint x0 if supplied. The default is 'off'. See SimplexAlgorithm for more information and an example.Large-Scale Algorithm OnlyThese options are used only by the large-scale algorithm:TolFun Termination tolerance on the functionvalue.ExamplesFind x that minimizessubject toFirst, enter the coefficientsA = [1 -1 13 2 4Next, call a linear programming routine.Entering x, lambda.ineqlin, and lambda.lower getsx =0.000015.00003.0000lambda.ineqlin =1.50000.5000lambda.lower =1.0000Nonzero elements of the vectors in the fields of lambda indicate active constraints at the solution. In this case, the second and third inequality constraints (inlambda.ineqlin) and the first lower bound constraint (in lambda.lower) are active constraints (i.e., the solution is on their constraint boundaries).AlgorithmLarge-Scale OptimizationThe large-scale method is based on LIPSOL (Linear Interior Point Solver, [3]), which is a variant of Mehrotra's predictor-corrector algorithm ([2]), a primal-dual interior-point method. A number of preprocessing steps occur before the algorithm begins to iterate. See Large-Scale Linear Programming.Medium-Scale Optimizationlinprog uses a projection method as used in the quadprog algorithm. linprog is an active set method and is thus a variation of the well-known simplex method for linear programming [1]. The algorithm finds an initial feasible solution by first solving another linear programming problem.Alternatively, you can use the simplex algorithm, described in Simplex Algorithm, by enteringoptions = optimset('LargeScale', 'off', 'Simplex', 'on')and passing options as an input argument to linprog. The simplex algorithm returns a vertex optimal solution.DiagnosticsLarge-Scale OptimizationThe first stage of the algorithm might involve some preprocessing of the constraints (see Large-Scale Linear Programming). Several possible conditions might occur that cause linprog to exit with an infeasibility message. In each case, the exitflag argument returned by linprog is set to a negative value to indicate failure.If a row of all zeros is detected in Aeq but the corresponding element of beq is not zero,the exit message isExiting due to infeasibility: An all zero row in the constraint matrix does not have a zero in corresponding right-hand sizeentry.If one of the elements of x is found not to be bounded below, the exit message is Exiting due to infeasibility: Objective f'*x is unbounded below If one of the rows of Aeq has only one nonzero element, the associated value in x iscalled a singleton variable. In this case, the value of that component of x can becomputed from Aeq and beq. If the value computed violates another constraint, the exit message isExiting due to infeasibility: Singleton variables in equalityconstraints are not feasible.If the singleton variable can be solved for but the solution violates the upper or lower bounds, the exit message isExiting due to infeasibility: Singleton variables in the equality constraints are not within bounds.Once the preprocessing has finished, the iterative part of the algorithm begins until the stopping criteria are met. (See Large-Scale Linear Programming for more informationabout residuals, the primal problem, the dual problem, and the related stopping criteria.)If the residuals are growing instead of getting smaller, or the residuals are neithergrowing nor shrinking, one of the two following termination messages is displayed, respectively,One or more of the residuals, duality gap, or total relative erro has grown 100000 times greater than its minimum value so far:orOne or more of the residuals, duality gap, or total relative erro has stalled:After one of these messages is displayed, it is followed by one of the following sixmessages indicating that the dual, the primal, or both appear to be infeasible. The messages differ according to how the infeasibility or unboundedness was measured.The dual appears to be infeasible (and the primal unbounded).(The primal residual < TolFun.)The primal appears to be infeasible (and the dual unbounded). (Th dual residual < TolFun.)The dual appears to be infeasible (and the primal unbounded) sinc the dual residual > sqrt(TolFun).(The primal residual <10*TolFun.)The primal appears to be infeasible (and the dual unbounded) sinc the primal residual > sqrt(TolFun).(The dual residual <10*TolFun.)The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.Both the primal and the dual appear to be infeasible.Note that, for example, the primal (objective) can be unbounded and the primal residual, which is a measure of primal constraint satisfaction, can be small.Medium-Scale Optimizationlinprog gives a warning when the problem is infeasible.there is no feasible solution.In this case, linprog produces a result that minimizes the worst case constraintviolation.When the equality constraints are inconsistent, linprog givesWarning: The equality constraints are overlyUnbounded solutions result in the warningthe constraints are not restrictive enough.In this case, linprog returns a value of x that satisfies the constraints.LimitationsMedium-Scale OptimizationAt this time, the only levels of display, using the Display option in options, are'off' and 'final''iter' is not available.See AlsoquadprogReferences[1] Dantzig, G.B., A. Orden, and P. Wolfe, "Generalized Simplex Method for Minimizinga Linear from Under Linear Inequality Constraints," Pacific Journal Math., Vol. 5, pp. 183-195.[2] Mehrotra, S., "On the Implementation of a Primal-Dual Interior Point Method," SIAM Journal on Optimization, Vol. 2, pp. 575-601, 1992.[3] Zhang, Y., "Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment," Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.gangstr lsqcurvefit © 1994-2005 The MathWorks, Inc. Terms of Use Patents Trademarks。

Finite Model Theory and Its ApplicationsSpringer61Constraint Satisfactionthe data complexity of a fragment of existential second-order logic.We then go on in Section1.6and offer a logical approach,via definability in Datalog, to establishing the tractability of non-uniform constraint-satisfaction prob-lems.In Section1.7,we leverage the connection between Datalog and certain pebble games,and show how these pebble games offer an algorithmic ap-proach to solving uniform constraint-satisfaction problems.In Section1.8,we relate these pebble games to consistency properties of constraint-satisfaction instances,a well-known approach in constraint solving.Finally,in Section1.9, we show how the same pebble games can be used to identify large“islands of tractability”in the constraint-satisfaction terrain that are based on the concept of bounded treewidth.Much of the logical machinery used in this chapter is described in detail in Chapter??.For a book-length treatment of constraint satisfaction from the perspective of graph homomorphism,see[44].Two books on constraint programming and constraint processing are[3,23].1.2PreliminariesThe standard terminology in AI formalizes an instance P of constraint satis-faction as a triple(V,D,C),where1.V is a set of variables;2.D is a set of values,referred to as the domain;3.C is a collection of constraints C1,...,C q,where each constraint C i is apair(t,R)with t a k-tuple over V,k≥1,referred to as the scope of the constraint,and R a k-relation on D.A solution of such an instance is a mapping h:V→D such that,for each constraint(t,R)in C,we have that h(t)∈R,where h is defined on tuples component-wise,that is,if t=(a1,...,a k),then h(t)=(h(a1),...,h(a k)). The constraint-satisfaction problem asks whether a given instance is solvable,i.e.,whether it has a solution.Note that,without loss of generality, we may assume that all constraints(t,R i)involving the same scope t have been consolidated to a single constraint(t,R),where R is the intersection of all relations R i constraining t.Thus,we can assume that each tuple t of variables occurs at most once in the collection C.Consider the Boolean satisfiability problem3-Sat:given a3CNF-formula ϕwith variables x1,...,x n and clauses c1,...,c m,isϕsatisfiable?Such an instance of3-Sat can be thought of as the constraint-satisfaction instance in which the set of variables is V={x1,...,x n},the domain is D={0,1},and the constraints are determined by the clauses ofϕ.For example,a clause of the form(¬x∨¬y∨z)gives rise to the constraint((x,y,z),{0,1}3−{(1,1,0)}). In an analogous manner,3-Colorability can be modelled as a constraint-satisfaction problem.Indeed,an instance G=(V,E)of3-Colorability can be thought of as the constraint-satisfaction instance in which the set1.2Preliminaries7 of variables is the set V of the nodes of the graph G,the domain is the set D={r,b,g}of three colors,and the constraints are the pairs((u,v),Q), where(u,v)∈E and Q={(r,b)(b,r),(r,g)(g,r),(b,g)(g,b)}is the disequality relation on D.Let A and B be two relational structures1over the same vocabulary.A homomorphism h from A to B is a mapping h:A→B from the universe A of A to the universe B of B such that,for every relation R A of A and every tuple (a1,...,a k)∈R A,we have that(h(a1),...,h(a k))∈R B.The existence of a homomorphism from A to B is denoted by A→B,or by A→h B,when we want to name the homomorphism h explicitly.An important observation made in[29]2is that every such constraint-satisfaction instance P=(V,D,C)can be viewed as an instance of the homomorphism problem,asking whether there is a homomorphism between two structures A P and B P that are obtained from P in the following way:1.the universe of A P is V and the universe of B P is D;2.the relations of B P are the distinct relations R occurring in C;3.the relations of A P are defined as follows:for each distinct relation R onD occurring in C,we have the relation R A={t:(t,R)∈C}.Thus,R Aconsists of all scopes associated with R.We call(A P,B P)the homomorphism instance of P.Conversely,it is also clear that every instance of the homomorphism problem between two struc-tures A and B can be viewed as a constraint-satisfaction instance CSP(A,B) by simply“breaking up”each relation R A on A as follows:we generate a con-straint(t,R B)for each t∈R A.We call CSP(A,B)the constraint-satisfaction instance of(A,B).Thus,as pointed out in[29],the constraint-satisfaction problem can be identified with the homomorphism problem.To illustrate the passage from the constraint-satisfaction problem to the homomorphism problem,let us consider3-Sat.A3CNF-formulaϕwith vari-ables x1,...,x n and clauses c1,...,c m gives rise to a homomorphism instance (Aϕ,Bϕ)defined as follows:•Aϕ=({x1,...,x n},Rϕ0,Rϕ1,Rϕ2,Rϕ3),where Rϕi is the ternary relation consisting of all triples(x,y,z)of variables that occur in a clause ofϕwith i negated literals,0≤i≤3;for instance,Rϕ2consists of all triples (x,y,z)of variables such that(¬x∨¬y∨z)is a clause ofϕ(here,we assume without loss of generality that the negated literals precede the positive literals).•Bϕ=({0,1},R0,R1,R2,R3),where R i consists of all triples that satisfy a3-clause in which thefirst i literals are negated;for instance,R2= {0,1}3−{1,1,0}.Note that Bϕdoes not depend onϕ.It is clear thatϕis satisfiable if and only if there is a homomorphism from Aϕto Bϕ(in symbols,Aϕ→Bϕ).81Constraint SatisfactionAs another example,3-Colorability is equivalent to the problem of de-ciding whether there is a homomorphism h from a given graph G to the com-plete graph K3=({r,b,g},{(r,b)(b,r),(r,g)(g,r),(b,g)(g,b)}with3nodes. More generally,k-Colorability,k≥2,amounts to the existence of a ho-momorphism from a given graph G to the complete graph K k with k nodes (also known as the k-clique).Numerous other important NP-complete problems can be viewed as special cases of the Homomorphism Problem(and,hence,also of the Constraint-Satisfaction Problem).For example,consider the Clique problem:given a graph G and an integer k,does G contain a clique of size k?As a homo-morphism instance this is equivalent to asking if there is a homomorphism from the complete graph K k to G.As a constraint-satisfaction instance,the set of variables is{1,2,...,k},the domain is the set V of nodes of G,and the constraints are the pairs((i,j),E)such that i=j,1≤i,j≤k,and E is the edge relation of G.For another example,consider the Hamiltonic-ity Problem:given a graph G=(V,E)does it have a Hamiltonian cycle? This is equivalent to asking if there is a homomorphism from the structure (V,C V,=)to the structure(V,E,=),where C V is some cycle on the set V of nodes of G and=is the disequality relation on V.NP-completeness of the Homomorphism problem was pointed out explicitly in[53].In this chapter, we use both the traditional AI formulation of constraint satisfaction and the formulation as the homomorphism problem,as each has its own advantages.It turns out that in both formulations constraint satisfaction can be ex-pressed as a database-theoretic problem.We start with the homomorphism formulation,which is intimately related to conjunctive-query evaluation[48].A conjunctive query Q of arity n is a query definable by a positive existential first-order formulaϕ(X1,...,X n)having conjunction as its only propositional connective,that is,by a formula of the form∃Z1...∃Z mψ(X1,...,X n,Z1,...,Z m),whereψ(X1,...,X n,Z1,...,Z m)is a conjunction of(positive)atomic formu-las.The free variables X1,...,X n of the defining formula are called the distin-guished variables of Q.Such a conjunctive query is usually written as a rule, whose head is Q(X1,...,X n)and whose body isψ(X1,...,X n,Z1,...,Z m). For example,the formula∃Z1∃Z2(P(X1,Z1,Z2)∧R(Z2,Z3)∧R(Z3,X2))defines a binary conjunctive query Q,which as a rule becomesQ(X1,X2):-P(X1,Z1,Z2),R(Z2,Z3),R(Z3,X2).If the formula defining a conjunctive query Q has no free variables(i.e.,if it is a sentence),then Q is a Boolean conjunctive query.For example,the sentence∃Z1∃Z2∃Z3(E(Z1,Z2)∧E(Z2,Z3)∧E(Z3,Z1))1.2Preliminaries9 defines the Boolean conjunctive query“is there a cycle of length3?”.If D is a databaseand Q is a n-ary query,then Q(D)is the n-ary relationon D obtained by evaluating the query Q on D,that is,the collection of all n-tuples from D that satisfy the query(cf.Chapter??).The conjunctive-query evaluation problem asks:given a n-ary query Q,a database D, and a n-tuple a from D,does a∈Q(D)?Let Q1and Q2be two n-aryqueries having the same tuple of distinguished variables.We say that Q1iscontained in Q2,and write Q1⊆Q2,if Q1(D)⊆Q2(D)for every database D.The conjunctive-query containment problem asks:given two con-junctive queries Q1and Q2,is Q1⊆Q2?These concepts can be defined forBoolean conjunctive queries in an analogous manner.In particular,if Q is a Boolean query and D is a database,then Q(D)=1if D satisfies Q;otherwise,Q(D)=0.Moreover,the containment problem for Boolean queries Q1and Q2is equivalent to asking whether Q1logically implies Q2.It is well known that conjunctive-query containment can be reformu-lated both as a conjunctive-query evaluation problem and as a homomor-phism problem.What links these problems together is the canonical databaseD Q associated with Q.This database is defined as follows.Each variableoccurring in Q is considered a distinct element in the universe of D Q.Ev-ery predicate in the body of Q is a predicate of D Q as well;moreover,for every distinguished variable X i of Q,there is a distinct monadic pred-icate P i(not occurring in Q).Every subgoal in the body of Q gives rise toa tuple in the corresponding predicate of D Q;moreover,if X i is a distin-guished variable of Q,then P i(X i)is also a(monadic)tuple of D Q.Thus, returning to the preceding example,the canonical database of the conjunctivequery∃Z1∃Z2(P(X1,Z1,Z2)∧R(Z2,Z3)∧R(Z3,X2))consists of the factsP(X1,Z1,Z2),R(Z2,Z3),R(Z3,X2),P1(X1),P2(X2).The relationship be-tween conjunctive-query containment,conjunctive-query evaluation,and ho-momorphisms is provided by the following classical result,due to Chandra and Merlin.Theorem1.1.[11]Let Q1and Q2be two conjunctive queries having thesame tuple(X1,...,X n)of distinguished variables.Then the following state-ments are equivalent.•Q1⊆Q2.•(X1,...,X n)∈Q2(D Q1).•There is a homomorphism h:D Q2→D Q1.It follows that the homomorphism problem can be viewed as a conjunctive-query evaluation problem or as a conjunctive-query containment problem.Forthis,with every structure A,we view the universe A={X1,...,X n}of A as aset of individual variables and associate with A the Boolean conjunctive query ∃X1...∃X n∧t∈R A R(t);we call this query the canonical conjunctive query of A and denote it by Q A.It is clear that A is isomorphic to the canonicaldatabase associated with Q A.101Constraint SatisfactionCorollary1.2.Let A and B be two structures over the same vocabulary. Then the following statements are equivalent.•A→B.•B|=Q A.•Q B⊆Q A.As an illustration,we have that a graph G is3-colorable iffK3|=Q G iff⊆Q G.Q K3A relational join,denoted by the symbol1,is a conjunctive query with no existentially quantified variables.Thus,relational-join evaluation is a special case of conjunctive-query evaluation.For example,E(Z1,Z2)∧E(Z2,Z3)∧E(Z3,Z1)is a relational join that,when evaluated on a graph G=(V,E), returns all triples of nodes forming a3-cycle.There is a well known connec-tion between the traditional AI formulation of constraint satisfaction and relational-join evaluation that we describe next.Suppose we are given a constraint-satisfaction instance(V,D,C).We can assume without loss of gen-erality that in every constraint(t,R)∈C the elements in t are distinct. (Suppose to the contrary that t i=t j.Then we can delete from R every tu-ple in which the i th and j th entries disagree,and then project out that j-th column from t and R.)We can thus view every element of V as a relational attribute,every tuple of distinct elements of V as a relational schema,and every constraint(t,R)as a relation R over the schema t(cf.[1]).It now fol-lows from the definition of constraint satisfaction that CSP can be viewed as a relational-join evaluation problem.Proposition1.3.[6,42]A constraint-satisfaction instance(V,D,C)is solv-able if and only if1(t,R)∈C R is nonempty.Note that Proposition1.3is essentially the same as Corollary1.2.Indeed, the condition B|=Q A amounts to the non-emptiness of the relational join obtained from Q A by dropping all existential quantifiers and using the rela-tions from B as interpretations of the relational symbols in Q A.Moreover, the homomorphisms from A to B are precisely the tuples in the relational join associated with the constraint-satisfaction instance CSP(A,B).1.3Computational Complexity of Constraint SatisfactionThe Constraint-Satisfaction Problem is NP-complete,because it is clearly in NP and also contains NP-hard problems as special cases,including 3-Sat,3-Colorability,and Clique.As explained in Garey and Johnson’s classic monograph[36],one of the main ways to cope with NP-completeness is to identify polynomial-time solvable cases of the problem at hand that are obtained by imposing restrictions on the possible inputs.For instance,1.3Computational Complexity of Constraint Satisfaction11 Horn3-Sat,the restriction of3-Sat to Horn3CNF-formulas,is solvable in polynomial-time using a unit-propagation algorithm.Similarly,it is known that3-Colorability restricted to graphs of bounded treewidth is solvable in polynomial time(see[26]).In the case of constraint satisfaction,the pursuit of tractable cases has evolved over the years from the discovery of isolated cases to the discovery of large“islands of tractability”of constraint satisfaction.In what follows,we will give an account of some of the progress made in this ing the fact that the Constraint-Satisfaction Problem can be identified with the Homomorphism Problem,we begin by introducing some terminology and notation that will enable us to formalize the concept of an “island of tractability”of constraint satisfaction.In general,an instance of the Homomorphism Problem consists of two relational structures A and B.Thus,all restricted cases of this problem can be obtained by imposing restrictions on the input structures A and B.Definition1.4.Let A,B be two classes of relational structures.We write CSP(A,B)to denote the restriction of the Homomorphism Problem to in-put structures from A and B.In other words,CSP(A,B)={(A,B):A∈A,B∈B and A→B}.An island of tractability of constraint satisfaction is a pair(A,B)of classes of relational structures such that CSP(A,B)is in the complexity class PTIME of all decision problems solvable in polynomial time.(A more general definition of islands of tractability of constraint satisfaction would consider classes of pairs(A,B)of structures,cf.[28];we do not pursue this more general definition here.)The ultimate goal in the pursuit of islands of tractability of constraint sat-isfaction is to identify or characterize classes A and B of relational structures such that CSP(A,B)is in PTIME.The basic starting point in this investiga-tion is to consider the cases in which one of the two classes A,B is as small as possible,while the other is as large as possible.This amounts to considering the cases in which one of A,B is the class All of all relational structures over some arbitrary,butfixed,relational vocabulary,while the other is a single-ton,consisting of somefixed structure over that vocabulary.Thus,the start-ing points of the investigation is to determine,forfixed relational structures A,B,the computational complexity of the decision problems CSP({A},All) and CSP(All,{B}).Clearly,for eachfixed A,the decision problem CSP({A},All)can be solved in polynomial time,because,given a structure B,the existence of a homomorphism from A to B can be checked by testing all functions h from the universe A of A to the universe B of B(the total number of such functions is|B||A|,which is a polynomial number in the size of the structure B when A isfixed).Thus,having a singleton structure“on the left’is of little interest.At the other extreme,however,the situation is quite different,since the computational complexity of CSP(All,{B})may very well depend on the121Constraint Satisfactionparticular structure B.Indeed,CSP(All,{K3})is NP-complete,because it is the3-Colorability problem;in contrast,CSP(All,{K2})is in P,because it is the2-Colorability problem.For simplicity,in what follows,for every fixed structure B,we define CSP(B)=CSP(All,{B})and call this the non-uniform constraint-satisfaction problem associated with B.For such problems, we refer to B as the template.Thus,thefirst major goal in the study of the computational complexity of constraint satisfaction is to identify those templates B for which CSP(B)is in PTIME.This goals gives rise to an important open decision problem.The Tractability Classification Problem:Given a relational structure B,decide if CSP(B)is in PTIME.In addition to the family of non-uniform constraint-satisfaction problems CSP(B),where B is a relational structure,we also study decision problems of the form CSP(A,All),where A is a class of structures.We refer to such problems as uniform constraint-satisfaction problems.It is illuminating to consider the complexity of uniform and non-uniform constraint satisfaction from the perspective of query evaluation.As argued in[67](see Chapter??),there are three ways to measure the complexity of evaluating queries(we focus here on Boolean queries)expressible in a query language L:•The combined complexity of L is the complexity of the following decision problem:given an L-query Q and a structure A,does A|=Q?In symbols,{ Q,A :Q∈L and A|=Q}.•The expression complexity of L is the complexity of the following decision problems,one for eachfixed structure A:{Q:Q∈L and A|=Q}.•The data complexity of L is the complexity of the following decision prob-lems,one for eachfixed query Q∈L:{A:A|=Q}.As discussed in Chapter??,the data complexity offirst-order logic is in LOGSPACE,which means that,for eachfirst-order query Q,the problem {A:A|=Q}is in LOGSPACE.In contrast,the combined complexity for first-order logic is PSPACE-complete.Furthermore,the expression complex-ity forfirst-order logic is also PSPACE-complete.In fact,for all but trivial structures A,the problem{Q:Q∈F O and A|=Q}is PSPACE-complete. This exponential gap between data complexity,on one hand,and combined and expression complexity,on the other hand,is typical[67].For conjunc-tive queries,on the other hand,both combined and expression complexity are NP-complete.1.4Non-Uniform Constraint Satisfaction13Consider now the uniform constraint-satisfaction problem CSP(A,All)= {(A,B):A∈A,and A→B},where A is a class of structures.By Corol-lary1.2,we have thatCSP(A,All)={(A,B):A∈A,B is a structure and B|=Q A}.Thus,studying the complexity of uniform constraint satisfaction amounts to studying the combined complexity for a class of conjunctive queries,as, for example,in[12,39,62].In contrast,consider the non-uniform constraint-satisfaction problem CSP(B)={A:A→B}.By Corollary1.2we have that CSP(B)={A:B|=Q A}.Thus,studying the complexity of non-uniform constraint satisfaction amounts to studying the expression complexity of conjunctive queries with respect to different structures.This is a problem that has not been studied in the context of database theory.1.4Non-Uniform Constraint SatisfactionThefirst major result in the study of non-uniform constraint-satisfaction problems was obtained by Schaefer[63],who,in effect,classified the compu-tational complexity of all Boolean non-uniform constraint-satisfaction prob-lems.A Boolean structure is simply a relational structure with a2-element universe,that is,a structure of the form B=({0,1},R B1,...,R B m).A Boolean non-uniform constraint-satisfaction problem is a problem of the form CSP(B)with a Boolean template B.These problems are also known as Generalized-Satisfiability Problems,because they can be viewed as variants of Boolean-satisfiability problems in which the formulas are conjunc-tions of generalized connectives[36].In particular,they contain the well known problems k-Sat,k≥2,1-in-3-Sat,Positive1-in-3-Sat,Not-All-Equal 3-Sat,and Monotone3-Sat as special cases.For example,as seen ear-lier,3-Sat is CSP(B),where B=({0,1},R0,R1,R2,R3)and R i is the set of all triples that satisfy a3-clause in which thefirst i-literals are negated, i=0,1,2,3(thus,R0={0,1}3−{(0,0,0)}).Similarly,Monotone3-SAT is CSP(B),where B=({0,1},R0,R3).Ladner[51]showed that if PTIME=NP,then there are decision problems in NP that are neither NP-complete,nor belong to PTIME.Such problems are called intermediate problems.Consequently,it is conceivable that a given family of NP-problems contains intermediate problems.Schaefer[63],how-ever,showed that the family of all Boolean non-uniform constraint-satisfaction problems contains no intermediate problems.Theorem1.5.(Schaefer’s Dichotomy Theorem[63])•If B=({0,1},R B1,...,R B m)is Boolean structure,then either CSP(B)is in PTIME or CSP(B)is NP-complete.141Constraint Satisfaction•The Tractability Classification Problem for Boolean structures is decidable;in fact,there is a polynomial-time algorithm to decide,given a Boolean structure B,whether CSP(B)is in PTIME or is NP-complete.Schaefer’s Dichotomy Theorem can be described pictorially as follows:NP-completeCSP(B)PSchaefer[63]actually showed that there are exactly six types of Boolean structures such that CSP(B)is in PTIME,and provided explicit descriptions of them.Specifically,he showed that CSP(B)is in PTIME precisely when at least one of the following six conditions is satisfied:•Every relation R B i,1≤i≤m,of B is0-valid,that is,R B i contains the all-zeroes tuple(0,...,0).•Every relation R B i,1≤i≤m,of B is1-valid,that is,R B i contains the all-ones tuple(1,...,1).•Every relation R B i,1≤i≤m,of B is bijunctive,that is,R B i is the set of truth assignments satisfying some2-CNF formula.•Every relation R B i,1≤i≤m,of B is Horn,that is,R B i is the set of truth assignments satisfying some Horn formula.•Every relation R B i,1≤i≤m,of B is dual Horn,that is,R B i is the set of truth assignments satisfying some dual Horn formula.•Every relation R B i,1≤i≤m,of B is affine,that is,R B i is the set of solutions to a system of linear equations over the two-elementfield.Schaefer’s Dichotomy Theorem established a dichotomy and a decidable classification of the complexity of CSP(B)for Boolean templates B.After this, Hell and Neˇs etˇr il[43]established a dichotomy theorem for CSP(B)problems in which the template B is an undirected graph:if B is bipartite,then CSP(B) is solvable in polynomial time;otherwise,CSP(B)is NP-complete.To illus-trate this dichotomy theorem,let C n,n≥3,be a cycle with n elements.Then CSP(C n)is in PTIME if n is even,and is NP-complete if n is odd.The preceding two dichotomy results raise the challenge of classifying the computational complexity of CSP(B)for arbitrary relational templates B. Addressing this question,Feder and Vardi[29]formulated the following con-jecture.Conjecture1.6.(Dichotomy Conjecture)[29]If B=(B,R B1,...,R B m)is an arbitrary relational structure,then either CSP(B)is in PTIME or CSP(B)is NP-complete.1.4Non-Uniform Constraint Satisfaction15 In other words,the Dichotomy Conjecture says that the picture above de-scribes the complexity of non-uniform constraint-satisfaction problems CSP(B) for arbitrary structures B.The basis for the conjecture is not only the evi-dence from Boolean constraint satisfaction and undirected constraint satis-faction,but also from the seeming inability to carry out the diagonalization argument of[51]using the constraint-satisfaction machinery[27].The Dichotomy Conjecture inspired intensive research efforts that signif-icantly advanced our understanding of the complexity of non-uniform con-straint satisfaction.In particular,Bulatov confirmed two important cases of this conjecture.We say that a structure B=(B,R B1,...,R B m)is a3-element structure if B contains at most three element.We say that B is conserva-tive if all possible monadic relations on the universe included,that is,every non-empty subset of B is one of the relations R B i of B.Theorem1.7.[8,9]If B a3-element structure or a conservative structure, then either CSP(B)is in PTIME or CSP(B)is NP-complete.Moreover,in both cases the Tractability Classification Problem is decidable in poly-nomial time.In spite of the progress made,the Dichotomy Conjecture remains unre-solved in general.The research efforts towards this conjecture,however,have also resulted into the discovery of broad sufficient conditions for tractabil-ity and intractability of non-uniform constraint satisfaction that have pro-vided unifying explanations for numerous seemingly disparate tractability and intractability results and have also led to the discovery of new islands of tractability of CSP(B).These broad sufficient conditions are based on con-cepts and techniques from two different areas:universal algebra and logic.The approach via universal algebra yields sufficient conditions for tractabil-ity of CSP(B)in terms of closure properties of the relations in B under cer-tain functions on its universe B.Let R be a n-ary relation on a set B and f:B k→B a k-ary function.We say that R is closed under f,if whenever t1=(t11,t21,...,t n1),...,t k=(t1k,t2k,...,t n k)are k(not necessarily distinct) tuples in R,then the tuple(f(t11,...,t1k),f(t21,...,t2k),...,f(t n1,...,t n k))is also in R.We say that f:B k→B is a polymorphism of a structure B=(B,R1,...,R m)if each of the relations R j,1≤j≤m,is closed under f.It is easy to see that f is a polymorphism of B if and only if f is a homomorphism from B k to B,where B k is the k-th power of B.By definition, the k-th power B k is the structure(B k,R′1...,R′m)over the same vocabulary as B with universe B k and relations R′j,1≤j≤m,defined as follows:if R j is of arity n,then R′j(s1,...,s n)holds in B k if and only if R j(s i1,...,s i n) holds in B for1≤i≤n.We write Pol(B)for the set of all polymorphisms of B.As it turns out, the complexity of CSP(B)is intimately connected to the kinds of functions161Constraint Satisfactionthat Pol(B )contains.This connection was first unveiled in [29],and explored in depth by Jeavons and his collaborators;for a recent survey see [10].In particular,they showed that if Pol(B 1)=Pol(B 2)for two structures B 1and B 2(over finite vocabularies),then CSP(B 1)and CSP(B 2)are polynomially reducible to each other.Thus,the polymorphisms of a template B characterize the complexity of CSP(B ).The above mentioned dichotomy results for 3-element and conservative constraint satisfaction are based on a rather deep analysis of the appropriate sets of polymorphisms.1.5Monotone Monadic SNP and Non-UniformConstraint SatisfactionWe discussed earlier how non-uniform constraint satisfaction is related to the study of the expression complexity of conjunctive queries.We now show that it can also be viewed as the study of the data complexity of second-order logic.This will suggest a way to identify islands of tractability via logic.As described in Chapters ??and ??,existential second-order logic ESO defines,by Fagin’s Theorem,precisely the complexity class NP.The class SNP (for strict NP)[46,57]is a fragment of ESO,consisting of all existential second-order sentences with a universal first-order part,namely,sentences of the form (∃S ′)(∀x )Φ(x ,S,S ′),where Φis a first-order quantifier-free formula.We refer to the relations over the input vocabulary S as input relations ,while the relations over the quantified vocabulary S ′are referred to as existential re-lations .3-Sat is an example of an SNP problem.The input structure consists of four ternary relations C 0,C 1,C 2,C 3,on the universe {0,1},where C i cor-responds to a clause on three variables with the first i of them negated.There is a single existential monadic relation T describing a truth assignment.The condition that must be satisfied states that for all x 1,x 2,x 3,if C 0(x 1,x 2,x 3)then T (x 1)or T (x 2)or T (x 3),and similarly for the remaining C i by negating T (x j )if j ≤i .Formally,we can express 3-Sat with the SNP sentence:(∃T )(∀x 1,x 2,x 3)((C 0(x 1,x 2,x 3)→T (x 1)∨T (x 2)∨T (x 3))∧(C 1(x 1,x 2,x 3)→¬T (x 1)∨T (x 2)∨T (x 3))∧(C 2(x 1,x 2,x 3)→¬T (x 1)∨¬T (x 2)∨T (x 3))∧(C 3(x 1,x 2,x 3)→¬T (x 1)∨¬T (x 2)∨¬T (x 3))).It is easy to see that CSP(B )is in SNP for each structure B .For each ele-ment a in the universe of B ,we introduce an existentially quantified monadic relation T a ;intuitively,T a (x )indicates that a variable x has been assigned value a by the homomorphism.The sentence ϕB says that the sets T a cover all elements in the universe 3,and that the tuples in the input relations satisfy the constraints imposed by the structure B .Thus,if R (a 1,...,a n )does not hold in B ,then ϕB contains the conjunct ¬(R (x 1,...,x n )∧ n i =1T a i (x i )).For。

A Constraint Satisfaction Model of Causal Learning and ReasoningYork Hagmayer(york.hagmayer@bio.uni-goettingen.de)Department of Psychology,University of GöttingenGosslerstr.14,37073Göttingen,GermanyMichael R.Waldmann(michael.waldmann@bio.uni-goettingen.de)Department of Psychology,University of GöttingenGosslerstr.14,37073Göttingen,GermanyAbstractFollowing up on previous work by Thagard(1989,2000)we have developed a connectionist constraint satisfaction model which aims at capturing a wide variety of tasks involving causal cognitions,including causal reasoning,learning,hy-pothesis testing,and prediction.We will show that this model predicts a number of recent findings,including asymmetries of blocking,and asymmetries of sensitivity to structural im-plications of causal models in explicit versus implicit tasks.IntroductionCausal reasoning has been widely investigated during the last decade,which has led to a number of interesting novel findings(see Shanks,Holyoak,&Medin,1996;Hagmayer &Waldmann,2001,for overviews).For example,it has been shown that participants’causal judgments are sensitive to the contingency between the cause and the effect,and that people’s judgments reflect the causal models underlying the observed learning events(see Hagmayer&Waldmann, 2001;Waldmann,1996).Moreover,causal reasoning has been studied in the context of a number of different tasks, such as learning,reasoning,categorization,or hypothesis testing.Most psychological theories and computational models of causal learning and reasoning are rooted in two traditions. They are either based on associationistic or on probabilistic or Bayesian models(see Shanks et al.,1996;Thagard, 2000).Both kinds of models have been criticized.Associa-tionistic learning networks have proven unable to capture the fundamental semantics of causal models because they are insensitive to the differences between learning events that represent causes versus effects(see Waldmann,1996). By contrast,Bayesian networks are perfectly capable of rep-resenting causal models with links directed from causes to effects(see Pearl,2000).However,although the goal of these networks is to reduce the complexity of purely prob-abilistic reasoning,realistic Bayesian models still require fairly complex computations,and they presuppose compe-tencies in reasoning with numerical probabilities which seem unrealistic for untutored people(see Thagard,2000,for a detailed critique of these models).The aim of this paper is to introduce a more qualitatively oriented,connectionist constraint satisfaction model of causal reasoning and learning.Our model is inspired by Thagard’s(2000)suggestion that constraint satisfaction models may qualitatively capture many insights underlying normative Bayesian network models in spite of the fact that constraint satisfaction model use computationally far sim-pler,and therefore psychologically more realistic processes. The model differs from standard associationist learning models(e.g.,Rescorla&Wagner,1972)in that it is capable of expressing basic differences between causal models.Our model embodies a uniform mechanism of learning and rea-soning,which assesses the fit between data and causal mod-els.This architecture allows us to model a wide range of different tasks within a unified model,which in the literature have so far been treated as separate,such as learning and hypothesis testing.Constraint Satisfaction Models Constraint satisfaction models(Thagard,1989,2000)aim at capturing qualitative aspects of reasoning.Their basic as-sumption is that people hold a set of interconnected beliefs. The beliefs pose constraints on each other,they either sup-port each other,contradict each other,or are unrelated.Co-herence between the beliefs can be achieved by processes which attempt to honor these constraints.Within a constraint satisfaction model beliefs are repre-sented as nodes which represent propositions(e.g.,“A causes B”).The nodes are connected by symmetric relations. The numerical activation of the nodes indicates the strength of the belief in the proposition.A belief that is highly acti-vated is held strongly,a belief that is negatively activated is rejected.The activation of a node depends on the activation of all other nodes with which it is connected.More pre-cisely,the net input to a single node j from all other nodes i is defined as the weighted sum of the activation a of all re-lated nodes(following Thagard,1989,p.466,eq.5):Net j=∑i w ij a i(t)(1) The weights w represent the strength of the connection of the beliefs.In our simulations,they are generally pre-set to default values which are either positive or negative and re-main constant throughout the simulation.At the beginning of the simulations,the activation of the nodes representing hy-potheses are set to a low default value.However,nodes rep-resenting empirical evidence are connected to a special acti-vation node whose activation remains constant at1.0.This architecture allows us to capture the intuition that more faith is put into empirical evidence than into theoretical hypothe-ses(see Thagard,1989).To update the activation in eachcycle of the simulation,first the net input net j to each node is computed using Equation1.Second the activation of all nodes is updated using the following equation(Thagard, 1989,p.446,eq.4):a j(t+1)=a j(t)(1-θ)+net j(max-a j(t))if net j>0=a j(t)(1-θ)+net j(a j(t)-min)otherwise.(2) In Equation2,θis a decay parameter that decrements the activity of each node in every cycle,min represents the minimum activation(-1)and max the maximum activation (+1).The activations of all nodes are updated until a stable equilibrium is reached,which means that the activation of all nodes do no longer substantially change.To derive quantita-tive predictions it would be necessary to specify rules that map the final activations to different types of responses. This is an important goal which should be addressed in fu-ture research.In the present article we only derive ordinal, qualitative predictions from the model.The ModelFollowing causal-model theory(Waldmann,1996)we as-sume that people typically enter causal tasks with initial as-sumptions about the causal structure they are going to ob-serve.Even though specific knowledge about causal rela-tions may not always be available,people often bring to bear knowledge about abstract features of the models,such as the distinction between events that refer to potential causes and events that refer to potential effects.In virtually all psycho-logical studies this information can be gleaned from the ini-tial instructions and the materials(see Waldmann,1996).Figure1displays an example of how the model repre-sents a causal model.The nodes represent either causal hy-potheses or observable events.The causal hypothesis node at the top represents a structural causal hypothesis(H1),in this case the hypothesis that the three events e1,e2,x form a common-effect structure with e1and e2as the two alternative causes and x as the common effect.The two nodes on the middle level refer to the two causal relations H2and H3that are part of the common-effect model with two causes and a single effect.The nodes on the lowest level refer to all pat-terns of events that can be observed with three events(a dot represents“and”).On the left side,the nodes represent pat-terns of three events,in the middle pairs,and on the right side single events.Not only the present but also the corre-sponding absent events are represented within this model (for example~x).The links connecting the nodes represent belief relations.Thus,they do not represent probabilities or causal relations as in Bayesian models.There are two differ-ent kinds of connections between the nodes.Solid lines indi-cate excitatory links,dashed lines inhibitory links.How are the connections defined?A connection is positive if the propositions support each other.For example,if all three events are present,the observation is in accordance with both hypotheses H2and H3.This pattern might be observed if both e1and e2cause x.Therefore the evidence node e1.e2.x is positively connected to H2and H3.In general,a hypothesis is positively connected to an evidence node if the events mentioned in the hypothesis are either all present or all absent.If this is not the case,that is if one of the relevant events specified in the hypothesis is absent,the link is as-signed the negative default value.Exploratory studies have shown,that participants share a common intuition whether a certain pattern of events supports or contradicts a hypothesis (Hagmayer&Waldmann,2001).The assigned weights mir-ror these general intuitions.The weights of the links remain the same throughout the simulations.Figure1does not dis-play the special activation node.This node was pre-set to 1.0and attached to event nodes describing present events in the respective experiment.and reasoning.See text for further explanations.In Figure1,the dashed line between the hypotheses H1and H2,which signifies an inhibitory link,is of special interest. The network represents a common-effect structure.This means that there are two causes e1and e2which compete in explaining the occurrence of effect x.Therefore the two hypotheses referring to the individual causal relations have to be connected by a inhibitory link(see also Thagard, 2000).However,both hypotheses H2and H3are positively connected to the structural hypothesis H1.By contrast,a common-cause structure is represented slightly differently. In such a structure,event x would be the common cause of the two effects e1and e2(i.e.,H1:x!e1.e2).A model of this structure looks almost identical to the one for the com-mon-effect structure in Figure1.There is only one very im-portant difference.Because there is no competition between the effects of a common cause,a common-cause model has no inhibitory link between H2and H3.All other nodes and links in the two models are identical.Both the common-effect and the common-cause model were implemented using Microsoft Excel.Default values were adopted from the literature if not indicated otherwise (Thagard,1989).Initial activations were set to0.01,inhibi-tory links between nodes to–0.05,and excitatory links to +0.05.The inhibitory link between H1and H2within the common-effect model was pre-set to a value of–0.20.Thespecial activation node was attached to all evidence nodes. The additional activation was divided among the evidence nodes according to the relative frequency of the evidence in the learning input.This principle captures the intuition that more faith is put into evidence that is observed more fre-quently.EvaluationIn order to evaluate the proposed constraint satisfaction model different tasks and paradigms from the literature on causal learning and reasoning were modeled.One of our main goals was to show that the same architecture can be used to simulate different types of tasks.However,different tasks required different sections of the model depicted in Figure1.We used two principles for the construction of task specific networks.The first principle is that we only in-cluded the event nodes that corresponded to the event pat-terns observed in the learning phase or that corresponded to events that have to be evaluated or predicted in the test phase.For example,to model a task in which only event triples were shown,only the event nodes on the left side of the event layer in Figure1would be incorporated in the model.However,if the task following the learning phase required the prediction of single events,the corresponding nodes for single events would have to be added to the event layer.The second principle is that only the hypothesis nodes were included that represent hypotheses that are given or suggested to participants.These two principles ensure that for each paradigm a minimally sufficient sub-model of the complete model is instantiated.Test1:Asymmetries of BlockingBlocking belongs to the central phenomena observed in as-sociative learning which,among other findings,have moti-vated learning rules that embody cue competition(e.g.,Res-corla&Wagner,1972).A typical blocking experiment con-sists of two learning phases.In Phase1participants learn that two events e1and x are either both present or absent.In Phase2a third event e2is introduced.Now all three events are either present or absent.In both phases,events e1and e2 represent cues and x the outcome to be predicted.Associa-tive theories generally predict a blocking effect which means that participants should be reluctant about the causal status of the redundant event e2that has been constantly paired with the predictive event e1from Phase1.This prediction has come under attack by recent findings that have shown that the blocking effect depends on the causal model learn-ers bring to bear on the task(see Waldmann,1996,2000).If participants assume that e1and e2are the causes of x(com-mon-effect structure)a blocking effect can be seen.In con-trast,if participants assume that e1and e2are the collateral effects of the common cause x(common-cause structure),no blocking of e2is observed.In this condition,learners tend to view both e1and e2as equally valid diagnostic cues of x.To model blocking,we used a network that was ex-tended after Phase1.In Phase1,the net consisted of a hy-pothesis node(H2)and the nodes for patterns of two events (e1,x).After Phase1,the final activation of the hypothesis node was transferred to Phase2.In Phase2,the network consisted of two nodes for the two causal hypotheses(H2 and H3),and nodes that represented patterns of three events, the patterns participants observed within the learning phase. Furthermore,the node H1was included,which,depending on the condition,either coded a common-cause or a com-mon-effect hypothesis.The nodes for the event pairs from Phase1were removed.Figure2shows the activation of the two hypotheses re-ferring to the causal relations in Phase1and2.Figure2A depicts the activation for the common-cause model and Fig-ure2B for the common-effect model.Figure2A:Simulation of a blocking paradigm(Test1).Activation of hypothesis nodes for a common-causemodel.The solid line represents the activation ofH2:x→e1,the dotted line of H3:x→e2.Phase2started at the101st.cycle.The model shows no blocking for event e2in the context of the common-cause model.It quickly acquires the belief that there is a causal connection between x and e2.Figure2B:Simulation of a blocking paradigm(Test1).Activation of hypothesis nodes for a common-effectstructure.The upper line represents the activation ofH2:e1→x,the lower line of H3:e2→x.Phase2started at the101st cycle.For the common-effect model the simulation shows blocking of the second cause,that is the second hypothesis is believed to be wrong.Thus,the simulations closely correspond to the empirical finding that blocking interacts with the structure of the causal model used to interpret the learning data.Test2:Testing Complex Causal HypothesesThe first test of the model used a phenomenon from the lit-erature on causal learning.We now want to turn to a com-pletely different paradigm,hypothesis testing.In experi-ments on causal learning participants are typically instructed about a causal structure,and the task is to learn about the causal relations within the structure.They are not asked whether they believe that the structure is supported by the learning data or not.In recent experiments(Hagmayer, 2001;Hagmayer&Waldmann,2001)we gave participants the task to test a complex causal model hypothesis.For ex-ample,we asked them whether three observed events sup-port a common-cause hypothesis or not.Normatively this task should be solved by testing the implications of the given structural hypothesis.For example,a common-cause model implies a(spurious)correlation of the effects of the single common cause.In contrast,a common-effect structure does not imply a correlation of the different causes of the joint effect.Unless there is an additional hidden event that causes a correlation among the causes,they should be uncorrelated. In the experiment,participants were given data which either displayed a correlation between all three events(data set1) or correlations between e1-x and e2-x only,that is e1and e2 were marginally independent in this data(data set2).Data set1was consistent with a common-cause hypothesis which implies correlations between all three events.In contrast, data set2favors the common-effect hypothesis with x as the effect and e1and e2as independent causes.However,in a series of experiments we found that participants were not aware of these differential structural implications when test-ing the two hypotheses.Instead they checked whether the individual causal relations within the complex structures held(e.g.,e1-x).Thus,participants dismissed a hypothesis if one of the assumed causal links was missing.However,they proved unable to distinguish between the common-cause and the common-effect structure when both structures specified causal connections between the same events(regardless of the direction).To model this task we used the model without the nodes for event pairs and individual events.The special activation node was connected to the patterns of three events.As be-fore the activation of the individual event patterns was pro-portional to the frequency of the respective pattern in the data.To test the model,we used three sets of data.Either all three events were correlated(data set1),e1and x,and e2 and x were correlated and e1and e2were marginally inde-pendent(data set2),or e1and x,and e1and e2were corre-lated,and e2and x were uncorrelated(data set3).As com-peting hypotheses we either used a common-cause model with x as the common cause,or a common-effect model with x as the common effect.Figure3shows the activation of the node H1which represents the hypothesis that the respective causal model underlies the observed data.Figure3A shows the results for the common-cause hy-pothesis,Figure3B for the common-effect hypothesis.The results clearly mirror the judgments of our participants. Whenever the two assumed causal relations within either causal model were represented in the data,the structural hypothesis was accepted(solid lines),if one link was miss-ing the hypothesis was rejected(dotted line).One slight deviation from our empirical findings was ob-served.In early cycles there seems to be an effect favoring the common-effect hypothesis with data consistent with this hypothesis.However,the difference between the hypotheses is relatively small and further decreases after100updating cycles.Thus,the results are consistent with participants’insensitivity to structural implications of causal models in hypothesis testing tasks.Figure3A:Activation of hypothesis node H1for a com-mon-cause model(Test2).The solid lines represent the activations for data set1and2,the dotted line the activa-tions for data set3.Figure3B:Activation of hypothesis node H1for a com-mon-effect model(Test2).The solid lines represent the activations for data set1and2,the dashed line at thebottom the activations for data set3Why does the model not differentiate between the two causal structures?The reason is that it is assumed that com-plex structural hypotheses are not directly linked to empiri-cal evidence.In our model empirical evidence is connected to the hypotheses that represent individual causal links which in turn are linked to more complex model-related hypotheses.This architecture allows it to model learning and hypothesis testing within the same model.It also seems to capture the empirical finding that participants can easily decide whether a certain pattern of events supports a simple causal hypothesis,but have a hard time to relate event pat-terns to complex causal hypotheses.Test3:Causal InferencesIn the previous section we have mentioned studies showing insensitivity to spurious relations implied by causal models.A last test for our model is a task in which participants have to predict other events under the assumption that a certain causal model holds.Interestingly we have empirically dem-onstrated sensitivity to structural implications of causal models in this more implicit task(Hagmayer&Waldmann, 2000).In this task participants do not have to evaluate the validity of a causal model in light of observed evidence but rather are instructed to use causal models when predicting individual events.In our experiments we presented partici-pants with two learning phases in which they learned about two causal relations one at a time.Thus,in each phase par-ticipants only received information about the presence and absence of two events(x and e1,or x and e2).They never saw patterns of all three events during the experiment.The initial instructions described the two causal relations,which were identically presented across conditions,either as parts of a common-cause model with x as the cause or as part of a common-effect model with x as the effect.After participants had learned about the two causal relations we asked them to predict whether e1and e2were present given that x was present.We found that participants were more likely to pre-dict that both e1and e2would co-occur when x was viewed as the common cause than when it was seen as a common effect.Thus,in this more implicit task the predictions ex-pressed knowledge about structural implications of causal models.In particular,the patterns the participants predicted embodied a spurious correlation among the effects of a com-mon cause,whereas the causes of a common effect tended to be marginally uncorrelated in the predicted patterns.By contrast,in a more direct task which required explicit judgments about correlations,no such sensitivity was observed,which is consistent with the results reported in the previous section.To model this experiment we eventually used the com-plete network depicted in Figure1which was successively augmented according to our two principles.In Phase1,the learning phase,patterns of two events were connected to the hypotheses H2and H3.Depending on the learning condi-tion,these two hypotheses were either linked to a common-cause or a common-effect hypothesis(H1).The activations of the hypothesis nodes at the end of Phase1were used as initial activation values in Phase2.In Phase2the model consisted of the three hypothesis nodes,the nodes for pat-terns of three events and the nodes representing single events.The single event nodes were included because the task required the prediction of individual events.The special activation node was now attached to event x.The model then predicted the other two individual events and patterns of all three events.The model quickly learned the causal relations during Phase1of the experiment.Figure4depicts the results of Phase2.Figure4A shows the predictions of the model for the condition in which participants assumed a common-cause model,Figure4B shows the results for the common-effect condition.The results of the simulations are consistent with the behavior we have observed in our participants. When the model assumes a common-cause model the pres-ence of x leads to a high positive activation of the two ef-fects e1and e2.This means that the model tends to prefer the prediction that the two effects of a common cause co-occur.In contrast,for the common-effect structure the model does not show such a preference.In this condition, both causes or either one of them equally qualify as possible explanations of the observed effect.This means that our model,similar to the one Thagard(2000)has proposed, tends to“explain away”the second cause when one of the competing causes is present.This is a consequence of the competition between the two causal hypothesis H2and H3.Figure4A:Implicit causal inferences(Test3).Activa-tion of single event nodes for the common-cause model: Event x(top),events e1and e2(bottom)Figure4B:Implicit causal inferences(Test3).Activa-tion of single event nodes for the common-effect model: Event x(top),event e1(middle),event e2(bottom)DiscussionA constraint satisfaction model of causal learning and rea-soning was presented in this paper that extends the architec-ture and scope of the model proposed by Thagard(2000). Thagard’s model focuses upon causal explanations of singu-lar events and belief updating.Our aim was to create a model that allows it to model both learning and reasoning within causal models.The model was successfully applied to three different tasks.It modeled people’s sensitivity to struc-tural implications of causal models in tasks involving learn-ing and predictions whereas the same model also predicted that people would fail in tasks which required explicit knowledge of the statistical implications of causal models.One question that might be raised is whether the pro-posed model really captures learning or just models causal judgment.In our view,the concept of learning does not nec-essarily imply incremental updating of associative weights Our model embodies a hypothesis testing approach to learn-ing which assumes that learners modify the strength of belief in deterministic causal hypotheses based on probabilistic learning input.This view also underlies recent Bayesian models of causality(Pearl,2000).In the model the activa-tion(i.e.,degree of belief)of the hypothesis nodes is modi-fied based on the learning input.This way the model is ca-pable of modeling trial-by-trial learning as well as learning based on summary data within the same architecture.Thus far we have pre-set the weights connecting evi-dence and hypotheses.In our view,the assigned values re-flect everyday qualitative intuitions about whether an event pattern supports or contradicts a hypothesized causal hy-pothesis.These weights remained constant throughout the simulations.Despite this restriction the model successfully predicted empirical phenomena in learning and reasoning. However,pre-setting these weights is not a necessary feature of the model.It is possible to add a learning component that acquires knowledge about the relation between event pat-terns and hypotheses based on feedback in a prior learning phase(see Wang et al.,1998,for a model adding associative learning to Echo).In summary,our constraint satisfaction model seems to offer a promising new way to model causal learning and reasoning.It is capable of modeling phenomena in a wide range of different tasks,which thus far have been treated as separate in the literature.Relative to normative Bayesian models,our connectionist model allows it to simulate a large number of different tasks and different phenomena while using fairly simple computational routines.It proved capable of capturing a number of recent phenomena that have pre-sented problems to extant models of causal cognition.More tests of the model clearly seem warranted.ReferencesHagmayer,Y.(2001).Denken mit undüber Kausalmodelle. Unpublished Doctoral Dissertation,University of Göttin-gen.Hagmayer,Y.,&Waldmann,M.R.(2000).Simulating causal models:The way to structural sensitivity.In L.R. Gleitman& A.K.Joshi(Eds.),Proceedings of the Twenty-Second Annual Conference of the Cognitive Sci-ence Society(pp.214-219).Mahwah,NJ:Erlbaum. Hagmayer,Y.,&Waldmann,M.R.(2001).Testing com-plex causal hypotheses.In M.May&U.Oestermeier (Eds.),Interdisciplinary perspectives on causation(pp.59-80).Bern:Books on Demand.Pearl,J.(2000).Causality:Models,reasoning,and infer-ence.Cambridge:Cambridge University Press. Rescorla,R.A.,&Wagner,A.R.(1972).A theory of Pav-lovian conditioning:Variations in the effectiveness of rein-forcement and non-reinforcement.In A.H.Black&W.F. Prokasy(Eds.),Classical conditioning II.Current re-search and theory(pp.64-99)New York:Appleton-Century-Crofts.Shanks,D.R.,Holyoak,K.J.,&Medin,D.L.(Eds.)(1996). The psychology of learning and motivation,Vol.34: Causal learning.San Diego:Academic Press. Thagard,P.(1989).Explanatory coherence.Behavioral and Brain Sciences,12,435-467.Thagard,P.(2000).Coherence in thought and action.Cam-bridge,MA:MIT Press.Waldmann,M.R.(1996).Knowledge-based causal induc-tion.In D.R.Shanks,K.J.Holyoak&D.L.Medin(Eds.), The psychology of learning and motivation,Vol.34: Causal learning(pp.47-88).San Diego:Academic Press. Waldmann,M.R.(2000).Competition among causes but not effects in predictive and diagnostic learning.Journal of Experimental Psychology:Learning,Memory,and Cognition,26,53-76.Wang,H.,Johnson,T.R.,&Zhang,J.(1998).UEcho:A model of uncertainty management in human abductive rea-soning.In M.A.Gernsbacher&S.R.Derry(Eds.),Pro-ceedings of the Twentieth Annual Conference of the Cog-nitive Science Society(pp.1113-1118).Mahwah,NJ:Erl-baum.。

人工智能原理_北京大学中国大学mooc课后章节答案期末考试题库2023年1.Turing Test is designed to provide what kind of satisfactory operationaldefinition?图灵测试旨在给予哪一种令人满意的操作定义？答案:machine intelligence 机器智能2.Thinking the differences between agent functions and agent programs, selectcorrect statements from following ones.考虑智能体函数与智能体程序的差异，从下列陈述中选择正确的答案。

答案:An agent program implements an agent function.一个智能体程序实现一个智能体函数。

3.There are two main kinds of formulation for 8-queens problem. Which of thefollowing one is the formulation that starts with all 8 queens on the boardand moves them around?有两种8皇后问题的形式化方式。

“初始时8个皇后都放在棋盘上，然后再进行移动”属于哪一种形式化方式？答案:Complete-state formulation 全态形式化4.What kind of knowledge will be used to describe how a problem is solved?哪种知识可用于描述如何求解问题？答案:Procedural knowledge 过程性知识5.Which of the following is used to discover general facts from trainingexamples?下列中哪个用于训练样本中发现一般的事实？答案:Inductive learning 归纳学习6.Which statement best describes the task of “classification” in machinelearning?哪一个是机器学习中“分类”任务的正确描述？答案:To assign a category to each item. 为每个项目分配一个类别。

A Dichotomy Theorem for Constraints on a Three-Element SetAndrei A.BulatovComputing Laboratory,University of Oxford,Oxford,UKE-mail:Andrei.Bulatov@AbstractThe Constraint Satisfaction Problem(CSP)provides a common framework for many combinatorial problems.The general CSP is known to be NP-complete;however,certain restrictions on the possible form of constraints may affect the complexity,and lead to tractable problem classes.There is,therefore,a fundamental research direction,aiming to separate those subclasses of the CSP which are tractable, from those which remain NP-complete.In1978Schaefer gave an exhaustive solution of this problem for the CSP on a2-element domain.In this paper we generalise this result to a classification of the complex-ity of CSPs on a3-element domain.The main result states that every subclass of the CSP defined by a set of allowed constraints is either tractable or NP-complete,and the cri-terion separating them is that conjectured in[6,8].We also exhibit a polynomial time algorithm which,for a given set of allowed constraints,determines whether if this set gives rise to a tractable problem class.To obtain the main result and the algorithm we extensively use the algebraic technique for the CSP developed in[17]and[6,8].1.IntroductionIn the Constraint Satisfaction Problem(CSP)[24]we aim tofind an assignment to a set of variables subject to specified constraints.Many combinatorial problems ap-pearing in computer science and artificial intelligence can be expressed as particular subclasses of the CSP.The stan-dard examples include the propositional satisfiability prob-lem,in which the variables must be assigned Boolean val-ues,graph colorability,scheduling problems,linear systems and many others.One advantage of considering a com-mon framework for all of these diverse problems is that it makes it possible to obtain generic structural results con-cerning the computational complexity of constraint satis-faction problems that can be applied in many different areas such as database theory[21,33],temporal and spatial rea-soning[30],machine vision[24],belief maintenance[11],technical design[26],natural language comprehension[1], programming language analysis[25],etc.The general CSP is NP-complete;however,certain re-strictions on the allowed form of the constraints involved may ensure tractability.Therefore,one of the main ap-proaches in the study of the CSP is identifying tractable subclasses of the general CSP obtained in this way[14,15, 9,17,29].Developments in this direction provide an ef-ficient algorithm solving a particular problem,if the prob-lem falls in one of the known tractable subclasses,or as-sist in speeding up of general superpolynomial algorithms [12,13,22].To formalize the idea of restricting the allowed constraints,we make use of the notion of a constraint lan-guage[16],which is simply a set of possible relations that can be used to specify constraints in a problem.We say that a constraint language is tractable[intractable]if the corresponding problem class is tractable[intractable.The ultimate goal of this research direction is tofind the pre-cise border between tractable and intractable constraint lan-guages.This goal was achieved by Schaefer[29]in the important case of Boolean constraints;he has characterised tractable constraint languages on a2-element set,and proved that the rest are NP-complete.This Schaefer’s result is known as Shaefer’s Dichotomy Theorem.Dichotomy theorems are of particular interests in study of the CSP,because,on the one hand,they determine the precise complexity of constraint languages,and on the other hand,the a priori existence of a dichotomy result cannot be taken for granted.For a short survey of dichotomy results the reader is referred to[9].The analogous problem,which is referred to as the clas-sification problem,for the CSP in which the variables can be assigned more than2values,remains open since1978, in spite of intensive efforts.For instance,Feder and Vardi, in[14],used database technique and group theory to iden-tify some large tractable families of constraints;Jeavons and coauthors have characterised many tractable and NP-complete constraint languages using invariance properties of constraints[17,18,19];in[8],a possible form of a di-chotomy result for the CSP onfinite domains was conjec-tured;in[7],a dichotomy result was proved for a certaintype of constraint languages on a3-element domain.In this paper we generalise the results of[29]and[7],and provethe dichotomy conjecture from[8]for the constraint sat-isfaction problem on a3-element domain.In particular, we completely characterise tractable constraint languagesin this case,and prove that the rest are NP-complete.The main result will be precisely stated at the end of Section2.The classification problem for constraint languages on aset containing more than2elements,even on a3-element set,turns out to be much harder than that for the2-elementcase.Besides the obvious reason that Boolean CSPs closely relate to various problems from propositional logic,and therefore,are much better investigated,there is another deepreason.As is showed in[19,20,17],when studying the complexity of constraint languages we may restrict our-selves with a certain class of languages,so called relationalclones.There are only countably many relational clones on a2-element set,and all of them are known[28].However,the class of relational clones on a3-element set already con-tains continuum many elements,and any its explicit charac-terization is believed to be unreachable.Another problem tackled here is referred to,in[9],as themeta-problem:given a constraint language determine if this language gives rise to a tractable problem class.Making useof the dichotomy theorem obtained we exhibit an effective algorithm solving the meta-problem for the CSP on a3-element domain.The technique used in this paper relies upon the idea,that was developed in[8,6,17](and also mentioned in[14]as a possible direction for future research),that algebraic in-variance properties of constraints can be used for studying the complexity of the corresponding constraint satisfaction problems.The main advantage of this technique is that itallows us to employ structural results from universal alge-bra.The algebraic approach has proved to be very fruitfulin identifying tractable classes of the CSP[2,4,18].We strongly believe that the synthesis between complexity the-ory and universal algebra which we describe here is likelyto lead to new results in bothfields.2.Algebraic structure of CSP classes2.1.The Constraint Satisfaction ProblemThe set of all-tuples with components from a set isdenoted.The th component of a tuple will be denoted .Any subset of is called an-ary relation on;and a constraint language on is an arbitrary set offinitaryrelations on.Definition1The constraint satisfaction problem()over a constraint language,denoted,is defined to be the decision problem with instance,where Instance:is a set of variables;is a set of values(some-times called a domain);and is a set of constraints,,in which the constraint is a pair with is a tuple of variables of length, called the constraint scope,and an-ary re-lation on,called the constraint relation. Question:is whether there exists a solution to, that is,a function from to,such that,for each constraint in,the image of the constraint scope is a member of the constraint relation.We shall be concerned with distinguishing between those constraint languages which give rise to tractable problems (i.e.,problems for which there exists a polynomial-time so-lution algorithm),and those which do not.Definition2A constraint language,is said to be tractable,if is tractable for eachfinite subset .It is said to be NP-complete,if is NP-complete for somefinite subset.By a Boolean constraint language we mean a constraint language on a2-element set,usually.In[29],Schae-fer has classified Boolean constraint languages with re-spect to complexity.This result is known as Schaefer’s Di-chotomy theorem.Theorem1(Schaefer,[29])A constraint language,,on is tractable if one of the following conditions holds:(1)every in contains;(2)every in contains;(3)every in is definable by a CNF formula in whicheach clause has at most one negated variable;(4)every in is definable by a CNF formula in whicheach clause has at most one unnegated variable; (5)every in is definable by a CNF formula in whicheach clause has at most two literals;(6)every in is the solution space of a linear systemover.Otherwise is NP-complete.More examples of both tractable and NP-complete con-straint languages will appear later in this paper and can also be found in[8,10,14,19].It follows from Theorem1 that every Boolean constraint language is either tractable or NP-complete;and so,there is no language of intermedi-ate complexity.Some dichotomy results have been obtained for other variations of Boolean CSP[9].The classification problem for larger domains is still open and seems to be very interesting and hard[14].Problem1(classification problem)Characterise all trac-table constraint languages onfinite domains.2.2.Algebraic structure of problem classesSchaefer’s technique heavily uses the natural representa-tion of Boolean relations by propositional formulas.Such a representation does not exist for larger domains.Instead, we shall use algebraic properties of relations.In our alge-braic definitions we mainly follow[23].Definition3An algebra is an ordered pairsuch that is a nonempty set and is a family offinitary operations on.The set is called the universe of,the operations from are called basic.An algebra with afinite universe is referred to as afinite algebra.Every constraint language on a set can be assigned an algebra with the universe.Definition4An-ary operation preserves an-ary re-lation(or is a polymorphism of,or is invariant un-der)if,for any, the tuple belongsto as well.The set of all polymorphisms of a constraint language is denoted;and the set of all relations invariant under all operations from a set is denoted.Given a constraint language,,on,the algebra is called the algebra associated with,and is denoted.Conversely,for anyfinite algebra,there is a constraint language associated with,the language, and the associated problem class. Notice that is the largest constraint language such that,see,e.g.[27,31].A connection between the complexity of a constraint language and the associated algebra is provided by the following theorem.Theorem2([17])A constraint language on afinite set is tractable[NP-complete]if and only if is tractable[NP-complete].Informally speaking,Theorem2says that the complexity of is determined by the algebra.We,therefore,make the following definition:for a constraint language,the alge-bra is said to be tractable[NP-complete]if is tractable [NP-complete].In[18,19],Jeavons and coauthors have identified cer-tain types of algebras which give rise to tractable problem classes.Definition5Let be afinite set.An operation on is calleda projection if there is such thatfor any;essentially unary if,for some unary operation,and any;a constant operation if there is such that,for any;idempotent if for any.a semilattice operation1,if it is binary idempotent andfor any satisfies the following two condi-tions:(a)(Associativity),(b)(Commutativity);a majority operation if it is ternary,and,for any;affine if where are the operations of an Abelian group.For afinite algebra,an operation from is said to be a term operation2of.If is a constraint language, the term operations of are the polymorphisms of. Proposition1([18,19])If afinite algebra has a term operation which is constant,semilattice,affine,or major-ity,then is tractable.The2-element algebras associated with Schaefer’s six types of constraint languages have the constant term operation or in cases(1),(2);the semilattice term operation or in cases(3),(4);the majority term operationin case(5);and the affine term operation in case(6).An algebra is said to be a-set if every term operation is essentially unary and the corresponding unary operation is a permutation.Proposition2([18,19])Afinite-set is NP-complete. By combining those two results,and the classical result of E.Post[28],the algebraic version of Schaefer’s theorem can be derived[8].Theorem3(Schaefer)A constraint language on a2-element set is tractable if is not a-set.Otherwise is NP-complete.2.3.Algebraic constructions and the complexity ofconstraint languagesCertain transformations of constraint languages preserve the complexity,and may lead to languages with certain de-sirable properties.Let be a constraint language on,anda unary polymorphism of such that. By we denote the set where;and by the set.If is a unary operation whose range is minimal among ranges of unary operations from with the property, then the constraint language will be denoted. Proposition3([8])Let be a constraint language on, and a unary operation on with a minimal range and such that.Then is tractable [NP-complete]if and only if is tractable[NP-complete]. If and satisfy the conditions of Proposition3then the algebra is idempotent,that is,all its basic operations are idempotent.The complexity of the constraint language does not depend on the choice of,and we shall denote every such language by.Due to Theorem2and Proposition3the study of the complexity of constraint languages is completely reduced to the study of properties of idempotent algebras.Definition6Let be an algebra,and a sub-set of such that,for any(-ary),and for any,we have.Then the al-gebra consists of restrictions of operations from onto,is called a subalgebra of.The universe of a subalgebra of is called a subuniverse of.An equivalence relation is said to be a con-gruence of.The-class containing is denoted, the set is said to be the factor-set, and the algebra,where,is said to be thefactor-algebra.Proposition4([8])Let be a tractable constraint lan-guage on,a subuniverse of,and an equiva-lence relation invariant under.Then(1)the subalgebra,for a natural number,we will denote the set.Let be an-ary relation,and;Definition7The algebrasatisfies the partial zero property if there exist a set of its subuniverses,,and for each,such that(a);(b)for any relation,and any,there is withifotherwisesatisfies the splitting property if any(-ary)relationcan be represented in the form, contains the tuple withifif andif andsatisfies the-semisplitting property if,for any ir-reducible(-ary)relation,we have(i)procedure until the instance stays unchanged:solve all re-stricted problems involving variables,and then remove from each constraint all tuples such thatis a part of no partial solution for a certain-element set of variables.This procedure is called‘establishing-minimality’,and is said to be the-minimal instance associated with.Definition9A class of constraint satisfaction problems is said to be of width3if any problem instance from has a solution if and only if the-minimal problem associ-ated with contains no empty constraint.Every class offinite width is tractable,because,assuming fixed,establishing-minimality takes polynomial time. 4.2.Multi-sorted constraint satisfaction problemsIn[5],an algebraic approach to a generalised version of the constraint satisfaction problem was developed.In this generalised version every variable is allowed to have its own domain.In this paper we need the notion of multi-sorted constraint satisfaction problem,and some results from[5] as an auxiliary tool.Definition10For any collection of sets, and any list of indices,a subset of,together with the list, will be called an(-ary)relation over with signature.For any such relation,the th compo-nent of the signature of will be denoted.Definition11The multi-sorted constraint satisfaction problem is the combinatorial decision problem with Instance:a quadruple where is a set of vari-ables;is a collection of sets of values[domains];is a mapping from to, called the domain function;is a set of constraints.Each constraint is a pair,whereis a tuple of variables of length, called the constraint scope;is an-ary relation over with signature,called the constraint relation.Question:does there exist a solution,i.e.a function, from to,such that,for each variable,,and for each constraint, with,the tuplebelongs to?It is possible to introduce the algebraic structure of the multi-sorted CSP in a very similar way to the usual one.Corollary1If a3-element idempotent algebra satisfies (N O-G-S ET)then any2-valued problem instance from can be solved in polynomial time.Most of the‘good’properties of relations allow us,first,to reduce an arbitrary problem instance to a2-valued problem instance,and,second,to solve the obtained instance as amulti-sorted problem instance by making use of the algo-rithms from[5].4.3.Why‘good’properties are good4.3.1.Relations invariant with respect to a special oper-ation.In condition(8)of Theorem5,the tractability offollows from Proposition1.In(9),is of width3,as is proved in[4].The result of[2]states that anyfinite alge-bra with a Mal’tsev operation is tractable,and the solutionalgorithm is very similar to algorithms from linear algebra.4.3.2.The partial zero property.In this case any prob-lem instance can be reduced to a2-valued one.Indeed,if satisfies the partial zero property,and a1-minimal probleminstance has a solution,then also has the solution such that if, and otherwise.Thus,to solve we assignthe value to each variable with. Since,the obtained problem instance is2-valued.4.3.3.The replacement property.In this case any prob-lem instance can also be reduced to a2-valued one.If satisfies the-replacement property,and a1-minimal problem instance has a solu-tion,then the mapping such thatif,,and otherwise, is a solution to.We therefore,may reduce to a2-valued problem instance where for eachthere is such that if and only if and whenever.4.3.4.The extendibility property.We prove that in this case is of width3.Suppose that satisfies the -extendibility property,and take a3-minimal problem in-stance.An easy proof of the following lemma is left to the reader.Lemma1Let.There is such that,for any.Finally,the-extendibility property of implies that the mapping whereifif oris a solution to.4.3.5.Rectangularity and semirectangularity.Suppose that is-rectangular or-semirectangular,and.We show that any problem instance in this case can be reduced to a2-valued one.Take a problem instance.Without loss of generality we may assume that is3-minimal.Let denote the set of all variables with.Let be the equivalence relation on generated by. Notice that,since is3-minimal,for any,any such that,and any,ei-ther,or.Repeat the follow-ing procedure until the obtained problem instance coincides with the previous one.For each class of,solve the problemwhere,for each,we make the constraint.If,for a class of,the problem instancehas no solution then,for each constraint, remove from all the tuples such that for some.Replace the obtained problem instance with the asso-ciated3-minimal problem instance.Remove from those variables for which no longer equals or.Calculate the relation for the obtained problem instance and the set.Obviously,the obtained problem instance has a solution if and only if the original problem instance has.Supposefirst that is-rectangular.Then,if has no empty constraint,then there is a solution to such that whenever.Indeed,letbe the classes of,and a solution to,It is not hard to see that if has a solution,then has a solution(see also[4]).Let be a solution to,andsolutions to.The mapping whereifif,,andif,,andis a solution to.Indeed,take a constraint. Since for eachis the majority opera-tion,and satisfies the-semisplitting property.A prob-lem instance is said to be irreducible if every constraint relation is irreducible.Every3-minimal problem instancecan be reduced to an equivalent irreducible problem instance in polynomial time.Indeed,denote by the binary relation on such that if and only if is the graph of a bijec-tive mapping.Since is3-minimal,,for any,where denotes the composition of binary relations;hence,is an equivalence relation.Choose a representative from each class of,and let be the set of the representatives.Then, for no pair of variables,is the graph of a bijective mapping,and for any,there issuch that is the graph of a bijective mapping.We transform in three steps.For each constraint and any,replacewith where,andis the representative of the-class containing.For each constraint and each,re-place with.Replace every constraint with.Now,let be a3-minimal ir-reducible problem instance,and consider the instancewhere,for each,there iswith for all such that .The problem instance is2-valued,there-fore,we just have to show that and are equivalent.Clearly,if has a solution then has a solution.Con-versely,let have a solution,and set,and.By condition(i)of the definition of the semisplitting property,has a solution if and only if both and have.Since,the instance has a solution.By condition(ii),for any,where denotes the set of partial solutions to for.Moreover,since is3-minimal,for any every such partial solution can be extended to a solution from.(The last property is called strong2-consistency[18].)Recall that any relation such that is invariant with respect to a majority operation,in particular,all the constraint rela-tions of satisfy this condition.By Theorem3.5of[18], if for any then strong2-consistency ensures existence of a solution to.5.Recognising tractable casesFrom a practical perspective,we need a method that al-lows us to recognise if a given constraint language is tractable.The following problem is,therefore,very tempt-ing.T RACTABLE-L ANGUAGE.Is a givenfinite constraint lan-guage on afinite set tractable?Schaefer’s Dichotomy Theorem[29]does not solve this problem satisfactorily.Indeed,it can be easily verified if a relation satisfies conditions(1)or(2)of Theorem1,how-ever,the way of recognising if one of conditions(3)–(6) holds is not obvious(see also[21]).Theorem3,the alge-braic version of Schaefer’s result,fills this gap:to check the tractability of a Boolean constraint language one just has to check whether all relations from the language are invari-ant under one of the6Boolean operations corresponding to conditions(1)–(6).In the general case,such a method can hopefully be de-rived from a description of tractable algebras.For example, in[6],a polynomial time algorithm has been exhibited that checks if afinite algebra,whose basic operations are given explicitely by their operation tables,satisfies(N O-G-S ET). Therefore,if Conjecture1holds then the tractability of an algebra can be tested in polynomial time.In particular,this algorithm is valid in the case of3-element algebras.However,this algorithm does not solve T RACTABLE-L ANGUAGE even under the assumption of Conjecture1, because in this problem we are given a constraint language, not an algebra.Actually,we need to solve the problemN O-G-S ET-L ANGUAGE.Given afinite constraint language on afinite set,does the algebra satisfy(N O-G-S ET)?By the results of[6],this problem is NP-complete.How-ever,its restricted version remains tractable.N O-G-SET-L ANGUAGE().Given afinite constraint lan-guage on afinite set,,does the algebra satisfy(N O-G-S ET)?This means that the tractability of a constraint language on a3-element set can be tested in polynomial time.Theorem7There is a polynomial time algorithm that given a constraint language on a3-element set determines if is tractable.An example of such an algorithm is provided by the gen-eral algorithm from[6].That algorithm employs some deep algebraic results and sophisticated constructions.In the par-ticular case of a3-element domain,we may avoid using hard algebra,and apply a simpler and easier algorithm.To this end,notice that if a3-element idempotent algebra has a2-element subuniverse or a nontrivial congruence, and there is a term operation which is not a projection on the subalgebra or the factor-algebra,then witnesses that the algebra itself is also not a-set.We,therefore,have two cases to consider.C ASE1.has no2-element subuniverse,and no proper congruence.Such an algebra is said to be strictly simple.There is a com-plete description offinite strictly simple algebras[32].In particular,if a strictly simple algebra satisfies(N O-G-S ET) then one of the following operations is its term operation: a majority operation,the affine operation of an Abelian group,or the operationifotherwisefor some element.C ASE2.has either a2-element subalgebra,or a proper congruence.In this case,satisfies(N O-G-SET)if and only if every2-element subalgebra and every proper factor-algebra(which is also2-element)is not a-set.In its turn,the latter con-dition holds if and only if,for any2-element subuniverse of,and any congruence,there is a polymorphism of such that()is one of the Boolean operations,,,;–if not then output“NO”.Output“Yes”.This algorithm is polynomial time,because the hardest step,finding the set,requires inspecting of all ternary operations on a3-element set;and,since their number does not depend on,takes cubic time.Recognising which of the10properties a tractable al-gebra satisfies also can be completed in polynomial time. However,to establish this requires a more detailed study of the set of ternary polymorphisms,see[3].6ConclusionIn fact,Theorem5implies a stronger result than that claimed in Theorem4.The difference appears when consid-ering infinite constraint languages satisfying the conditions of Conjecture1.Theorem4claims that,for anyfinite sub-set of such a language,there is its own polynomial time algorithm solving,and for different sub-sets the corresponding algorithms might be quite different.Theorem5yields a uniform polynomial time algorithm that solves any problem from the class associated with the con-straint language.Moreover,from the proof of Theorem5a general algorithm can be derived,which solves any problem instance on a3-element set provided that, for some tractable.Note that Theorem4is proved by a‘brute force’method, that is,by analysing a large number of operations which provide the condition(N O-G-S ET).We believe that devel-opment of algebraic tools and more subtle usage of results from universal algebra will make it possible to obtain di-chotomy results for larger domains,and eventually,for an arbitraryfinite domain.References[1]J.Allen.Natural Language Understanding.Benjamin Cum-mihgs,1994.[2] A.Bulatov.Mal’tsev constraints are tractable.TechnicalReport PRG-RR-02-05,Computing Laboratory,University of Oxford,Oxford,UK,2002.[3] A.Bulatov.Tractable constraints on a three-element set.Technical Report PRG-RR-02-06,Computing Laboratory, University of Oxford,Oxford,UK,2002.[4] A.Bulatov and P.Jeavons.Tractable constraints closed un-der a binary operation.Technical Report PRG-TR-12-00, Computing Laboratory,University of Oxford,Oxford,UK, 2000.[5] A.Bulatov and P.Jeavons.Algebraic approach to multi-sorted constraints.Technical Report PRG-RR-01-18,Com-puting Laboratory,University of Oxford,Oxford,UK,2001.[6] A.Bulatov and P.Jeavons.Algebraic structures in combina-torial problems.Technical Report MATH-AL-4-2001,Tech-nische universit¨a t Dresden,Dresden,Germany,2001. [7] A.Bulatov,P.Jeavons,and A.Krokhin.The complex-ity of maximal constraint languages.In Proceedings of the33rd Annual ACM Simposium on Theory of Comput-ing,pages667–674,Hersonissos,Crete,Greece,July2001.ACM Press.[8] A.Bulatov,A.Krokhin,and P.Jeavons.Constraint sat-isfaction problems andfinite algebras.In Proceedings of 27th International Colloquium on Automata,Languages and Programming—ICALP’00,volume1853of Lecture Notes in Computer Science,pages272–282.Springer-Verlag,2000.[9]N.Creignou,S.Khanna,and plexity Classi-fications of Boolean Constraint Satisfaction Problems,vol-ume7of SIAM Monographs on Discrete Mathematics and Applications.SIAM,2001.[10]putational Complexity of Problems overGeneralised Formulas.PhD thesis,Department LSI of the Universitat Politecnica de Catalunya(UPC),Barcelona., March,2000.[11]R.Dechter and A.Dechter.Structure-driven algorithmsfor truth maintenance.Artificial Intelligence,82(1-2):1–20, 1996.[12]R.Dechter and I.Meiri.Experimental evaluation of prepro-cessing algorithms for constraint satisfaction problems.Ar-tificial Intelligence,68:211–241,1994.[13]R.Dechter and work-based heuristics for con-straint satisfaction problems.Artificial Intelligence,34(1):1–38,1988.[14]T.Feder and M.Vardi.The computational structure ofmonotone monadic SNP and constraint satisfaction:A study through datalog and group theory.SIAM Journal of Comput-ing,28:57–104,1998.[15]G.Gottlob,L.Leone,and F.Scarcello.A comparison ofstructural CSP decomposition methods.Artificial Intelli-gence,124(2):243–282,2000.[16]P.Jeavons.Constructing constraints.In Proceedings4th In-ternational Conference on Constraint Programming—CP’98 (Pisa,October1998),volume1520of Lecture Notes in Com-puter Science,pages2–16.Springer-Verlag,1998.[17]P.Jeavons.On the algebraic structure of combinatorial prob-lems.Theoretical Computer Science,200:185–204,1998.[18]P.Jeavons,D.Cohen,and M.Cooper.Constraints,consis-tency and closure.Artificial Intelligence,101(1-2):251–265, 1998.[19]P.Jeavons,D.Cohen,and M.Gyssens.Closure properties ofconstraints.Journal of the ACM,44:527–548,1997. [20]P.Jeavons,D.Cohen,and J.Pearson.Constraints and uni-versal algebra.Annals of Mathematics and Artificial Intelli-gence,24:51–67,1998.[21]P.Kolaitis and M.Vardi.Conjunctive-query containment andconstraint put.Syst.Sci.,61:302–332, 2000.[22]V.Kumar.Algorithms for constraint satisfaction problems:A survey.AI Magazine,13(1):32–44,1992.[23]R.McKenzie,G.McNulty,and W.Taylor.Algebras,Latticesand Varieties,volume I.Wadsworth and Brooks,California, 1987.[24]works of constraints:Fundamental prop-erties and applications to picture rmation Sciences,7:95–132,1974.[25] B.Nadel.Constraint satisfaction in Prolog:Complexity andtheory-based rmation Sciences,83(3-4):113–131,1995.[26] B.Nadel and J.Lin.Automobile transmission design asa constraint satisfaction problem:Modeling the kinematiklevel.Artificial Intelligence for Engineering Design,Anaysis and Manufacturing(AI EDAM),5(3):137–171,1991. [27]R.P¨o schel and L.Kaluˇz nin.Funktionen-und Relationenal-gebren.DVW,Berlin,1979.[28] E.Post.The two-valued iterative systems of mathematicallogic,volume5of Annals Mathematical Studies.Princeton University Press,1941.[29]T.Schaefer.The complexity of satisfiability problems.InProceedings10th ACM Symposium on Theory of Computing (STOC’78),pages216–226,1978.[30] E.Schwalb and L.Vila.Temporal constraints:a survey.Con-straints,3(2-3):129–149,1998.[31] A.Szendrei.Clones in Universal Algebra,volume99ofSeminaires de Mathematiques Superieures.Universit´e de M´o ntreal,1986.[32] A.Szendrei.Simple surjective algebras having no propersubalgebras.Journal of the Australian Mathematical Society (Series A),48:434–454,1990.[33]M.Vardi.Constraint satisfaction and database theory:a tu-torial.In Proceedings of19th ACM Symposium on Priciples of Database Systems(PODS’00),2000.。

英语（二）词汇表organizational [,ɔ:ɡənai'zeiʃənəl, -ni'z-] a.组织（上）的goal[ɡəul] n.1.目的，目标；2.得分进球，球门objective[əb'dʒektiv, ɔb-]n.目标，目的；a.1.客观的，真实的；2如实的，无偏见的accomplish [ə'kʌmpliʃ, ə'kɔm-]vt.完成（任务等）predict[pri'dikt] vt./vi.预言；预示accompany[ə'kʌmpəni]vt.1.伴随，陪同； 2.为……伴奏implement['implimənt, 'impliment]vt.实现；完成（任务等）；履行（协定、诺言等）constraint [kən'streint] n.1.强制；2强制因素，制约条件precedent[pri'si:dənt, 'presi-] n.先例，前例simplify['simplifai] vt.简化tendency['tendənsi] n.趋势，倾向managerial[,mæni'dʒiəriəl] a.1.经理的，管理人的；2管理上的，经营上的maker['meikə] n.制造者；制造商achievement[ə'tʃi:vmənt] n.1.完成，达到；2成就，成绩attain[ə'tein] vt.达到；完成optimal['ɔptiməl] a.最适宜的；最理想的suboptimization[sʌb,ɔptimai-'zeiʃən, -mi'z-] n.局部最优化（指使整体目标中的某个选定目标圆满实现）trade-off n.1.（对不能同时兼顾的因素）权衡；2物物交换argue['ɑɡju:] vt./vi.争辨，争论，辩论；vt.1.说服；2用辩论证明budget['bʌdʒit]n.预算；vt.1.把……编入预算；2安排，预定scheme[ski:m] n.计划；方案；vt./vi.计划，策划define[di'fain] vt.1.解释，给……下定义；2限定，规定multiple ['mʌltipl] a.多样的，复合的；n.倍数profitability[,prɑfɪtə'bɪlətɪ]n.赚钱，获利correctness[kə'rektnis] n.正确，正确性unintended[,ʌnin'tendid] a.非计划中的，非故意的ongoing['ɔn,ɡəuiŋ, 'ɔ:n-] a.进行中的，前进的entity['entəti] n.1.存在，实体；2统一性skilled [skild] a.熟练的；有技能的in the way 挡路；碍事make a guess at猜测moving ['mu:viŋ] a.1.活动的，移动的；2.动人的，令人感动的sensitive['sensitiv] a.1.敏感的；2.灵敏的，感光的be affected with患有……疾病debate on 关于……进行辩论make request for 要求……be opposed to 反对open up1.打开；2.开办，开辟，开发；3坦诚地或无拘束地谈话take……into account考虑到need for对……的需要opt out of 决定不参加……，决定（从……）中退出have……at heart对某事十分关心conspiracy[kən'spirəsi]n.1.阴谋，密谋；2.阴谋集团，阴谋帮派old-boy ['əuld'bɔi] n.1.老同学；2.（招呼用）老朋友，老弟，老兄network['netwə:k] 1.[纺]网眼织物；2.网状物，网络escalator['eskəleitə]n.自动扶梯privilege ['privilidʒ] n.特权；vt.给予……特权profession[prəu'feʃən] n. （尤指脑力劳动或受过专业训练的）职业graduate['ɡrædʒuət, -eit, 'ɡrædjueit, -dʒu-] vi.大学毕业，[美]毕业；vt.[主美]准予……毕业；a.1.毕业的；2.研究生的；n.大学毕业生，[美]毕业生unfair[,ʌn'fεə] a.不公平的，不公正的employment[im'plɔimənt] n.1.使用；2.雇佣；3.职业，工作publish ['pʌbliʃ]vt.1.出版，刊印；2.公布，发表senior ['si:njə] a.1.年长的，年纪较大的；2.地位较高的，资历较深的；3.[英]（大学）高年级的，[美]大学四年级的；n.1.年长者；2资历深者，上级appoint [ə'pɔint] vt.1.任命，委任（as）；2.私营的，私立的；3秘密的，私下的headmaster['hed'mɑ:stə, -mæstə] n.（中学或小学的）校长leading ['li:diŋ] a.1.领导的，指引的；2.最重要的，主要的bias['baiəs]n.偏见；v.[常用被动语态]有偏见（常与against， towards 连用）entry['entri] n.1.进入，入场（权），入会权；2.入口；3.登记，条目，账目merit['merit] n.1.优点，长处；2.功绩，功劳fiercely['fiəsli] ad.1.凶猛地，凶残地；2.猛烈地competitive[kəm'petitiv] a.竞争的；比赛的entrance['entrəns] n.1.进入；2.入口，门口；3.入场，入会，入学additional[ə'diʃənəl] a.附加的，追加的；另外的abolish [ə'bɔliʃ] vt.废除（法律，习惯等）；取消applicant['æplikənt] n.申请人，请求者performance[pə'fɔ:məns] n.1.执行，完成；2.表现，工作性能；3.演出，演奏accessible[ək'sesəbl] a.1.易接近的，能进去的；2.易受影响的（to）；3可理解的（to）elite [ei'li:t, i'li:t] n.[集合名词]精英，杰出人物；a.杰出的，精英的academic[,ækə'demik] a.1.（高等）专科院校的，研究院的，学会的；2.学术的excellence['eksələns]n.优秀，杰出recruit[ri'kru:t] vt./vi.1.征募（新兵），吸收（新成员）；2.聘用，补充；n.新兵；新成员equivalent [i'kwivələnt] a.1.相等的，相同的（to）；2.等价的，等量的，等效的；n.1.等价（物），等量（物）；2.对应词（或对应语）ivy['aivi]n.常青replicate['replikit, 'replikeit] vt.重复；复制elitist [ei'li:tist, i'-] n.1.杰出人物；2.杰出人物统治论者；adj.1.杰出人物的；2.杰出人物统治论的remedial [ri'mi:diəl, -djəl] a.1.治疗的，治疗上用的；2.补救的prime[praim] a.1.最初的，基本的；2.首要的，主要的；3.第一流的，最好的vision['viʒən]n.1.想象力，幻觉；2.视力，视觉；3.眼光classless[/'klɑ:slis/] a.1.无阶级的；2.不属于任何阶级的amount to 1.达到总计；2.相当于，等于on average 平均blame……for为……责备某人by nature 生来，天生，就其本性而言be worth doing 值得做……slavery['sleivəri] n.1.奴隶制度，奴役；2.奴隶身份domestic[dəu'mestik] adj.1.家庭的，家务的；2.国内的，本国的；n.家仆，佣人Briton['britən] n.大不列颠人；英国人statistics[stə'tistiks] n.1.统计数字，统计资料；2.[用作单]统计学diplomat['dipləmæt] a.外交家；外交官abroad[ə'brɔ:d]ad.到国外；在国外exploit['eksplɔit, ik's-] vt.1.开发，开采；2.利用；3.剥削abuse [ə'bju:z, ə'bju:s]vt./n.1.滥用，妄用；2.虐待，凌辱campaign[kæm'pein]n.1.战役；2.运动，参选活动；v.参加运动，参加竞选活动sexually['sekʃuəli]ad.在性方面passport ['pɑ:spɔ:t, 'pæs-] n.护照Filipino [fili'pi:nəu] n.1.菲律宾人；2菲律宾语；a.菲律宾人的；菲律宾的maid[meid] n.1.少女；2侍女，女仆execute['eksikju:t] vt.1.实行，执行，完成，贯彻；2.将……处死convict[kən'vikt] vt.1.证明……有罪（of）；2.宣判；n.罪犯despite[di'spait] prep.尽管，任凭guilt[ɡilt] n.1.有罪；2.内疚deserving[di'zə:viŋ] a.应得的，值得的（of）Saudi['sɔ:di; sɑ:'u:di; 'saudi]n.沙特阿拉伯人；a.沙特阿拉伯的，沙特阿拉伯人的，沙特阿拉伯语的Breadwinner['bred,winə] n.养家糊口的人shelf[ʃelf] n.（壁橱，书橱内）搁板；架子minimum ['miniməm] n.最小量；最低限度；a.最小的；最低的；最少的employee[,emplɔi'i:, em'plɔii:]n.雇员，雇工leaflet['li:flit] n.1.小叶，嫩叶；2.传单，活页incidence['insidəns] n.1.影响程度，影响范围；2. 发生率immigrant['imiɡrənt] a.（从国外）移民的，侨民的；n.移民，侨民status['steitəs, 'stæ-] n.1.情形，状况；2.地位，身份kingdom['kiŋdəm] n.1.王国；2.领域concession [kən'seʃən]n.1.让步；2.特许权；3.租界，租界地immigration [,imi'ɡreiʃən]n.移居；外来的移民foreigner['fɔrinə]n.外国人deport[di'pɔ:t] vt.驱逐出境bring over 把……带来；使转变convict…of证明……有罪，宣判……有罪be deserving o f 值得；应得be supposed to 应该gang[ɡæŋ] n.1.一队，一族；2.（囚犯，歹徒等）一群，一帮eyewitness['ai,witnis] n.目击者；见证人unison ['ju:nizən] n.一致；协调interstate ['intəsteit, intə's-] a.[主美]州际的BBC 英国广播公司Correspondent[,kɔ:ri'spɔndənt] n .1.对应物；2.新闻通讯员，记者，通信者shackle ['ʃækl]n.1.[常pl.]镣铐；2.[pl.]束缚，枷锁ditch [ditʃ] n.沟，沟渠，vt./vi.开渠，筑渠weed [wi:d] n.1.杂草，野草；2.水生植物；vt.除草，拔草deny[di'nai] vt.1.否定，否认；2.拒绝接受，拒绝给予re-introduction[,riɪntrə'dʌkʃən] n.重新采用，重新引入gap[ɡæp]n.裂口，裂缝toilet['tɔilit]n.盥洗室；厕所circus['sə:kəs] n.1.马戏团，杂技团；2.马戏场，杂技场degrade['di'ɡreid]vt.1.降级，贬低；2.堕落；3.退化plantation[plæn'teiʃən] n.1.种植园，大农场；2.植树造林spokesman ['spəuksmən] n.发言人；代言人racist['reisist] n.种族主义者；a.种族主义的；种族歧视的racial ['reiʃəl] a.种族的inhumane[,imhju:'mein] a.不人道的，残忍的ineffective [,ini'fektiv] a .无效的，不起作用的civil ['sivəl] n.1.国民的，民用的；2.国内的，民间的union['ju:niən] n.1.工会，协会；2结合，联合liberty ['libəti] n.1.自由，自由权；2.冒昧，失礼；3.[常pl.]特许权，特权punishment['pʌniʃmənt] n.1.处罚，罚，刑罚；2.折磨，损害disaffection[,disə'fekʃən] n.不满argument['ɑ:ɡjumənt]n.1.争论，辩论；2.论据，理由watch over看守，照管，监视in unison 完全一致地call up 1.打电话；2使想起，使忆起blues[blu:z] n.1.[用作单或复]布鲁斯（源于美国南部黑人之中抑郁伤感的曲调）；2.慢四步舞rock'n'roll ['rɔkən'rəul]n.摇滚乐，摇滚舞folk[fəuk]n.1.人们；2.[口]家属，亲属；a.民间的musician[mju:'ziʃən] n.音乐家；作曲家transformation [,trænsfə'meiʃən, ,trænz-, trɑ:n-] n.1.变化，转化；2改造，改革rhythmic ['riðmik, 'riθ-] a.有韵律的；有节奏的musically['mju:zikəli] ad.在音乐方面；好听地；悦耳地distinct [dis'tiŋkt] a.1.与其他不同的，独特的；2.明显的consciousness['kɔnʃəsnis]n.意识，知觉；觉悟youthful['ju:θful] a.1.年轻的；2.朝气蓬勃的anti-war ['ænti'wɔ:] a.反战的sentiment['sentimənt] n.1.感情，情绪；2.感伤spontaneous[spɔn'teiniəs] a.1.自发的，本能的，自动的；2.出自自然的originate[ə'ridʒəneit] vi./vt.发源；发生，发起imitator['imiteitə（r）] n.模仿者Negro['ni:grəu] n.黑人；a.黑人的Eclecticism [e'klektisizəm] n.折衷主义synthesis['sinθisis] n.结合，合成jazz [dʒæz] n.爵士乐readily['redili]ad.1.乐意地；2很快地，容易地limitless['limitlis] a.无限制的，无限的instrument['instrumənt, 'instrə-, -ment] n.1.仪器；2.乐器electronic[,ilek'trɔnik] a.电子的amplifier['æmplifaiə] n.放大器guitar[ɡi'tɑ:] n.六弦琴，吉他electronics[,ilek'trɔniks] [复]n.[用作单]电子学studio['stju:diəu, 'stu:-]n.1.（艺术家的）工作室；2.（无线电，电视）播音室，演播室；3.电影制片厂penetrating['penitreitiŋ] 1.穿透的，贯穿的；2.深刻的，透彻的thereby[,ðεə'bai, 'ðεəbai]ad.由此，从而passive ['pæsiv] a.1.被动的；2.消极的participant[pɑ:'tisipənt] n.参加者；a.参与的multimedia[,mʌlti'mi:diə] a.1.多种手段的；2.多媒体的；同时使用形、光、声效果的；n.多媒体，多媒体的使用ballroom['bɔ:lru:m] n.舞厅lighting['laitiŋ]n.照明，照明设备take place 发生take over 1.接管，接任；2.把……从一处运到另一处take on 1.具有；2.担任（工作等）；3.雇佣composer[kəm'pəuzə] n.作曲家inspire[in'spaiə]vt.1.鼓舞；2.使产生灵感fruitful['fru:tful] a.有成果的，有收获的output['autput, ,aut'put]n.1.产量；2.输出theme [θi:m]n.1.题目，主题；2.主旋律invariably[in'vɛəriəbli] ad.不变地improvise['imprəvaiz]vt.1.即兴创作；2.临时准备，临时凑成symphony['simfəni] n.1.交响曲，交响乐；2.交响乐队，交响音乐会handle ['hændl] n.柄，把手；vt.1.拿，弄；2.运用，操纵3.经营，管理constructive [kən'strʌktiv] a.建设的，建设性的creative[kri'eitiv] a.创造性的notebook['nəutbuk]n.笔记本preliminary[pri'liminəri] a.预备的；初步的；n.初试；预赛painstaking['peinz,teikiŋ]] a.苦干的；费力的traditionalist [trə'diʃənəlist]n.传统主义者；因循守旧者thematic[θi'mætik, θi:-] a.1.题目的，主题的；2.主旋律的conception[kən'sepʃən] n.概念，观念well-established['weli'stæbliʃt]a.1.固定下来的；2.得到确认的temper ['tempə] vt.1.[冶]使回火，锻炼；2.调合well（-）tempered ['wel'tempəd] 1.脾气好的；2.（键盘乐器）调到平均律的clavichord ['klævikɔ:d] n.[音]击弦古钢琴mold [məuld] n.模子；模型；vt.用模子做，浇铸sake[seik]n.缘故completeness[kəm'pli:tnis] n.1.完整，圆满；2.完成，结束summarize['sʌməraiz] vt./vi.概述，总结diversified [dai'və:sifaid, di-] a.多样化的conventional[kən'venʃənəl] a.1.惯例的，常规的；2.（艺术等）因袭的experimental[ek,speri'mentəl, ek's-] a.实验的；经验的harmony['hɑ:məni] n.1.协调，和谐；2.融洽，一致sonority ['səu'nɔ:rəti, -'nɔ-] n.响亮，洪亮evident['evidənt] a.明显的，明白的in other words 换句话说in a sense 在某种意义上at a stretch连续不断地serve as 适合belong in 应归入（类别、范畴等）in advance 1.在前面；2.预先It goes without saying不言而喻，理所当然for the sake of 为了……之好处；为了……的目的efficiency[i'fiʃənsi] n.1.效率；2.功效，效能，实力robotics [rəu'bɔtiks]n.[用作单]机器人学，机器人技术robot['rəubɔt, -bət, 'rɔbət] n.机器人；自动控制装置increasingly[in'kri:siŋli]ad.不断增加地prevalent['prevələnt] a.流行的，普通的automotive[,ɔ:təu'məutiv] a.1.自动的，机动的；2.汽车的weld[weld] vt./n.焊接spray[sprei] n.1.浪花，水花；2.喷雾，喷雾状物；vt.喷；向……喷射；喷涂；vi.喷；溅散cast [kɑ:s, kæst]vt.1.投，扔，抛，掷；2.投射（光、影，视线等）（on，at）；3.浇铸，铸造；n.1.投，掷；2.模具；3.演员（阵容）frame[freim]n.构架，框架install [in'stɔ:l]vt.安装appliance [ə'plaiəns] n.1.应用，适用；2.用具，器械calculator ['kælkjuleitə] n.1.计算者；2.计算器radioactive [,reidiəu'æktiv] a.[原]放射性的；放射引起的personnel [,pə:sə'nel] n.1.[集合名词]全体人员，全体职员；2.人事（部门）expose[ik'spəuz] vt.1.使暴露，使面临；2.揭露，揭发radiation [,reidi'eiʃən]n.1.放射，发光；2.放射物，辐射线，辐射能reduction[ri'dʌkʃən]n.1.减少，减小；2.降级，降职；3.归纳，归并automatic[,ɔ:tə'mætik] a.1.自动的；2.无意识的，机械的reprogramme['ri：'prəugræm] v.再次（重新）设定程序completion [kəm'pli:ʃən] n.完成，结束；完满specific [spi'sifik] a.1.特有的，特定的；2.具体的，明确的switch [switʃ]n.1.开关，转换器；2.（思路、话题等的）转换；vt.1.转换，改变（思路、话题等）；2.接通……电流（on），切断……电流（off）；vi.转换，变换critical['kritikəl] a.1.批评（性）的，批判（性）的；2.对……表示谴责的，对……感到不满的（of）；3.紧要的，关键性的，危急的digital['didʒitəl] a.1.手指的，指状的；2.数字的，计数的camera['kæmərə] n.照相机，摄影机light-sensitive[,lait'sensitiv] a.光敏的intensity[in'tensəti] n.强烈，剧烈grayscale['grei,skeil] 灰度（使不同黑白比例混合而得从黑到白的一系列色差灰色色调）brightness['braitnis] n.1.明亮，晴朗；2.聪敏，机灵scale[skeil]n.1.刻度，表度；2.规模；3.比例（尺）；4.[pl.]天平，磅秤shade [ʃeid]n.1.荫，阴影；2.遮光物，罩；vt.遮蔽，遮光calculation[,kælkju:leiʃən] n.1.计算，计算结果；2.仔细考虑defective [di'fektiv] a.有缺点的；有缺陷的assemble[ə'sembl] vt.1.集合；2.装配；vi.集合attendant [ə'tendənt] n.1.侍者，服务员；2.出席者fireman['faiəmən]n.消防队员housekeeper['haus,ki:pə]n.管理家务的主妇；女管家expose to 暴露；面临；曝露in that 在于，原因是in between 在中间；每间隔；在……期间in question 正被谈论的plenty of 大量的；丰富的earthquake['ə:θkweik]n.地震warning['wɔ:niŋ] n.警告；警报；a.警告的forecast['fɔ:kɑ:st] vt.1.预测，预报；2.预示giant['dʒaiənt]n.1.巨大；2.巨物，巨大的动物；a.巨大的shift[ʃift]vt./vi.1.替换；转移；2.轮班；n.1.转换，转移；2.轮班fault [fɔ:lt]n.1.缺点，毛病；2.错误，过失；3.[地]断层seismic ['saizmik, 'sais-] a.地震的precede [pri:'si:d, pri-] vt.先于……，比……优先；vi.在前面，居前，领先radon ['reidɔn] n.氡decay [di'kei]vi.1.腐朽，腐烂；2.衰败；3.[原]衰变；vt.使腐朽，使腐烂；n.1.腐朽，腐烂；2.衰败radium ['reidiəm]n.镭underground['ʌndəɡraund]a.1.地下的；2.秘密的，隐蔽的；ad.1.在地下；2秘密地，隐蔽地speculate['spekjuleit] vi.思索；推测（on/upon， about）；vt.1.投机；2.思索，推测subside[səb'said] vi.1.沉淀；2.沉降，下沉；3.平静下来，平息，减退datum['deitəm] 1.资料，材料，2.数据reliability [ri,laiə'biləti] n.可靠性partial ['pɑ:ʃəl] a.1.偏袒的，偏心的，对……偏袒（to）；2.部分的，不完全的up-to-date['ʌptə'deit] a.1.最新的，现代化的；2.直至目前的analyze ['ænəlaiz] vt.分析eastern ['i:stən] a.1.东方的，东部的；2.向东方的，来自东方的work on 1.从事……；2.对……有影响set up 1.设立，建立；2.建立，提出on the alert警戒，处于戒备状态leadership ['li:dəʃip] n.1.领导；2.[总称]领导人员research [ri'sə:tʃ, 'ri:s-] n.研究，调查；vi.调查，研究attach[ə'tætʃ] vt.（to）1.固定住，系；2.附加，隶属；3.把（重点等）放在；4.使喜爱，使依恋possession[pə'zeʃən] n.1.有，拥有；2.[常pl.]占有物；财产satisfaction [,sætis'fækʃən] n.满意，满足relaxation[,ri:læk'seiʃən] n.1.松弛，放松；2.缓和，减轻；3.休养desirable[di'zaiərəbl] a.称心的，合意的，理想的occupation [,ɔkju'peiʃən] n.1.占领；2.占有；ɔ.职业portray [pɔ:'trei, pəu-] vt.描绘；描写；描述urban ['ə:bən] a.城市的，都市的stressful ['stresful] a.紧张的；压力重的loom [lu:m] vi.隐隐呈现；逼近renewal [ri'nju:əl] n.1.更新；2重新开始underlie[,ʌndə'lai]vt.支撑；构成（理论，政策，行为等）的基础acquire [ə'kwaiə]vt.获得，得到recognition [,rekəg'niʃən] n.1.认出；2.承认，公认impart[im'pɑ:t] vt.把……分给；给予（to）positive['pɔzətiv, -zi-] a.1.明确的，确实的；2.积极的，肯定的；3.正的，阳性的motivate['məutiveit] vt.作为…的动机，激发relevant['reləvənt] a.1.贴切的，中肯的；2.与……有关的（to）communicator [kə'mju:nikeitə] n.传播者，传播工作者participation[pɑ:tisi'peiʃən]n.参加，参与attainment[ə'teinmənt] n.1.达到，到达；2.[常pl.]成就，造诣be concerned with 1.关于，涉及；2.忙于……；3.关心，关切attach importance to认为……很重要take to 1.开始从事；2.养成……的习惯3.培养对……的爱好put……to use使用；利用be relevant to 与……有关on the part of就……而言set……as objective把……作为目标elusive[i'lju:siv,-səri] a.1.躲避的；2.难以捉摸的，难以理解的tricky['triki] a.1.狡猾的，耍花招的；2.难以处理的slip[slip]vi.1.滑动，滑过；2.溜，溜走；vt.使滑动；使滑过quicksand['kwiksænd] n.流沙oversupply[,əuvəsə'plai, 'əuvəsə,plai] vt./n.过多供应wayside['weisaid]n.路边；2.路边的flexible['fleksibl] a.1.柔韧的，柔顺的；2.可变通的，灵活的readjustment[,ri:ə'dʒʌstmənt] n.再整理，再调整project['prɔdʒekt, 'prəu, prə'dʒekt] n.1.设计，规划；2.项目；vt.1.方案，计划；2.投射，映射3.使突出appointment[ə'pɔintmənt] n.1.任命；2.约会weekly['wi:kli] a.每周的；一周一次的；ad.每周；每周一次；n.周刊，周报adjustment[ə'dʒʌstmənt]n.调整realistic[,riə'listik, ,ri:-] a.1.现实的，实际的；2.逼真的；3.现实主义的，现实主义者的underestimate[,ʌndə'estimeit] vt.低估；看轻overestimate[,əuvər'estimeit, -'estimət]vt.过高估计；过高评价emergency [i'mə:dʒənsi] n.紧急情况；突发事件routine [ru:'ti:n] n.日常工作；例行手续，常规；2.日常的；例行的；常规的crash [kræʃ] a.紧急的，速成的inflexible[in'fleksəbl] a.1.不可弯曲的，僵硬的；2.不可改变的，固执的adjust[ə'dʒʌst]vt.1.调整，调节；2.校准deem [di:m] vt.认为，相信assignment [ə'sainmənt] n.1.分配，委派；2.任务，（课外）作业freshman['freʃmən] n.1新手，生手；2.大学一年级学生kid[kid]vt./vi./n.1.戏弄，开玩笑；2.欺骗，哄骗faithfully ['feiθfuli]adv忠诚地；如实地temptation [temp'teiʃən]n.引诱，诱惑look ahead to 向前看；展望未来allocate……for分配给……；配给fall by the wayside半途而废，中途退出hang up 1.把……挂起来；2.挂断（电话）；3.延迟，拖延throw off 扔掉；摆脱work out 做出；制定出retention [ri'tenʃən] n.保持；保留distract[dis'trækt] vt.分散（注意，心思等）；使人分心adversely [æd'və:sli] ad.1.相反地；2.不利地，有害地appreciate[ə'pri:ʃieit] vt.1.欣赏，鉴赏；2.正确评价，鉴别；3感激，感谢contrary ['kɔntrəri] a.相反的，相对的，与……相反（to）mislead [,mis'li:d] vt.把……带错路，使……错或做错motivation[,məuti'veiʃən] n.动机；动力inefficient [,ini'fiʃənt] a.无效的；效率低的exceptional [ik'sepʃənəl] a.1.例外的；2.异常的，特殊的hinder ['hində] vt.阻止；妨碍typical['tipikəl] a.典型的，代表性的to date 到目前为止attend to 专心；注意；照顾make the grade 取得成功，达到理想标准fall apart 四分五裂；崩溃be true of 符合于……，对……适用classify [/'klæsifai/] vt.1.把……分类，把……分等级；2.把……列为（as）aged ['eidʒid] a.年老的，老的northwestern[,nɔ:θ'westən] a.1.在西北的，向西北的；2.来自西北的approximate [ə'prɔksimit，ə'prɔksimeit] a.近似的，大约的；vt.1.近似，接近；2.使接近；vi.接近（to）paradox ['pærədɔks] 1.似非而可能是的论点；2.自相矛盾的话proportion [prəu'pɔ:ʃən] n.比率，比例；vt.使成比例，使相称dependency [ di'pendənsi] n.从属；依赖（on）advantageous [,ædvən'teidʒəs] a.有利的，有助的liability [,laiə'biləti] n.1.责任，义务；2.[pl.]债务，负债；3.不利条件，妨碍的人（或物）inactive [in'æktiv] a.不活动的；不活跃的appreciation[ə,pri:ʃi'eiʃən] n.1.欣赏，鉴赏；2.正确评价；3.感激，感谢salient['seiljənt, -liənt] a.1.突出的，凸起的；2.显著的resettlement[ri'setlmənt;]n.重新定居，重新安置acknowledge[ək'nɔlidʒ] vt.1.承认；2.表示感谢fore [fɔ:] ad.在前面；a.1.先时的，先前的；2.在前部的；n.前部gathering ['ɡæðəriŋ] n.1.聚集；2.集会birthrate ['bə:θreit]n.出生率elsewhere [,els'hwεə] ad.在别处；向别处demography[di:'mɔɡrəfi] n.人口统计学alter['ɔ:ltə] vt./vi.改变，改动experiential[ik,spiəri'enʃəl] a.经验的；凭经验的continued[kən'tinju:d] a.继续的，连续的lengthen['leŋθən] vt.使延长；vi.变长，延伸wealthy ['welθi] a.富裕的；丰富的neglect [ni'ɡlekt] vt.1.忽视，忽略；2.疏忽；n.忽略；疏忽expectation[,ekspek'teiʃən] n.1.期待；2.估计寿命slippery ['slipəri] a.1.滑的；2.圆滑的demographer [di:'mɔɡrəfə] n.人口学家revision[ri'viʒən]n.修订，修改upwards ['ʌpwədz] ad.向上；趋向上升approximate to与……接近to the fore 1.在前面，到前面；2.在显著地位resistance to 对……的阻力esteem [i'sti:m] vt./n.尊敬，尊重cope[kəup] vi.对付，妥善处理（with）parenting ['pεərəntiŋ] n.父母对孩子的养育tone[təun]n.1.音调，音色；2.腔调，语气；3.[语]声调，语调infant'infənt]n.婴儿，幼儿；a.婴儿的，幼儿的lovable['lʌvəbl] a.可爱的，讨人喜欢的manageable['mænidʒəbl] a.易管理的unlovable[,ʌn'lʌvəbl] a.不可爱的；不讨人喜爱的worthless['wə:θlis] a.1.无价值的，无用的；2.不足道的，不可取的ultimately ['ʌltimətli] ad.最后，最终地self-defeating [,selfdi'fi:tiŋ] a.1.自我挫败的；2.有违被衰的crisis ['kraisis] n.1危机；2.决定性时刻withdraw[wið'drɔ:, wiθ-]vt.1.收回，提取；2.撤退，撤销；vi.1.撤退，退出；2.退缩，逃避现实inconsiderate [,inkən'sidərət] a.不替别人考虑的；不体谅人outcome ['autkʌm]n.1.结果，结局；2.出路，出口reinforcement[,ri:in'fɔ:smənt] n.增强，加固；强化tangible['tændʒəbl] a.1.可触摸的，可感知的；2.确实的，真实的attribute[ə'tribju:t, 'ætribju:t]n.1.属性，特征；2.[语]定语；vt.把……归因于（to）fold[fəuld] vt./vi.折叠；对折； n.褶（痕）appropriate [ə'prəuprieit, ə'prəupriət] a.适合的，恰当的，相宜的cope with 对付；处理no other……than 1.除……外没有，只有；2.正是，就是take advantage of 1.利用；2.占……便宜act out 1.将……表演出来；2.（用行动）表示出来election [i'lekʃən] n.选举；选举权presidential [,prezi'denʃəl] a.总统（或校长）的，总统（或校长等）职务的winner['winə] n.获胜者，优胜者；成功者republican [ri'pʌblikən] a.1.共和国的；2.[R-]（美国）共和党的；n.1.共和主义者；2.[R-]共和党党员democratic[,demə'krætik,-kəl] a.民主的，民主主义的nominee [,nɔmi'ni:] n.被提名者；被任命者vote [vəut] n.1.选举，投票；2.票，选票；vi.投票，选举certainty ['sə:tənti] n.一定；必定nomination [,nɔmi'neiʃən] n.提名；任命loyalty ['lɔiəlti] n.忠诚；忠心decline[di'klain]vi.1.下倾，下降；2.衰退，衰落；3.谢绝，拒绝；vt.拒绝，谢绝；n.1.下倾，下降；2.衰退，衰落democrat['deməkræt] n.1.民主主义者，民主人士；2.[D-]民主党党员voter['vəutə] n.选举人，投票人strategically [strə'ti:dʒikəli] ad.战略上地，颇具策略地pursue [pə'sju:, -'su:] vt.1.追赶；2.追求，寻求；3.进行，从事impact ['impækt, im'pækt] n.1.冲击，碰拦；2.效果，影响；vt.装紧，压紧headquarters [,hed'kwɔ:təz][复]n.1.司令部，指挥部；2.（机构，企业）总部，总店economy[i'kɔnəmi] n.1.经济；2.节约strategist['strætidʒist] n.战略家rating['reitiŋ] n.1.等级，规格；2.评定结果，（电视）收视率poll[pəul] n.1.选举，投票；2.民意测验；vt1.得到选票；2.对……进行民事测验；vi.投票stir[stə:] vt.1.搅拌，搅动；2.激起，打动；vi.微动；活动；n.惊动；轰动strategy['strætidʒi] n.战略；策略constitutional [,kɔnsti'tju:ʃənəl] a.1.宪法上规定的；2.组成的，构成的provision [prəu'viʒən] n.1.供应，供应品；2.条款，规定；3.[常pl.]给养，口粮electoral [i'lektərəl] a.选举的representation [,reprizen'teiʃən] n.1.描写，表现；2.代表，代理congress['kɔŋɡres, kən'ɡres]n.1.（代表）大会；2.国会，议会；3.[C-]（美法等的）参议院，上院House [haus, hauz] n.[英]议院district ['distrikt] n.1.区，行政区；2.地区，区域representative [,repri'zentətiv] n.代表，代表人；a.典型的，有代表性的presidency ['prezidənsi]n.1.总统（或校长，会长，行长等）职务（或职权，任期）；2.管辖overwhelming[,əuvə'hwelmiŋ] a.压倒之势的stand no chance 没有可能；没有希望identify……as把……看作impact on 对……之影响contest ['kɔntest, kən'test] n.1.竞争，比赛；2.争夺，竞争；3.争论，争辩rivalry ['raivəlri] n.竞争；对抗dozen ['dʌzən] n.1.一打，十二个；2.十来个，十几个nominate ['nɔmineit, 'nɔminət, -neit]vt.1.提名；2.任命；3.命名electorate [i'lektərət] n.全体选民；选区inevitably[in'evitəbli]ad.不可避免地，必然地dominance['dɔminəns,-nənsi] n.优势，控制，统治assault[ə'sɔ:lt] n.1.攻击，袭击；2.（军）冲击，突击，强击parliamentary[,pɑ:lə'mentəri] a.议会的，国会的congressman ['kɔŋɡresmən] n.（美）国会议员statistically[stə'tistikli] ad.在统计方面dominant['dɔminənt] a.占优势的；支配的majority[mə'dʒɔriti] n.1.多数，大半；2.多数党，多数派automatically[,ɔ:tə'mætikəli]ad.自动地；习惯性地competitor [kəm'petitə] n.竞争者；对手running['rʌniŋ] n.1.跑，赛跑；2.竞选inevitable [in'evitəbl] a.不可避免的，必然（发生）的peaceful ['pi:sful] a.1.平静的，安宁的；2.和平的，和平方式的transfer [træns'fə:] vt.1.转移，传输；2调动；3.改变；vi.1.转移，转学；2.换车；换船；n.转移，传输，变换overturn [,əuvə'tə:n, 'əuvətə:n] vt./n.1.打翻，使翻过来；2.推翻，颠覆，毁灭；vi.翻身；倒下foolproof ['fu:l,pru:f] a.1.连傻子都懂的；2.不会出毛病的； 3.有安全装置的monopoly[mə'nɔpəli] n.垄断；专卖opposition [,ɔpə'ziʃən] n.1.反对，反抗；2.对立，意见相反monopolize [mə'nɔpəlaiz] v.垄断；专卖moderation[,mɔdə'reiʃən] n.1.温和，适度；2.缓和，减轻legislation[,ledʒis'leiʃən] n.1.立法；2.法律，法规temporarily ['tempərərili, ,tempə'rεə-]ad.暂时地，临时地break up 打碎；结束；驱散；散开；分解in the running 参赛，参加竞选in power 掌权的，执政的out of power丧失权力in favour of 1.赞成，支持；2.为……的利益，有利于；3.支付给come into power 上台；开始掌权carry on 1.经营，进行；ɑ.继续anaesthetics[,ænis'θetiks] n.麻醉学vaccine ['væksi:n]n.牛痘苗；疫苗；a.牛痘的；疫苗的diabetes [,daiə'bi:ti:z] n.糖尿病developmental [di,veləp'mentəl] a.1.发展的，开发的；2.促使成长的，起改进作用的disorder [dis'ɔ:də] n.1.混乱；2.失调，紊乱；vt.使混乱；使失调irrelevant[i'reləvənt] a.不相干的，离题的，与……不相干（to）misleading[,mis'li:diŋ] a.引入歧途的；使人误解的irresponsible[,iri'spɔnsəbl] a.无责任感的，不负责任的unethical[ʌn'eθikl] a.不合伦理的；不合道德的thalidomide [θə'lidəmaid] n.[药]萨立多胺（原用作中枢神经镇静剂，因有造成胎儿缺肢畸形的副作用，已被禁用）replacement[ri'pleismənt] n.1.复位，复职；2.替换，代替refinement[ri'fainmənt] n.精炼，精制simulate['simjuleit]vt……假装，冒充；ɑ.模仿，模拟cell [sel] 1.细胞；2.小房间，单人牢房toxicity [tɔk'sisəti] n.毒性eventual[i'ventʃuəl] a.最后的，结局的dose[dəus] n.（一次）剂量replace [ri'pleis]vt.1.把……放回（原处），使恢复（原职）；2.更换，以……替代tube [tju:b, tu:b] n.1.管，软管；2.电子管，真空管；3.[英]地铁partly ['pɑ:tli] ad.部分地；在一定程度上polio ['pəuliəu]n.[医]脊髓灰质炎，小儿麻痹症biomedical[,baiəu'medikəl] a.生物医学的ethics ['eθiks] n.[pl.]1.[用作单]伦理学；2.伦理观，道德标准undergo [,ʌndə'ɡəu] vt.经历，经受；忍受suitable['sju:təbl] a.合适的；适当的rabbit ['ræbit] n.兔litter ['litə]n.1.（供动物睡眠或植物防冻的）干草；2.杂乱无章；3.（猫狗等）一窝（仔畜）；4.[总称]乱丢的东西（尤指废纸等杂物）；vt.1.为（动物）铺草；2.（多产动物）产（仔）；3.乱丢refine [ri'fain]vt.1.提纯，精制；2.使精美，使改进；vt.1.精炼，提纯；2.变优雅regeneration[ri,dʒenə'reiʃən, ri:-] n.新生，再生，复兴paralyse['pærəlaiz] vt.1.使麻痹，使瘫痪；2.使无力，使气馁regrow[ri:'ɡrəu] vt.再生长，重新生长reproduce[,ri:prə'dju:s]vt.1.繁殖；2.再生产，再生长（器官）；2.复制；4.再现，重现sacrifice to 向……献祭；为……而牺牲；为……而失去do research into 进行……的研究be central to 对……极为重要的do experiment on 用……做实验be irrelevant to 与……不相干；不切题test on 对……进行试验aim for瞄准；以……为目标pet [pet] n.宠物，爱畜；a.宠爱的，表示亲昵的delightful[di'laitful] a.令人高兴的；讨人喜欢的humanity [hju:'mænəti] n.1.人性，博爱，仁慈；2.人类negative['neɡətiv] a.1.否定的，否认的；2.反面的，消极的；3.[数]负的，[电]阴性的；n.1.负片，底片；2.负数remark [ri'mɑ:k]vt.说，评论；vi.评论，议论（on）；n.评论，看法touching ['tʌtʃiŋ] a.动人的，使人感伤的going['ɡəuiŋ]n.进行状况；a.进行中的；现行的coming ['kʌmiŋ] a.正在到来的，即将来到的；n.来到，到达literal['litərəl] a.1.精确的，如实的；2.逐字的，字面的grant[ɡrɑ:nt, ɡrænt]vt.同意；准予；n.1.同意，授予；2.拨款contented [kən'tentid] a.满足的，满意的serene [si'ri:n] a.安详的；宁静的contemplate['kɔntəm,pleit] vt.1.注视，凝视；2.沉思plea[pli:] n.1.请求，恳求；2.托词devotion [di'vəuʃən] n.献身，忠诚ownership['əunəʃip] n.1.拥有；2.所有权，所有制imperative [im'perətiv] a.1.绝对必要的，迫切的；2.命令，强制的；3.[语]祈使的stricken ['strikən] I. strike的过去分词 II.a.1.被打中的，被击伤的；2（常用以构成复合词）受灾的，受侵袭的relief [ri'li:f]n.1.（痛苦，压迫等）减轻，宽慰；2.救济donation [dəu'neiʃən] n.捐献；赠送afflict [ə'flikt] vt.使苦恼，折磨deprive[di'praiv] vt.夺去，剥夺；使失去（of）individualistic['indi,vidjuə'listik, -dʒu-] a.个人主义（者）的prevail[pri'veil, pri:-]vi.1.胜过（over， against）；2.流行，盛行starvation [stɑ:'veiʃən] n.饥饿；饿死kwashiorkor [,kwɑ:ʃi'ɔ:kə] n.[医]恶性营养不良症deficiency[di'fiʃənsi] n.缺乏，不足starve [stɑ:v] vi.1.饿死；2.挨饿；3.极需，渴望（for）；vt.使饿死；使挨饿sustain [sə'stein] vt.1.支撑，承受住；2.供养，维持unreasonable[,ʌn'ri:zənəbl] a.1.不讲道理的，非理智的；2.不合情理的，过度的bring out 1.使显现，显示；2生产，使产生attach……to使……与……相关，把……附加到goings and comings 1.来往；2.活动，发生的事take……for granted 1.认为真实；2.视为当然at ease 自在的，舒适的plea for 恳求；请求not that……并不是说not （never） for a moment 决不；从不break in on（upon） 1.打扰；2.打断，闯进feel bitter at 对……怀恨seize hold of 1.抓住；2.占有daydream['deidri:m] vi./n.白日做梦symptom['simptəm] n.症状，征兆habitual[hə'bitjuəl] a.1.习惯性的，习以为常的2.惯常的，已成规则的maladjustment [,mælə'dʒʌstmənt] n.1.失调；2.不适应环境compensatory[kəm'pensətəri] a.赔偿，补偿的equilibrium [,i:kwi'libriəm]n.1.平衡，均衡，平均，相称；2.均势；3.（心情的）平静；4.（判断上的）不偏不倚intellectual[,intə'lektjuəl, -tʃuəl] n.知识分子；a.智力的，理智的detail ['di:teil, di'teil] n.细节，详情；vt.详述，详细说明enhance [in'hɑ:ns, -hæns] vt.提高；增强spur [spə:] vt.1.用催马刺催促（马）；2.激励，鞭策；n.1.踢马刺；2.刺激（物），激励，鼓舞initial [i'niʃəl] a.1.最初的，开始的；2.词首的；n.首字母inventor [in'ventə] n.发明者，创造者waylay[,wei'lei, 'weilei] vt.伏击；拦住……问讯muse [mju:z] v./n.沉思，冥想confront[kən'frʌnt] vt.1.面对，遭遇；2.正视，对抗painter ['peintə] n.漆工；画家sensitivity [,sensi'tiviti] n.敏感性；灵敏度inner ['inə] a.1.内部的，里面的；2.思想的，精神的；n.内部；里面reflection [re'flekʃən] n.1.反射，反映，映像；2.深思，考虑creativity[,kriei'tiviti] n.创造性effortless['efətlis] a.1.不作努力的；2.不费力的，容易的dreamlike ['dri:mlaik] a.梦一般的，梦幻的surrounding [sə'raundiŋ] n.[pl.]周围的事物；环境；a.周围的character['kærəktə]n.1.性格，品质；2.特性，特征；3.人物，角色；4.（书写或印刷）符号，（汉）字thinker['θiŋkə] n.思想家；思考者steadily ['stedili] ad.稳固地；稳定地vividly ['vividli] ad.鲜明地；生动地drift [drift] n.1.漂流；2.趋势，倾向；vi.漂流；漂泊；vt.使漂流trace [treis] n.1.痕迹，踪迹；2.微量，少许；vt.跟踪，查找undisturbed [,ʌndi'stə:bd] a.不受干扰的；宁静的tune[tju:n, tu:n] n.1.曲调，曲子；2.和谐，协调；vt.1.为（乐器）调音；2.和谐，调节midst[midst] n.中间，当中；prep.（=amidst）在……当中impoverished[im'pɔvəriʃt] a.贫困的，赤贫的well-being ['wel'bi:ŋ] n.1.健康；2.福利，幸福modest ['mɔdist] a.1.谦虚的，谦恭的；2.适中的，不过分的investment [in'vestmənt] n.投资；（时间，精力的）投入excitement[ik'saitmənt] n.刺激；兴奋to excess过分，过度，过量substitute……for用……代替……be contrary to 与……相反in reality 实际上，事实上put off 1.延期；2.消除；3.阻碍let go of 放手；放开be confronted with 面临，面对draw on 1.用做来源，依靠；2.临近gaze at凝视，注视be unaware of 不知道……，没觉察到……dream of 梦见；梦想in one's mind's eye 在脑海里at sea 1.在海上，在航海中；2.迷惑，茫然go over 1.越过，渡过；2.仔细检查impress……on使……铭记，牢记be free from 没有……的；不受……的put aside 1.放在一边，撇开；2.储存be beneficial to对……有益add up to 1.总和是；2.[口]总起来意味着perchance [pə'tʃɑ:ns] ad.[古]1.偶然，意外地；2.可能，或许miserable['mizərəbl] a.悲惨的；可怜的far-fetched ['fɑ:'fetʃt] a.1.牵强的；2.未必会的，靠不住的veteran['vetərən] n.1.老兵，老手；2.[美]退伍军人；a.老练的；经验丰富的administration [əd,mini'streiʃən] n.1.管理，经营；2.行政，行政机关sleepy['sli:pi] a.困倦的，嗜睡的link[liŋk] n.环节，联系；vt.用环连接；联系elude [i'lju:d] vt.（巧妙地）逃避，躲避respectively[ri'spektivli]ad.各自地，分别地definitive[di'finitiv] a.1.决定的，确定的；2.限定的，明确的evolve[i'vɔlv]vt.1.使发展，使形成，制定；2.引申出，推论；vi.1.进展；2.进化differ ['difə] vi.1.不同，相异（from）；2.与……意见不同（from， with）surprisingly [sə'praiziŋli]ad.惊人地；出乎意料地namely['neimli] ad.即，也就是plus[plʌs]prep.加，加上；a.1.正的；2.附加的acronym ['ækrəunim] n.首字母缩略词eyeball['aibɔ:l] n.眼球correlation [,kɔ:ri'leiʃən] n.相互关系，关联physiology[,fizi'ɔlədʒi] n.生理学unhappy [,ʌn'hæpi]n.1.不快乐的，愁苦的；2.不幸的dreamer ['dri:mə] n.1.做梦的；2.空想家volunteer[,vɔlən'tiə] n.志愿者；志愿兵；a.志愿的；vi.志愿identity [ai'dentəti] n.1.同一，一致；2.身份，本体primarily ['praimərəli, prai'me-] ad.1.首先，起初；2.首要地，主要地merry['meri] a.欢乐的，愉快的psychology [psai'kɔlədʒi] n.1.心理学；2.心理location [ləu'keiʃən] n.1.定位，测位；2.位置，场所reinforce[,ri:in'fɔ:s] vt.1.增援，支援；2加强，增加；3.进一步证实influence on 对……的影响break into 分成（部分）check into 调查compel[kəm'pel] vt.强迫（to）rightly ['raitli] ad.1公正地，正当地；2.合适地，恰当地laborer ['leibərə] n.劳动者；工人antithesis [æn'tiθisis] n.1.对偶（修辞学）对句；2.对立，对立面。