This article discusses five propositions about managerial moral tractability -- that is, a morality that is amenable to the complexity of managers’ continual pressure to decide and act -- in their customer relations. The propositions come from the comparison of three case studies of different types of managers. To analyze the morality of managers, discursive practices of managers are studied. At the end of the article also some consideration is given to “information strategies” of managers, in relation to their (...) tractable morality. (shrink)

This book aims to lay bare the logical foundations of tractable reasoning. It draws on Marvin Minsky's seminal work on frames, which has been highly influential in computer science and, to a lesser extent, in cognitive science. Only very few people have explored ideas about frames in logic, which is why the investigation in this book breaks new ground. The apparent intractability of dynamic, inferential reasoning is an unsolved problem in both cognitive science and logic-oriented artificial intelligence. By means of (...) a logical investigation of frames and frame concepts, Andreas devises a novel logic of tractable reasoning, called frame logic. Moreover, he devises a novel belief revision scheme, which is tractable for frame logic. These tractability results shed new light on our logical and cognitive means to carry out dynamic, inferential reasoning. Modularity remains central for tractability, and so the author sets forth a logical variant of the massive modularity hypothesis in cognitive science. (shrink)

According to Church’s thesis, we can identify the intuitive concept of effective computability with such well-defined mathematical concepts as Turing computability and partial recursiveness. The almost universal acceptance of Church’s thesis among logicians and computer scientists is puzzling from some epistemological perspectives, since no formal proof is possible of a thesis that involves an informal concept such as effectiveness. Elliott Mendelson has recently argued, however, that equivalencies between intuitive notions and precise notions need not always be considered unprovable theses, and (...) that Church’s thesis should be accepted as true.I want to discuss a thesis that is nearly as important in current research in computer science as Church’s thesis. I call the newer thesis the tractability thesis, since it identifies the intuitive class of computationally tractable problems with a precise class of problems whose solutions can be computed in polynomial time. After briefly reviewing the theory of intractability, I compare the grounds for accepting the tractability thesis with the grounds for accepting Church's thesis. Intimately connected with the tractability thesis is the mathematical conjecture, whose meaning I shall shortly explain, that P≠NP. Unlike Church's thesis, this conjecture is precise enough to be capable of mathematical proof, but most computer scientists believe it even though no proof has been found. As we shall see below, understanding the grounds for acceptance of the conjecture that P≠NP has implications for general questions in the philosophy of mathematics and science, especially concerning the epistemological importance of explanatory and conceptual coherence. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...) evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

According to the Best System Account of lawhood, laws of nature are theorems of the deductive systems that best balance simplicity and strength. In this paper, I advocate a different account of lawhood which is related, in spirit, to the BSA: according to my account, laws are theorems of deductive systems that best balance simplicity, strength, and also calculational tractability. I discuss two problems that the BSA faces, and I show that my account solves them. I also use my (...) account to illuminate the nomological character of special science laws. (shrink)

FDE is a logic that captures relevant entailment between implication-free formulae and admits of an intuitive informational interpretation as a 4-valued logic in which “a computer should think”. However, the logic is co-NP complete, and so an idealized model of how an agent can think. We address this issue by shifting to signed formulae where the signs express imprecise values associated with two distinct bipartitions of the set of standard 4 values. Thus, we present a proof system which consists of (...) linear operational rules and only two branching structural rules, the latter expressing a generalized rule of bivalence. This system naturally leads to defining an infinite hierarchy of tractable depth-bounded approximations to FDE. Namely, approximations in which the number of nested applications of the two branching rules is bounded. (shrink)

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance the Tractable Cognition thesis: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational‐level theories of cognition. To utilize this constraint, a precise and workable definition of “computational tractability” is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial‐time computability, leading to (...) the P‐Cognition thesis. This article explains how and why the P‐Cognition thesis may be overly restrictive, risking the exclusion of veridical computational‐level theories from scientific investigation. An argument is made to replace the P‐Cognition thesis by the FPT‐Cognition thesis as an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed‐parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified. (shrink)

FDE, LP and K3 are closely related to each other and admit of an intuitive informational interpretation. However, all these logics are co-NP complete, and so idealized models of how an agent can think. We address this issue by shifting to signed formulae, where the signs express imprecise values associated with two bipartitions of the corresponding set of standard values. We present proof systems whose operational rules are all linear and have only two structural branching rules that express a generalized (...) Principle of Bivalence. Each of these systems leads to defining an infinite hierarchy of tractable approximations to the respective logic, in terms of the maximum number of allowed nested applications of the two branching rules. Further, each resulting hierarchy admits of an intuitive 5-valued non-deterministic semantics. (shrink)

:We propose to strengthen Popper’s notion of falsifiability by adding the requirement that when an observation is inconsistent with a theory, there must be a ‘short proof’ of this inconsistency. We model the concept of a short proof using tools from computational complexity, and provide some examples of economic theories that are falsifiable in the usual sense but not with this additional requirement. We consider several variants of the definition of ‘short proof’ and several assumptions about the difficulty of computation, (...) and study their different implications on the falsifiability of theories. (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.

The depth-bounded approach seeks to provide realistic models of reasoners. Recognizing that most useful logics are idealizations in that they are either undecidable or likely to be intractable, the approach accounts for how they can be approximated in practice by resource-bounded agents. The approach has been applied to Classical Propositional Logic (CPL), yielding a hierarchy of tractable depth-bounded approximations to that logic, which in turn has been based on a KE/KI system. -/- This Thesis shows that the approach can be (...) naturally extended to useful nonclassical logics such as First-Degree Entailment (FDE), the Logic of Paradox (LP), Strong Kleene Logic (K3 ) and Intuitionistic Propositional Logic (IPL). To do this, we introduce a KE/KI-style system for each of those logics such that: is formulated via signed formulae, consist of linear operational rules and branching structural rule(s), can be used as a direct-proof and a refutation method, and is interesting independently of the approach in that it has an exponential speed-up on its tableau system counterpart. The latter given that we introduce a new class of examples which we prove to be hard for all tableau systems sharing the V/& rules with the classical one, but easy for their analogous KE-style systems. Then we focus on showing that each of our KE/KI-style systems naturally yields a hierarchy of tractable depth-bounded approximations to the respective logic, in terms of the maximum number of allowed nested applications of the branching rule(s). The rule(s) express(es) a generalized rule of bivalence, is (are) essentially cut rule(s) and govern(s) the manipulation of virtual information, which is information that an agent does not hold but she temporarily assumes as if she held it. Intuitively, the more virtual information needs to be invoked via the branching rule(s), the harder the inference is for the agent. So, the nested application the branching rule(s) provides a sensible measure of inferential depth. We also show that each hierarchy approximating FDE, LP, and K3 , admits of a 5-valued non-deterministic semantics; whereas, paving the way for a semantical characterization of the hierarchy approximating IPL, we provide a 3-valued non-deterministic semantics for the full logic that fixes the meaning of the connectives without appealing to “structural” conditions. -/- Moreover, we show a super-polynomial lower bound for the strongest possible version of clausal tableaux on the well-known class of “truly fat” expressions (which are easy for KE), settling a problem left open in the literature. Further, we investigate a hierarchy of tractable depth-bounded approximations to CPL based only on KE. Finally, we propose a refinement of the p-simulation relation which is adequate to establish positive results about the superiority of a system over another with respect to proof-search. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...) evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

This chapter examines the scope and limits of the tractability argument. It argues for two claims. First, that when explored with appropriate care and attention, it becomes clear that the argument provides no good reason to prefer massive modularity to the more traditional rationalist alternative. Second, while it is denied that tractability considerations support massive modularity per se, this does not mean that they show nothing whatsoever. Careful analysis of tractability considerations suggests a range of characteristics that (...) any plausible version of psychological rationalism is likely to possess. The chapter proceeds as follows: Section 1 outlines and clarifies the general form of the tractability argument. Section 2 explains how massive modularity is supposed to resolve intractability worries. Sections 3 to 7 highlight the deficiencies of the main extant arguments for claiming that nonmodular mechanisms are intractable. Section 8 concludes by sketching some of the general characteristics that a plausible rationalist alternative to massive modularity — one capable of subserving tractable cognitive processes — is likely to possess. (shrink)

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, (...) to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)

Much like admissibility is the key concept underlying preferred semantics, strong admissibility is the key concept underlying grounded semantics, as membership of a strongly admissible set is sufficient to show membership of the grounded extension. As such, strongly admissible sets and labellings can be used as an explanation of membership of the grounded extension, as is for instance done in some of the proof procedures for grounded semantics. In the current paper, we present two polynomial algorithms for constructing relatively small (...) strongly admissible labellings, with associated min–max numberings, for a particular argument. These labellings can be used as relatively small explanations for the argument’s membership of the grounded extension. Although our algorithms are not guaranteed to yield an absolute minimal strongly admissible labelling for the argument (as doing so would have implied an exponential complexity), our best performing algorithm yields results that are only marginally larger. Moreover, the runtime of this algorithm is an order of magnitude smaller than that of the existing approach for computing an absolute minimal strongly admissible labelling for a particular argument. As such, we believe that our algorithms can be of practical value in situations where the aim is to construct a minimal or near-minimal strongly admissible labelling in a time-efficient way. (shrink)

In this paper we study the semantic data complexity of several controlled fragments of English designed for natural language front-ends to OWL (Web Ontology Language) and description logic ontology-based systems. Controlled languages are fragments of natural languages, obtained by restricting natural language syntax, vocabulary and semantics with the goal of eliminating ambiguity. Semantic complexity arises from the formal logic modelling of meaning in natural language and fragments thereof. It can be characterized as the computational complexity of the reasoning problems associated (...) to their semantic representations. Data complexity (the complexity of answering a question over an ontology, stated in terms of the data items stored therein), in particular, provides a measure of the scalability of controlled languages to ontologies, since tractable data complexity implies scalability of data access. We present maximal tractable controlled languages and minimal intractable controlled languages. (shrink)

Perception solves computationally demanding problems at lightning fast speed. It recovers sophisticated representations of the world from degraded inputs, often in a matter of milliseconds. Any theory of perception must be able to explain how this is possible; in other words, it must be able to explain perception's computational tractability. One of the few attempts to move toward such an explanation has been the information encapsulation hypothesis, which posits that perception can be fast because it keeps computational costs low (...) by forgoing access to information stored in cognition. I argue that we have no compelling reason to believe that encapsulation explains (or even contributes to an explanation of) perceptual tractability, and much reason to doubt it. This is because there exist much deeper computational challenges for perception than information access, and these threaten to make the costs of access irrelevant. If this is right, it undermines a core computational motivation for encapsulation and sends us back to the drawing board for explanations of perceptual tractability. (shrink)

Lisciandra poses a challenge for robustness analysis as applied to economic models. She argues that substituting tractability assumptions risks altering the main mathematical structure of the model, thereby preventing the possibility of meaningfully evaluating the same model under different assumptions. In such cases RA is argued to be inapplicable. However, Lisciandra is mistaken to take the goal of RA as keeping the mathematical properties of tractability assumptions intact. Instead, RA really aims to keep the modeling component while varying (...) the corresponding mathematical formulation. Thus, her argument concerning whether the associated mathematical properties of certain assumptions can be kept intact is irrelevant to the success of RA. Furthermore, we explicate and develop Lloyd’s account of “model robustness” to provide solutions to Lisciandra’s challenges. Our solutions are, namely, error analysis and independent empirical support. We conclude that although complex economic models do face potential dangers, there are solutions and robustness analysis need not be given up.. (shrink)

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as (...) computational models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order (classical) systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...) is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

There continues to be significant confusion about the goals, scope, and nature of modelling practice in neuroeconomics. This article aims to dispel some such confusion by using one of the most recent critiques of neuroeconomic modelling as a foil. The article argues for two claims. First, currently, for at least some economic model of choice behaviour, the benefits derivable from neurally informing an economic model do not involve special tractability costs. Second, modelling in neuroeconomics is best understood within Marr’s (...) three-level of analysis framework and in light of a co-evolutionary research ideology. The first claim is established by elucidating the relationship between the tractability of a model, its descriptive accuracy, and its number of variables. The second claim relies on an explanation of what it can take to neurally inform an economic model of choice behaviour. 1 Introduction2 Neurally Informed Models of Choice: A Case Study2.1 A case study on risk-sensitive choice2.1.1 Target and modelling framework2.1.2 Research question and hypotheses2.1.3 Competitive models of risk-sensitive behaviour2.1.4 Model-based fMRI: from economics to brains and back2.2 Neurally informed modelling3 Tractability: When Does Size Matter?4 Neural Integration and the Co-evolutionary Research Ideology5 Conclusion. (shrink)

How can we prove that some fragment of a given logic has the power to define precisely all structural properties that satisfy some characteristic semantic preservation condition? This issue is a fundamental one for classical model theory and applications in non-classical settings alike. While methods differ greatly, and while the classical methods can usually not be matched for instance in the setting of finite model theory, this note surveys some interesting commonality revolving around the use and availability of tractable representatives (...) in the relevant model classes. The construction of models in which simple invariants like partial types based on some weak fragment control all the relevant structural properties, may be seen at the heart of such questions. We highlight some constructions involving degrees of acyclicity and saturation that can be achieved in finite model constructions, and discuss their uses towards expressive completeness w.r.t. bisimulation based equivalences in hypergraphs and relational structures. The emphasis is on the combinatorial challenges in such more constructive approaches that work in non-classical settings and especially in finite model theory. One new result concerns expressive completeness w.r.t. guarded negation bisimulation, a back-and-forth equivalence involving local homomorphisms. (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)

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets , introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC-nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, (...) and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MC-nets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks. (shrink)

Many compelling examples have recently been provided in which people can achieve impressive epistemic success, e.g. draw highly accurate inferences, by using simple heuristics and very little information. This is possible by taking advantage of the features of the environment. The examples suggest an easy and appealing naturalization of rationality: on the one hand, people clearly can apply simple heuristics, and on the other hand, they intuitively ought do so when this brings them high accuracy at little cost.. The ‘ought-can’ (...) principle is satisfied, and rationality is meaningfully normative. We show, however, that this naturalization program is endangered by a computational wrinkle in the adaptation process taken to be responsible for this heuristics-based (‘ecological’) rationality: for the adaptation process to guarantee even minimal rationality, it requires astronomical computational resources, making the problem intractable. We consider various plausible auxiliary assumptions in attempt to remove this obstacle, and show that they do not succeed; intractability is a robust property of adaptation. We discuss the implications of our findings for the project of naturalizing rationality. (shrink)

In the philosophy of science and epistemology literature, robustness analysis has become an umbrella term that refers to a variety of strategies. One of the main purposes of this paper is to argue that different strategies rely on different criteria for justifications. More specifically, I will claim that: i) robustness analysis differs from de-idealization even though the two concepts have often been conflated in the literature; ii) the comparison of different model frameworks requires different justifications than the comparison of models (...) that differ only for the assumption under test; iii) the replacement of specific assumptions with different ones can encounter specific difficulties in scientific practice. These claims will be supported by a case study in population ecology and a case study in geographical economics. (shrink)

Risk attitude is known to be a key determinant of various economic and financial choices. Behavioral studies that aim to evaluate the role of risk attitudes in contexts of this type, therefore, require tools for measuring individual risk tolerance. Recent developments in decision theory provide such tools. However, the methods available can be time consuming. As a result, some practitioners might have an incentive to prefer “fast and frugal” methods to clean but more costly methods. In this article, we focus (...) on a tractable procedure initially proposed by Holt and Laury (2002) to elicit risk attitude. We generalize this method to measure utility and risk aversion as follows. First, we allow measurement of probabilistic risk attitude through violations of expected utility due to probability weighting. Second, we use the outcome scale rather than the probability scale in the menu of choices. Third, we compare sure payoffs with lotteries instead of comparing non-degenerate lotteries. A within-subject experimental study illustrates the gains in tractability and bias minimization that can result from such an extension. (shrink)

Burt's critique of using polygenic scores in social science conflates the “scientific costs” of sociogenomics with “sociopolitical and ethical” concerns. Furthermore, she paradoxically enlists recent advances in controlling for environmental confounding to argue such confounding is scientifically “intractable.” Disinterested social scientists should support ongoing efforts to improve this technology rather than obstructing progress and excusing genetically confounded research.

We present a rational model of consumer choice, which can also serve as a behavioral model. The central construct is λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document}, the marginal utility of money, derived from the consumer’s rest-of-life problem. It provides a simple criterion for choosing a consumption bundle in a separable consumption problem. We derive a robust approximation of λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document} and show how to incorporate liquidity constraints, (...) indivisibilities, and adaptation to a changing environment. We find connections with numerous historical and recent constructs, both behavioral and neoclassical, and draw contrasts with standard partial equilibrium analysis. The result is a better grounded, more flexible, and more intuitive description of consumer choice. (shrink)

We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-hard). In particular, (...) we investigate the impact of assuming information structures to be partition-based (rather than arbitrary relational structures) on the complexity of various problems. We focus on the tractability of concrete epistemic tasks and not on epistemic logics describing them. (shrink)