Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the (...) $\mathbf{P} \neq \mathbf{NP}$ problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (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)

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity (...) results to investigate semantic distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)

Following Marr’s famous three-level distinction between explanations in cognitive science, it is often accepted that focus on modeling cognitive tasks should be on the computational level rather than the algorithmic level. When it comes to mathematical problem solving, this approach suggests that the complexity of the task of solving a problem can be characterized by the computational complexity of that problem. In this paper, I argue that human cognizers use heuristic and didactic tools and thus engage (...) in cognitive processes that make their problem solving algorithms computationally suboptimal, in contrast with the optimal algorithms studied in the computational approach. Therefore, in order to accurately model the human cognitive tasks involved in mathematical problem solving, we need to expand our methodology to also include aspects relevant to the algorithmic level. This allows us to study algorithms that are cognitively optimal for human problem solvers. Since problem solving methods are not universal, I propose that they should be studied in the framework of enculturation, which can explain the expected cultural variance in the humanly optimal algorithms. While mathematical problem solving is used as the case study, the considerations in this paper concern modeling of cognitive tasks in general. (shrink)

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to (...) the problem of computational complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

We study the computational complexity of reciprocal sentences with quantified antecedents. We observe a computational dichotomy between different interpretations of reciprocity, and shed some light on the status of the so-called Strong Meaning Hypothesis.

We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.

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)

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)

This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.

This book asks not only how the study of white-collar crime can enrich our understanding of crime and justice more generally, but also how criminological ...

A central aim of cognitive science is to understand the fundamental mechanisms that enable humans to navigate and make sense of complex environments. In this letter, we argue that computational complexity theory, a foundational framework for evaluating computational resource requirements, holds significant potential in addressing this challenge. As humans possess limited cognitive resources for processing vast amounts of information, understanding how humans perform complex cognitive tasks requires comprehending the underlying factors that drive information processing demands. Computational (...) complexity theory provides a comprehensive theoretical framework to achieve this goal. By adopting this framework, we can gain new insights into how cognitive systems work and develop a more nuanced understanding of the relation between task complexity and human behavior. We provide empirical evidence supporting our argument and identify several open research questions and challenges in applying computational complexity theory to human decision‐making and cognitive science at large. (shrink)

The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems. The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, (...) and to the theory of formal languages and complexity theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory. It is both a textbook for introductory courses in the above-mentioned disciplines as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit the connections and analogies between a variety of concepts and constructions. (shrink)

Leech et al. present a connectionist algorithm as a model of (the development) of analogizing, but they do not specify the algorithm's associated computational-level theory, nor its computational complexity. We argue that doing so may be essential for connectionist cognitive models to have full explanatory power and transparency, as well as for assessing their scalability to real-world input domains.

Social choice rules are often evaluated and compared by inquiring whether they satisfy certain desirable criteria such as the Condorcet criterion, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise (...) majority relation. These sets include the Copeland set, the Smith set, the Schwartz set, von Neumann-Morgenstern stable sets, the Banks set, and the Slater set. We investigate the relationships between these sets and completely characterize their computational complexity, which allows us to obtain hardness results for entire classes of social choice rules. (shrink)

The first-order logical theory Th $({\mathbb{N}},x + 1,F(x))$ is proved to be complete for the class ATIME-ALT $(2^{O(n)},O(n))$ when $F(x) = 2^{x}$ , and the same result holds for $F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)$ , and F(x) = tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.

We study the computational complexity of the model checking problem for quantifier-free dependence logic ${(\mathcal{D})}$ formulas. We characterize three thresholds in the complexity: logarithmic space (LOGSPACE), non-deterministic logarithmic space (NL) and non-deterministic polynomial time (NP).

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations (...) of the theory. For model-independence never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n L(F ). The proof resembles Berry’s..

This book illustrates the program of Logical-Informational Dynamics. Rational agents exploit the information available in the world in delicate ways, adopt a wide range of epistemic attitudes, and in that process, constantly change the world itself. Logical-Informational Dynamics is about logical systems putting such activities at center stage, focusing on the events by which we acquire information and change attitudes. Its contributions show many current logics of information and change at work, often in multi-agent settings where social behavior is essential, (...) and often stressing Johan van Benthem's pioneering work in establishing this program. However, this is not a Festschrift, but a rich tapestry for a field with a wealth of strands of its own. The reader will see the state of the art in such topics as information update, belief change, preference, learning over time, and strategic interaction in games. Moreover, no tight boundary has been enforced, and some chapters add more general mathematical or philosophical foundations or links to current trends in computer science. (shrink)

Many scholars have conducted in-depth research on the evaluation and prediction of scholars’ scientific impact and meanwhile discovered various factors that affect the success of scholars. Among all these relevant factors, scholars’ ages have been universally acknowledged as one of the most important factors for it can shed light on many practical issues, e.g., finding supervisors, discovering rising stars, and research funding or award applications. However, due to the inaccessibility or the privacy issues of acquiring scholars’ personal data, there is (...) little research to explore the true ages of scholars currently. Alternatively, scholars’ publications’ information can be obtained through various digital libraries. Inspired by this fact, we propose a novel scholar’s age prediction method based on their articles’ information. Our method first classifies factors that affect scholars’ ages into intuitive and complex types according to their computational complexity and then apply machine learning algorithms to predict the ages of scholars based on these factors. The experimental results on the real dataset demonstrate that our method can effectively predict the true ages of scholars. Given that there is no completely accurate dataset because of the continuous publication of academic papers, we then apply our method on the incomplete dataset. Nevertheless, our method still has high prediction accuracy in such situations. (shrink)

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (...) (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed (...) in polynomial time. Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

This work is concerned with hierarchical modular descriptions, their algorithmic production, and their importance for certain types of scientific explanations of the structure and dynamical behavior of complex systems. Networks are taken into consideration as paradigmatic representations of complex systems. It turns out that algorithmic detection of hierarchical modularity in networks is a task plagued in certain cases by theoretical intractability and in most cases by the still high computational complexity of most approximated methods. A new notion, antimodularity, (...) is then proposed, which consists in the impossibility to algorithmically obtain a modular description fitting the explanatory purposes of the observer for reasons tied to the computational cost of typical algorithmic methods of modularity detection, in relation to the excessive size of the system under assessment and to the required precision. It turns out that occurrence of antimodularity hinders both mechanistic and functional explanation, by damaging their intelligibility. Another newly proposed more general notion, explanatory emergence, subsumes antimodularity under any case in which a system resists intelligible explanations because of the excessive computational cost of algorithmic methods required to obtain the relevant explanatory descriptions from the raw data. The possible consequences, and the likelihood, of incurring in antimodularity or explanatory emergence in the actual scientific practice are finally assessed, concluding that this eventuality is possible, at least in disciplines which are based on the algorithmic analysis of big data. The present work aims to be an example of how certain notions of theoretical computer science can be fruitfully imported into philosophy of science. (shrink)

Ko, K., On the computational complexity of integral equations, Annals of Pure and Applied Logic 58 201–228. The computational complexity of Volterra integral equations of the second kind and of the first kind is investigated. It is proved that if the kernel functions satisfy the Lipschitz condition, then the solutions of Volterra equations of the second kind are polynomial-space computable. If, one the other hand, the kernel functions only satisfy the local Lipschitz condition with the Lipschitz (...) constants growing in an exponential rate, then the solutions could be exponential-time hard. We identify a class of Volterra equations of the first kind that can be converted to Volterra equations of the second kind satisfying the local Lipschitz condition. The complexity of the solutions of these equations is also proved to be exponential-time hard. (shrink)

The following result is an approximation to the answer of the question of Kokorin about decidability of a quantifier-free theory of field of rational numbers. Let Q0 be a subset of the set of all rational numbers which contains integers 1 and −1. Let be a set containing Q0 and closed by the functions of addition, subtraction and multiplication. For example coincides with Q0 if Q0 is the set of all binary rational numbers or the set of all decimal rational (...) numbers. It is clear that , where Z is the set of all integers and Q is the set of all rational numbers. A negationless theory uses only conjunction and disjunction as logical connectives. Let T be a quantifier-free negationless elementary theory of signature , where Pol is the list of all polynomials with rational coefficients from Q0 in which exponent of the polynomials and rational coefficients are written in binary number system. Theorem 1. Theory T is NP-hard and if is everywhere dense then the theory T is decidable by an algorithm which belongs to EXPTIME. The set of all rational numbers or the set of all binary rational numbers may be taken instead of . The quantifier-free negationless theory of the field of rational numbers may be regarded as a base of constructive mathematics. (shrink)

Some problems rarely discussed in traditional philosophy of science are mentioned: The empirical sciences using mathematico-quantitative theoretical models are frequently confronted with several types of computational problems posing primarily methodological limitations on explanatory and prognostic matters. Such limitations may arise from the appearances of deterministic chaos and (too) high computational complexity in general. In many cases, however, scientists circumvent such limitations by utilizing reductional approximations or complexity reductions for intractable problem formulations, thus constructing new models which (...) are computationally tractable. Such activities are compared with reduction types (more) established in philosophy of science. (shrink)

I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.

We report two experiments which tested whether cognitive capacities are limited to those functions that are computationally tractable (PTIME-Cognition Hypothesis). In particular, we investigated the semantic processing of reciprocal sentences with generalized quantifiers, i.e., sentences of the form Q dots are directly connected to each other, where Q stands for a generalized quantifier, e.g. all or most. Sentences of this type are notoriously ambiguous and it has been claimed in the semantic literature that the logically strongest reading is preferred (Strongest (...) Meaning Hypothesis). Depending on the quantifier, the verification of their strongest interpretations is computationally intractable whereas the verification of the weaker readings is tractable. We conducted a picture completion experiment and a picture verification experiment to investigate whether comprehenders shift from an intractable reading to a tractable reading which should be dispreferred according to the Strongest Meaning Hypothesis. The results from the picture completion experiment suggest that intractable readings occur in language comprehension. Their verification, however, rapidly exceeds cognitive capacities in case the verification problem cannot be solved using simple heuristics. In particular, we argue that during verification, guessing strategies are used to reduce computational complexity. (shrink)

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).

According to physicalism, everything is physical or metaphysically connected to the physical. If physicalism were true, it seems that we should – in principle – be able to reduce the descriptions and explanations of special sciences to physical ones, for example, explaining biological regularities, via chemistry, by the laws of particle physics. The multiple realization of the property types of the special sciences is often seen to be an obstacle to such epistemic reductions. Here, we introduce another, new argument against (...) epistemic reduction. Based on mathematical complexity, we show that, under certain conditions, there can be “complexity barriers” that make epistemic reduction – in principle – unachievable even if physicalism were true. (shrink)

I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.