Results for 'computational complexity'

951 found
Order:
  1.  91
    Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  35
    Computability, complexity, logic.Egon Börger - 1989 - New York, N.Y., U.S.A.: Elsevier Science Pub. Co..
    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, (...)
    Direct download  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  1
    Computational complexity and Godel's incompleteness theorem.Gregory J. Chaitin - 1970 - [Rio de Janeiro,: Centro Técnico Científico, Pontifícia Universidade Católica do Rio de Janeiro. Edited by Gregory J. Chaitin.
  4. Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2010 - Linguistics and Philosophy 33 (3):215-250.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  5.  29
    Computational complexity for bounded distributive lattices with negation.Dmitry Shkatov & C. J. Van Alten - 2021 - Annals of Pure and Applied Logic 172 (7):102962.
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  22
    Harnessing Computational Complexity Theory to Model Human Decision‐making and Cognition.Juan Pablo Franco & Carsten Murawski - 2023 - Cognitive Science 47 (6):e13304.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  92
    Universality, Invariance, and the Foundations of Computational Complexity in the light of the Quantum Computer.Michael Cuffaro - 2018 - In Hansson Sven Ove (ed.), Technology and Mathematics: Philosophical and Historical Investigations. Cham, Switzerland: Springer Verlag. pp. 253-282.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  8. The Computational Complexity of Quantified Reciprocals.Jakub Szymanik - 2009 - In Peter Bosch, David Gabelaia & Jérôme Lang (eds.), Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. Springer.
    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.
     
    Export citation  
     
    Bookmark   1 citation  
  9.  18
    Computational complexity on computable metric spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  10.  87
    Computational Complexity Theory and the Philosophy of Mathematics†.Walter Dean - 2019 - Philosophia Mathematica 27 (3):381-439.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11. Computational complexity of stochastic programming problems.Martin Dyer & Leen Stougie - 2005 - Complexity 1 (13):21.
  12.  37
    The computational complexity of hybrid temporal logics.C. Areces, P. Blackburn & M. Marx - 2000 - Logic Journal of the IGPL 8 (5):653-679.
    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 (...)
    Direct download  
     
    Export citation  
     
    Bookmark   28 citations  
  13.  67
    The computational complexity of logical theories.Jeanne Ferrante - 1979 - New York: Springer Verlag. Edited by Charles W. Rackoff.
    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 ...
  14.  13
    A Computational Complexity-Based Method for Predicting Scholars’ Ages through Articles’ Information.Jun Zhang, Xiaoyan Su, Mingliang Hou & Jing Ren - 2021 - Complexity 2021:1-15.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  22
    Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski Jakub Szymanik & M. Mostowski - 2007 - Bulletin of Symbolic Logic 13:281-282.
  16.  12
    The Computational Complexity of Choice Sets.Felix Brandt, Felix Fischer & Paul Harrenstein - 2009 - Mathematical Logic Quarterly 55 (4):444-459.
    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 (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  17. Computability, Complexity and Languages.Martin Davies, Ron Segal & Elaine Weyuker - 1994 - Academic Press.
     
    Export citation  
     
    Bookmark   23 citations  
  18.  40
    Computational complexity reduction and interpretability improvement of distance-based decision trees.Marcin Blachnik & Mirosław Kordos - 2012 - In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. pp. 288--297.
  19. Cognitive and Computational Complexity: Considerations from Mathematical Problem Solving.Markus Pantsar - 2019 - Erkenntnis 86 (4):961-997.
    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 (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  20.  26
    Computational complexity and cognitive science : How the body and the world help the mind be efficient.Peter Gärdenfors - unknown
    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, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  27
    The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules.Linqiang Pan, Bosheng Song, Luis Valencia-Cabrera & Mario J. Pérez-Jiménez - 2018 - Complexity 2018:1-21.
    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 (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  27
    Computational complexity in the design of voting rules.Koji Takamiya & Akira Tanaka - 2016 - Theory and Decision 80 (1):33-41.
    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.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23. Causal vs. computational complexity?Matthias Scheutz - 2001 - Minds and Machines 11:534-566.
  24.  22
    The computational complexity of propositional STRIPS planning.Tom Bylander - 1994 - Artificial Intelligence 69 (1-2):165-204.
  25.  22
    The computational complexity of probabilistic inference using bayesian belief networks.Gregory F. Cooper - 1990 - Artificial Intelligence 42 (2-3):393-405.
  26.  70
    Computational complexity of logical theories of one successor and another unary function.Pascal Michel - 2007 - Archive for Mathematical Logic 46 (2):123-148.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  27.  14
    The computational complexity of ideal semantics.Paul E. Dunne - 2009 - Artificial Intelligence 173 (18):1559-1591.
  28. Epistemic virtues, metavirtues, and computational complexity.Adam Morton - 2004 - Noûs 38 (3):481–502.
    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.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  29.  56
    Computational complexity analysis can help, but first we need a theory.Todd Wareham, Iris van Rooij & Moritz Müller - 2008 - Behavioral and Brain Sciences 31 (4):399-400.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  30.  62
    Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas.Jarmo Kontinen - 2013 - Studia Logica 101 (2):267-291.
    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).
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  31.  19
    Computational Complexity and the Universal Acceptance of Logic.Christopher Cherniak - 1984 - Journal of Philosophy 81 (12):739.
  32.  59
    Computational complexity, speedable and levelable sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
  33.  32
    Computational complexity of flat and generic Assumption-Based Argumentation, with and without probabilities.Kristijonas Čyras, Quentin Heinrich & Francesca Toni - 2021 - Artificial Intelligence 293 (C):103449.
  34.  6
    Computational complexity of planning and approximate planning in the presence of incompleteness.Chitta Baral, Vladik Kreinovich & Raúl Trejo - 2000 - Artificial Intelligence 122 (1-2):241-267.
  35.  16
    The computational complexity of abduction.Tom Bylander, Dean Allemang, Michael C. Tanner & John R. Josephson - 1991 - Artificial Intelligence 49 (1-3):25-60.
  36.  13
    The computational complexity of multi-agent pathfinding on directed graphs.Bernhard Nebel - 2024 - Artificial Intelligence 328 (C):104063.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  37.  8
    Computational complexity of terminological reasoning in BACK.Bernhard Nebel - 1988 - Artificial Intelligence 34 (3):371-383.
  38. Computational complexity and Godel's incompleteness theorem. McGraw-Hill - unknown
    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..
     
    Export citation  
     
    Bookmark   1 citation  
  39. Abstraction and computational complexity.D. Leivant - 1990 - Journal of Symbolic Logic 55:379-80.
  40.  32
    (1 other version)Conference on computability, complexity and randomness: Isaac Newton institute, cambridge, uk july 2-6, 2012.Elvira Mayordomo & Wolfgang Merkle - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Elvira Mayordomo and Wolfgang Merkle The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 135-136, March 2013.
    Direct download  
     
    Export citation  
     
    Bookmark  
  41.  12
    Computational complexity of relating time points with intervals.Peter Jonsson, Thomas Drakengren & Christer Bäckström - 1999 - Artificial Intelligence 109 (1-2):273-295.
  42.  18
    Why computational complexity may set impenetrable barriers for epistemic reductionism.Michael H. Herzog, Adrien Doerig & Christian Sachse - 2023 - Synthese 202 (5):1-13.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  43.  29
    On computational complexity in weakly admissible structures.Viggo Stoltenberg-Hansen - 1980 - Journal of Symbolic Logic 45 (2):353-358.
  44. Computability and computational complexity.Patrick Doyle - 2003 - In L. Nadel (ed.), Encyclopedia of Cognitive Science. Nature Publishing Group.
  45.  67
    On the computational complexity of the numerically definite syllogistic and related logics.Ian Pratt-Hartmann - 2008 - Bulletin of Symbolic Logic 14 (1):1-28.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  46. Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2009 - Dissertation, University of Amsterdam
    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 (...)
    Direct download  
     
    Export citation  
     
    Bookmark   13 citations  
  47.  23
    Computation, complexity, and systems in nature.Bradley W. Dickinson - 1990 - Behavioral and Brain Sciences 13 (3):447-447.
  48.  27
    Computational complexity explains neural differences in quantifier verification.Heming Strømholt Bremnes, Jakub Szymanik & Giosuè Baggio - 2022 - Cognition 223 (C):105013.
  49.  26
    Computational Complexity of Solving Equation Systems.Przemysław Broniek - unknown
    We present conclusions and open problems raising from studying solving equations over unary algebras. We suggest areas that are most promising for expanding our knowledge.
    Direct download  
     
    Export citation  
     
    Bookmark  
  50.  19
    The computational complexity of scenario-based agent verification and design.Yves Bontemps & Pierre-Yves Schobbens - 2007 - Journal of Applied Logic 5 (2):252-276.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 951