The main result of the present paper is that the variable-free fragment of logic K*, the logic with a single K-style modality and its “reflexive and transitive closure,” is EXPTIMEcomplete. It is then shown that this immediately gives EXPTIME-completeness of variable-free fragments of a number of known EXPTIME-complete logics. Our proof contains a general idea of how to construct a polynomial-time reduction of a propositional logic to its n-variable—and even, in the cases of K*, PDL, CTL, ATL, and some others, (...) variable-free—fragments. Complexity of countermodels for such fragments is considered. (shrink)

In the paper we consider complexity of intuitionistic propositional logic and its natural fragments such as implicative fragment, finite-variable fragments, and some others. Most facts we mention here are known and obtained by logicians from different countries and in different time since 1920s; we present these results together to see the whole picture.

This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions in (...) terms of their intrinsic, and not just their model-dependent, difficulty, and it shows how the approach allows us to model the idea that intrinsic difficulty is a fuzzy concept. (shrink)

In his bookMinimal Rationality (1986), Christopher Cherniak draws deep and widespread conclusions from our finitude, and not only for philosophy but also for a wide range of science as well. Cherniak's basic idea is that traditional philosophical theories of rationality represent idealisations that are inaccessible to finite rational agents. It is the purpose of this paper to apply a theory of idealisation in science to Cherniak's arguments. The heart of the theory is a distinction between idealisations that represent reversible, solely (...) quantitative simplifications and those that represent irreversible, degenerate idealisations which collapse out essential theoretical structure. I argue that Cherniak's position is best understood as assigning the latter status to traditional rationality theories and that, so understood, his arguments may be illuminated, expanded, and certain common criticisms of them rebutted. The result, however, is a departure from traditional, formalist theories of rationality of a more radical kind than Cherniak contemplates, with widespread ramifications for philosophical theory, especially philosophy of science itself. (shrink)

In the study of cognitive processes, limitations on computational resources (computing time and memory space) are usually considered to be beyond the scope of a theory of competence, and to be exclusively relevant to the study of performance. Starting from considerations derived from the theory of computational complexity, in this paper I argue that there are good reasons for claiming that some aspects of resource limitations pertain to the domain of a theory of competence.