Search Results

This chapter shows the equivalence of K-triviality and lowness for Martin–Löf randomness. This coincidence extends to other lowness properties, such as being a base for Martin–Löf randomness, and lowness for weak 2-randomness. To prove the results, the chapter develops the accounting, cost function and decanter methods, and the golden run construction. The Main Lemma, derived from the golden run construction, yields a general way to restrict K-trivial sets.

This chapter studies lowness properties of sets not necessarily below the halting problem. The main new notions are all related to traceability. It characterizes lowness for Schnorr, and computable randomness. It also studies strong jump traceability and its relationship to the cost function method of Chapter 5. Many research problems are posed.

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.

This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and describes existing approaches to the optimization-driven evolution of complex networks. In particular, the optimized trade-off model of a growing network is described, as well as models showing the explosive percolation phenomenon.

The objective of ETRs is to improve the environment (for example, by reducing carbon emissions) while reducing other taxes which may have a negative economic effect. Often ETRs also have the objective of increasing employment. The aim of this chapter is to estimate the effect on the demand for energy and the level of unemployment of the UK and German ETRs that have been implemented. In order to do this, we estimate a specification based on a translog cost function which allows us to model the cross-price elasticities among capital, labour, energy, material, and services.

Phase transitions have long been studied empirically in various combinatorial searches and theoretically in simplified models [91, 264, 301, 490]. The analogy with statistical physics [397], explored throughout this volume, shows how the many local choices made during search relate to global properties such as the resulting search cost. These studies have led to a better understanding of typical search behaviors [514] and improved search methods [195, 247, 261, 432, 433]. Among the current research questions in this field are the range of algorithms exhibiting the transition behavior and the algorithm-independent problem properties associated with the difficult instances concentrated near the transition. Towards this end, the present chapter examines quantum computer [123, 126, 158, 486] algorithms for nondeterministic polynomial (NP) combinatorial search problems [191]. As with many conventional methods, they exhibit the easy-hard-easy pattern of computational cost as the degree of constraint in the problems varies. We describe how properties of the search space affect the algorithms and identify an additional structural property, the energy gap, motivated by one quantum algorithm but applicable to a variety of techniques, both quantum and classical. Thus, the study of quantum search algorithms not only extends the range of algorithms exhibiting phase transitions, but also helps identify underlying structural properties. Specifically, the next two sections describe a class of hard search problems and the form of quantum search algorithms proposed to date. The remainder of the chapter presents algorithm behaviors, relevant problem structure, arid an approximate asymptotic analysis of their cost scaling. The final section discusses various open issues in designing and evaluating quantum algorithms, and relating their behavior to problem structure. The k-satisfiability (k -SAT) problem, as discussed earlier in this volume, consists of n Boolean variables and m clauses. A clause is a logical OR of k variables, each of which may be negated. A solution is an assignment, that is, a value for each variable, TRUE or FALSE, satisfying all the clauses. An assignment is said to conflict with any clause it does not satisfy.

Three generic economic optimization problems (expenditure (cost) minimization, revenue maximization, and profit maximization) are studied using the mathematical tools developed in Chapters 2 and 3. Conjugate duality results are developed for each. The resulting dual representations (E(q;y), R(p,x), and π‎(p,q)) are shown to characterize all of the economically relevant information in, respectively, V(y), Y(x), and Gr(≽(y)). The implications of different restrictions on ≽(y) for the dual representations are examined.

This chapter explores several of the most common and useful approaches to atmospheric data fitting as well as the process of using air mass factors to produce vertical atmospheric column abundances from line-of-sight slant columns determined by data fitting. An atmospheric spectrum or other type of atmospheric sounding is usually fitted to a parameterized physical model by minimizing a cost function, usually chi-squared. Linear fitting, when the model of the measurements is linear in the model parameters is described, followed by the more common nonlinear fitting case. For nonlinear fitting, the standard Levenberg-Marquardt method is described, followed by the use of optimal estimation, one of several retrieval methods that make use of a priori information to providing regularization for the solution. In the context of optimal estimation, weighting functions, contribution functions, and averaging kernels are described. The Twomey-Tikhonov regularization procedure is presented. Correlated parameters, with the important example of Earth’s atmospheric ozone, are discussed.