Cook and Reckhow [5] pointed out that $\mathcal {N}\mathcal {P} \neq co\mathcal {N}\mathcal {P}$ iff there is no propositional proof system that admits polynomial size proofs of all tautologies. The theory of proof complexity generators aims at constructing sets of tautologies hard for strong and possibly for all proof systems. We focus on a conjecture from [16] in foundations of the theory that there is a proof complexity generator hard for all proof systems. This can be equivalently formulated (...) (for p-time generators) without a reference to proof complexity notions as follows:•There exists a p-time function g stretching each input by one bit such that its range $rng(g)$ intersects all infinite $\mathcal {N}\mathcal {P}$ sets.We consider several facets of this conjecture, including its links to bounded arithmetic (witnessing and independence results), to time-bounded Kolmogorov complexity, to feasible disjunction property of propositional proof systems and to complexity of proof search. We argue that a specific gadget generator from [18] is a good candidate for g. We define a new hardness property of generators, the $\bigvee $ -hardness, and show that one specific gadget generator is the $\bigvee $ -hardest (w.r.t. any sufficiently strong proof system). We define the class of feasibly infinite $\mathcal {N}\mathcal {P}$ sets and show, assuming a hypothesis from circuit complexity, that the conjecture holds for all feasibly infinite $\mathcal {N}\mathcal {P}$ sets. (shrink)

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, (...) which assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some (...) of our main results.• Although Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time.• Although for every universal machine U, there are very complex sets that are -reducible to , it is nonetheless true that . • Any decidable set that is polynomial-time monotone-truth-table reducible to is in .• Any decidable set that is polynomial-time truth-table reducible to via a reduction that asks at most f queries on inputs of size n lies in. (shrink)

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov (...) class='Hi'>complexity for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations. (shrink)

Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the asymptotic behaviour of the sequence of the Kolmogorov complexities of the finitely-representable objects—such as rational numbers—used to approximate them.This idea will be taken further here by extending the definition to continuous functions over real numbers, based on the fact that every continuous real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials (...) with rational coefficients.Based on this definition, we will prove that for any growth rate imaginable, there are real functions whose Kolmogorov complexities have higher growth rates. In fact, using the concept of prevalence, we will prove that ‘almost every’ continuous real function has such a high-growth Kolmogorov complexity. An asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions will be presented as well. (shrink)

Classical fractal dimensions have recently been effectivized by characterizing them in terms of real-valued functions called gales, and imposing computability and complexity constraints on these gales. This paper surveys these developments and their applications in algorithmic information theory and computational complexity theory.

The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta (...) }}_2^0$orders, and call the new notions${\rm{\Delta }}_2^0$-bounded K-trivialand${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties ofK-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the${\rm{\Delta }}_2^0$-boundedK-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namelyinfinitely-often K-trivialityandweak lowness for K. We show that${\rm{\Delta }}_2^0$-boundedK-trivial implies infinitely-oftenK-trivial, but no implication holds between${\rm{\Delta }}_2^0$-bounded low forKand weakly low forK. (shrink)

Sequential decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known. Solomonoff's theory of universal induction formally solves the problem of sequence prediction for unknown prior distribution. We combine both ideas and get a parameter-free theory of universal Artificial Intelligence. We give strong arguments that the resulting AIXI model is the most intelligent unbiased agent possible. We outline how the AIXI model can formally solve a number of problem classes, (...) including sequence prediction, strategic games, function minimization, reinforcement and supervised learning. The major drawback of the AIXI model is that it is uncomputable. To overcome this problem, we construct a modified algorithm AIXItl that is still effectively more intelligent than any other time t and length l bounded agent. The computation time of AIXItl is of the order t x 2^l. The discussion includes formal definitions of intelligence order relations, the horizon problem and relations of the AIXI theory to other AI approaches. (shrink)

It is shown that time may be appreciated in at least two senses: chronological and dynamical. Chronological time is the time of our naïve acquaintance as transient beings. At its most extensive scale, it corresponds to history encompassing both the abiotic and the biotic universe. Dynamical time, deriving from classical mechanics, is the time embraced by most of the laws of physics. It concerns itself only with present conditions since it is held that that the (...) past may be reconstructed from the present and the future predicted from the present, a position known as Laplacian determinism.Nonlinear dynamics has shown the fallacy of this supposition: The concrete values that may be assumed in the variables of the equations of motion constituting the laws of physics as a result of the spontaneous or intentional interaction of subject or measuring systems and of object or measured systems cannot be of infinite precision. Indeed, even if they could be, it is not at all clear that they would permit Laplacian determinism because of what is thought to be the ubiquity of K-flow dynamics in nature in which even infinite past information leading to the present cannot yield prediction of the future. In consequence, nonlinear dynamics, in rebellion against dynamical time, generates a primitive form of history distinguishing past, present, and future that may be termed nonlinear dynamical hysteresis.When nonlinear dynamics came to be complemented with semiotic modulation through the implement of symbol-mediated language as first instantiated through the communicating as opposed to the merely dynamically interacting molecular complexes of the cell, what can be termed semiotic hysteresis was born. The paper attempts to show that indefinitely evolving complexity, sustainability, justice, and meaning are indissolubly bound with chronological time in the sense of semiotic hysteresis : This semiotic hysteresis yields the indefinite evolutionary time of the living condition—including culture. (shrink)

In 1984, Danecki proved that satisfiability in IPDL, i.e., Propositional Dynamic Logic (PDL) extended with an intersection operator on programs, is decidable in deterministic double exponential time. Since then, the exact complexity of IPDL has remained an open problem: the best known lower bound was the ExpTime one stemming from plain PDL until, in 2004, the first author established ExpSpace-hardness. In this paper, we finally close the gap and prove that IPDL is hard for 2-ExpTime, thus 2-ExpTime-complete. We (...) then sharpen our lower bound, showing that it even applies to IPDL without the test operator interpreted on tree structures. (shrink)

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some (...) sense. We give an example of how this result can be used in the study of scattered linear orders. (shrink)

If we express our knowledge in sentences, we will find that these sentences are linked in complex patterns governed by our observations and our inferences from these observations. These inferences are to a large extent driven by logical rules. We ask whether the structure logic imposes on our knowledge restricts what we forget and what we remember. The model is a two period S5 logic. In this logic, we propose a memory loss operator: the agent forgets a sentence pif and (...) only if he knows pat time 1 and he does not know pat time 2. Equipped with the operator, we prove theorems on the relation between knowledge and memory loss. The main results point to classes of formulas that an agent cannot forget, and classes of formulas he must forget. A desirable feature is that most results hold in the S4 logic. The results illustrate bounds to memory loss, and thus to bounded rationality. We apply the model to single-agent conventions: conventions made between an agent and himself. (shrink)

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access (...) machine in polylogarithmic parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

There have been two major lines of research aimed at capturing resource-bounded players in game theory. The first, initiated by Rubinstein (), charges an agent for doing costly computation; the second, initiated by Neyman (), does not charge for computation, but limits the computation that agents can do, typically by modeling agents as finite automata. We review recent work on applying both approaches in the context of decision theory. For the first approach, we take the objects of choice in (...) a decision problem to be Turing machines, and charge players for the “complexity” of the Turing machine chosen (e.g., its running time). This approach can be used to explain well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on) and belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions) as the outcomes of quite rational decisions. For the second approach, we model people as finite automata, and provide a simple algorithm that, on a problem that captures a number of settings of interest, provably performs optimally as the number of states in the automaton increases. (shrink)

It is well known that for a given continuous function f : [0, 1] → ℝ and a number n there exists a unique polynomial pn ∈ Pn which best L1-approximates f. We establish the first upper bound on the complexity of the sequence n∈ ℕ, assuming f is polynomial-time computable. Our complexity analysis makes essential use of the modulus of uniqueness for L1-approximation presented in [13].

While classical temporal logics lose track of a state as soon as a temporal operator is applied, several branching-time logics able to repeatedly refer to a state have been introduced in the literature. We study such logics by introducing a new formalism, hybrid branching-time logics, subsuming the other approaches and making the ability to refer to a state more explicit by assigning a name to it. We analyze the expressive power of hybrid branching-time logics and the (...) class='Hi'>complexity of their satisfiability problem. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME -complete. To prove the upper bound, the automata-theoretic approach to branching-time logics is extended to hybrid logics. As a result of independent interest, the nonemptiness problem for alternating one-pebble Büchi tree automata is shown to be 2EXPTIME -complete. A common property of the logics studied is that they refer to only one state. This restriction is crucial: The ability to refer to more than one state causes a nonelementary blow-up in complexity. In particular, we prove that satisfiability for NCTL * has nonelementary complexity. (shrink)

The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: domains with polynomialtime computable boundaries, and polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type and type ; and (...) it has a polynomial-space lower bound for the domains of type , and has a #P lower bound for the domains of type. (shrink)

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper (...) to prove that, nevertheless, the definition has a large number of important applications. Using the framework of TTE [40], we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a c-proper c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have concise c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar one by Labhalla et al. [22]. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation. (shrink)

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic (...) exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster. (shrink)

We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There (...) are interesting choices of between these two extremes, for example the class of all singly exponential functions. In this article, we study the general theory of -fixed-parameter tractability. We introduce a generic notion of reduction and two classes -W[P] and -XP, which may be viewed as analogues of NP and EXPTIME, respectively, in the world of -fixed-parameter tractability. (shrink)

We derive the exact inefficiency upper bounds of the multiclass C-Logit stochastic user equilibrium in a transportation network. All travelers are classified on the basis of different values of time into M classes. The multiclass CL-SUE model gives a more realistic path choice probability in comparison with the logit-based stochastic user equilibrium model by considering the overlapping effects between paths. To find efficiency loss upper bounds of the multiclass CL-SUE, two equivalent variational inequalities for the multiclass CL-SUE model, i.e., (...) time-based variational inequality and monetary-based VI, are formulated. We give four different methods to define the inefficiency of the multiclass CL-SUE, i.e., to compare multiclass CL-SUE with multiclass system optimum, or to compare multiclass CL-SUE with multiclass C-Logit stochastic system optimum, under the time-based criterion and the monetary-based criterion, respectively. We further investigate the effects of various parameters which include the degree of path overlapping, the network complexity, degree of traffic congestion, the VOT of user classes, the network familiarity, and the total demand on the inefficiency bounds. (shrink)

If S ⊆{0,1}; * and S ′ = {0,1} * \sb S are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A n → A′ n with unique interpolants I n that define S ∩{0,1} n ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T p for some fixed p \s>0. In general, complexity measures for (...) the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories. (shrink)

The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, (...) the [Formula: see text]-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new [Formula: see text]-principle that is conjectured to separate [Formula: see text] and [Formula: see text]. (shrink)

In this article, I will discuss possible differences between ecosystems and organisms on the basis of their intrinsic complexity. As the concept of complexity still remains highly debated, I propose here a practical and original way to measure the complexity of an ecosystem or an organism. For this purpose, I suggest using the concept of logical depth (LD) in a specific manner, in order to take into account the difficulty as well as the time needed to (...) generate the studied object. I illustrate this method with fully controlled Daisyworld simulations (i.e., simulations based on the Gaia hypothesis) that have often been proposed to mimic living systems. The method consists of the following sequential stages: (1) identification of the shortest program able to numerically model the studied system (also called the Kolmogorov–Solomonoff complexity); (2) running the program, once if there are no stochastic components in the system, several times if stochastic components are there; and (3) computing the time needed to generate the system with LD complexity. This measure is supposed to estimate the system complexity. It appears in this study that LD estimations fit well with the intuition we have of complex systems, with higher complexities being found for more realistic Daisyworlds. With such a method of capturing the time needed to build a system, we expect to detect in future studies any quantified differences between complex ecosystems and organisms. (shrink)

A crucial socio-political challenge for our age is how to rede!ne or extend group membership in such a way that it adequately responds to phenomena related to globalization like the prevalence of migration, the transformation of family and social networks, and changes in the position of the nation state. Two centuries ago Immanuel Kant assumed that international connectedness between humans would inevitably lead to the realization of world citizen rights. Nonetheless, globalization does not just foster cosmopolitanism but simultaneously yields the (...) development of new group boundaries. Group membership is indeed a fundamental issue in political processes, for: “the primary good that we distribute to one another is membership in some human community” – it is within the political community that power is being shared and, if possible, held back from non-members. In sum, it is appropriate to consider group membership a fundamental ingredient of politics and political theory. How group boundaries are drawn is then of only secondary importance. Indeed, Schmitt famously declared that “[e]very religious, moral, economic, ethical, or other antithesis transforms into a political one if it is suffciently strong to group human beings e#ectively according to friend and enemy”. Even though Schmitt’s idea of politics as being constituted by such antithetical groupings is debatable, it is plausible to consider politics among other things as a way of handling intergroup di#erences. Obviously, some of the group-constituting factors are more easily discernable from one’s appearance than others, like race, ethnicity, or gender. As a result, factors like skin color or sexual orientation sometimes carry much political weight even though individuals would rather con!ne these to their private lives and individual identity. Given the potential tension between the political reality of particular groupmembership defnitions and the – individual and political – struggles against those definitions and corresponding attitudes, citizenship and civic behavior becomes a complex issue. As Kymlicka points out, it implies for citizens an additional obligation to non-discrimination regarding those groups: “[t]his extension of non-discrimination from government to civil society is not just a shift in the scale of liberal norms, it also involves a radical extension in the obligations of liberal citizenship”. Unfortunately, empirical research suggests that political intolerance towards other groups “may be the more natural and ‘easy’ position to hold”. Indeed, since development of a virtue of civility or decency regarding other groups is not easy, as it often runs against deeply engrained stereotypes and prejudices, political care for matters like education is justified. Separate schools, for example, may erode children’s motivation to act as citizens, erode their capacity for it and!nally diminish their opportunities to experience transcending their particular group membership and behave as decent citizens. This chapter outlines a possible explanation for such consequences. That explanation will be found to be interdisciplinary in nature, combining insights from political theory and cognitive neuroscience. In doing so, it does not focus on collective action, even though that is a usual focus for political studies. For example, results pertaining to collective political action have demonstrated that the relation between attitudes and overt voting behavior or political participation is not as direct and strong as was hoped for. Several conditions, including the individual’s experiences, self-interest, and relevant social norms, turned out to interfere in the link between his or her attitude and behavior. Important as collective action is, this chapter is concerned with direct interaction between agents and the in$uence of group membership on such interaction – in particular joint action. Although politics does include many forms of action that require no such physical interaction, such physical interaction between individuals remains fundamental to politics – this is the reason why separate schooling may eventually undermine the citizenship of its isolated pupils. This chapter will focus on joint action, de!ned as: “any form of social interaction whereby two or more individuals coordinate their actions in space and time to bring about a change in the environment”. Cognitive neuroscienti!c evidence demonstrates that for such joint action to succeed, the agents have to integrate the actions and expected actions of the other person in their own action plans at several levels of speci!city. Although neuroscienti!c research is necessarily limited to simple forms of action, this concurs with a philosophical analysis of joint action, which I will discuss below. (shrink)

This article examines mixed ℋ -infinity and passivity synchronization of Markovian jumping neutral-type complex dynamical network models with randomly occurring coupling delays and actuator faults. The randomly occurring coupling delays are considered to design the complex dynamical networks in practice. These delays complied with certain Bernoulli distributed white noise sequences. The relevant data including limits of actuator faults, bounds of the nonlinear terms, and external disturbances are available for designing the controller structure. Novel Lyapunov–Krasovskii functional is constructed to verify the (...) stability of the error model and performance level. Jensen’s inequality and a new integral inequality are applied to derive the outcomes. Sufficient conditions for the synchronization error system are given in terms of linear matrix inequalities, which can be analyzed easily by utilizing general numerical programming. Numerical illustrations are given to exhibit the usefulness of the obtained results. (shrink)

In [U. Kohlenbach, Some logical metatheorems with applications in functional analysis, Trans. Amer. Math. Soc. 357 89–128], the second author obtained metatheorems for the extraction of effective bounds from classical, prima facie non-constructive proofs in functional analysis. These metatheorems for the first time cover general classes of structures like arbitrary metric, hyperbolic, CAT and normed linear spaces and guarantee the independence of the bounds from parameters ranging over metrically bounded spaces. Recently ]), the authors obtained generalizations of these (...) metatheorems which allow one to prove similar uniformities even for unbounded spaces as long as certain local boundedness conditions are satisfied. The use of classical logic imposes some severe restrictions on the formulas and proofs for which the extraction can be carried out. In this paper we consider similar metatheorems for semi-intuitionistic proofs, i.e. proofs in an intuitionistic setting enriched with certain non-constructive principles. Contrary to the classical case, there are practically no restrictions on the logical complexity of theorems for which bounds can be extracted. Again, our metatheorems guarantee very general uniformities, even in cases where the existence of uniform bounds is not obtainable by straightforward functional analytic means. Already in the purely intuitionistic case, where the existence of effective bounds is implicit, the metatheorems allow one to derive uniformities that may not be obvious at all from a given constructive proof. Finally, we illustrate our main metatheorem by an example from metric fixed point theory. (shrink)

Infinite machines (IMs) can do supertasks. A supertask is an infinite series of operations done in some finite time. Whether or not our universe contains any IMs, they are worthy of study as upper bounds on finite machines. We introduce IMs and describe some of their physical and psychological aspects. An accelerating Turing machine (an ATM) is a Turing machine that performs every next operation twice as fast. It can carry out infinitely many operations in finite time. Many (...) ATMs can be connected together to form networks of infinitely powerful agents. A network of ATMs can also be thought of as the control system for an infinitely complex robot. We describe a robot with a dense network of ATMs for its retinas, its brain, and its motor controllers. Such a robot can perform psychological supertasks - it can perceive infinitely detailed objects in all their detail; it can formulate infinite plans; it can make infinitely precise movements. An endless hierarchy of IMs might realize a deep notion of intelligent computing everywhere. (shrink)

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial (...) time complete consistent extension when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

This paper considers the computational complexity of the disjunction and existential properties of intuitionistic logic. We prove that the disjunction property holds feasibly for intuitionistic propositional logic; i.e., from a proof of A v B, a proof either of A or of B can be found in polynomial time. For intuitionistic predicate logic, we prove superexponential lower bounds for the disjunction property, namely, there is a superexponential lower bound on the time required, given a proof of A (...) v B, to produce one of A and B which is true. In addition, there is superexponential lower bound on the size of terms which fulfill the existential property of intuitionistic predicate logic. There are superexponential upper bounds for these problems, so the lower bounds are essentially optimal. (shrink)

In their simplest form, hybrid languages are propositional modal languages which can refer to states. They were introduced by Arthur Prior, the inventor of tense logic, and played an important role in his work: because they make reference to specific times possible, they remove the most serious obstacle to developing modal approaches to temporal representation and reasoning. However very little is known about the computational complexity of hybrid temporal logics.In this paper we analyze the complexity of the satisfiability (...) problem of a number of hybrid temporal logics: the basic hybrid language over transitive trees; nominal Until logic; and referential interval logic. We discuss the effects of including nominals, the @ operator, the somewhere modality E, and the difference operator D. Adding nominals to tense logic leads for several frame-classes to an increase in complexity of the satisfiability problem from PSPACE to EXPTIME. On transitive trees, however, the satisfiability problem for this language can be decided in PSPACE. Along the way we make a detour through hybrid propositional dynamic logic: we establish upper bounds for a number of temporal logics by generalizing results due to Passy and Tinchev [29] and De Giacomo [16]. We conclude with some remarks on the relevance of our results to description logic, and draw attention to the utility of the spypoint technique for proving upper and lower bounds. (shrink)

The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the size of (...) the input sentence and n the size of the input word. We establish a number of similar lower bounds for the model-checking problem for first-order logic, for example, on the class of all trees. (shrink)

The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: domains with polynomialtime computable boundaries, and polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type and type ; and (...) it has a polynomial-space lower bound for the domains of type, and has a #P lower bound for the domains of type. (shrink)

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? We (...) provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n. (shrink)

This paper proposes a Cournot game organized by three competing firms adopting bounded rationality. According to the marginal profit in the past time step, each firm tries to update its production using local knowledge. In this game, a firm’s preference is represented by a utility function that is derived from a constant elasticity of substitution production function. The game is modeled by a 3-dimensional discrete dynamical system. The equilibria of the system are numerically studied to detect their complex (...) characteristics due to difficulty to get an explicit form for those equilibria. For the proposed utility function, some cases with different value parameters are considered. Numerical simulations are used to provide an experimental evidence for the complex behavior of the evolution of the system. The obtained results show that the system loses its stability due to different types of bifurcations. (shrink)

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we (...) prove some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. (shrink)

The undecidability of first-order logic implies that there is no computable bound on the length of shortest proofs of valid sentences of first-order logic. Some valid sentences can only have quite long proofs. How hard is it to prove such "hard" valid sentences? The polynomial time tractability of this problem would imply the fixed-parameter tractability of the parameterized problem that, given a natural number n in unary as input and a first-order sentence φ as parameter, asks whether φ has (...) a proof of length ≤ n. As the underlying classical problem has been considered by Gödel we denote this problem by p-Gödel. We show that p-Gödel is not fixed-parameter tractable if DTIME(h O(1) ) ≠ NTIME(h O(1) ) for all time constructible and increasing functions h. Moreover we analyze the complexity of the construction problem associated with p-Gödel. (shrink)

The ability of ordinary differential equations (ODEs) to simulate discrete machines with a universal computing power indicates a new source of difficulties for event detection problems. Indeed, nearly any kind of event detection is algorithmi- cally undecidable for infinite or finite half-open time intervals, and explicitly given “well-behaved” ODEs (see [18]). Practical event detection, however, usually takes place on finite closed time intervals. In this paper the undecidability of general event detection is extended to such intervals. On the (...) other hand, on finite closed time in- tervals event detection in a certain approximate sense is quite generally decidable, which partly saves the case for practicable event detection. The capability of simulat- ing universal Turing machines is still there, and is used to give complexity lower bounds in terms of accuracy of event detection. The ODEs used here are of course quite complicated, but not artificial, in that even from the point of view of practical event detection it would appear difficult to find criteria to exclude them. (shrink)

Tissue P systems with evolutional communication rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class (...) P can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most, for each natural number n≥1. In the case where that length is upper bounded by, a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem. (shrink)

Many problems in Multi-Agent Systems (MASs) research are formulated in terms of the abilities of a coalition of agents. Existing approaches to reasoning about coalitional ability are usually focused on games or transition systems, which are described in terms of states and actions. Such approaches however often neglect a key feature of multi-agent systems, namely that the actions of the agents require resources. In this paper, we describe a logic for reasoning about coalitional ability under resource constraints in the probabilistic (...) setting. We extend Resource-bounded Alternating-time Temporal Logic (RB-ATL) with probabilistic reasoning and provide a standard algorithm for the model-checking problem of the resulting logic Probabilistic resource-bounded ATL (pRB-ATL). We implement model-checking algorithms and present experimental results using simple multi-agent model-checking problems of increasing complexity. (shrink)

We study the class that consists of distributional problems which can be solved in average polynomial time by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for under polynomial time samplable distributions. Since we use deterministic reductions, the existence of a deterministic algorithm with average polynomial running time for our problem would imply. Note that, while it is easy to construct a promise problem that is complete for, it (...) is unknown whether contains complete languages. We also prove a time hierarchy theorem for. We compare average-case classes with their classical counterparts and show that the inclusions are proper. (shrink)

This research evaluates the production of three dimensional (3D) clouds for geospatial viewing programs such as Google Earth, NASA World Wind, and X3D Earth. This thesis took advantage of iso-standard X3D graphics and X3D Edit in conjunction with manually produced image textures to represent 3D clouds. While a 3D geospatial viewing might never completely characterize the current state of the atmosphere, a sufficiently realistic virtual 3D rendering can be created to present current sky coverage given adequate satellite and model data. (...) Various visualization demonstration results are presented that can be rendered and navigated in real time. Further research and development is needed to match a cloud typing model output with a particular method of 3D cloud production. Data-driven adaptation and production of cloud models for web-based delivery is an achievable capability given continued research and development. (shrink)

Demuth tests generalize Martin-Löf tests in that one can exchange the m-th component a computably bounded number of times. A set fails a Demuth test if Z is in infinitely many final versions of the Gm. If we only allow Demuth tests such that GmGm+1 for each m, we have weak Demuth randomness.We show that a weakly Demuth random set can be high and , yet not superhigh. Next, any c.e. set Turing below a Demuth random set is strongly (...) jump-traceable.We also prove a basis theorem for non-empty classes P. It extends the Jockusch–Soare basis theorem that some member of P is computably dominated. We use the result to show that some weakly 2-random set does not compute a 2-fixed point free function. (shrink)