Results for 'Computational complexity'

1000+ found
Order:
  1.  49
    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  
    Translate
     
     
    Export citation  
     
    My bibliography   9 citations  
  2.  70
    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 (9 more)  
     
    Export citation  
     
    My bibliography   8 citations  
  3.  1
    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 (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  4.  29
    Easy Solutions for a Hard Problem? The Computational Complexity of Reciprocals with Quantificational Antecedents.Fabian Schlotterbeck & Oliver Bott - 2013 - Journal of Logic, Language and Information 22 (4):363-390.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  5.  32
    Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
    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 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 (...)
    Direct download (10 more)  
     
    Export citation  
     
    My bibliography  
  6.  27
    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.
    Direct download  
    Translate
     
     
    Export citation  
     
    My bibliography  
  7.  5
    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 (3 more)  
     
    Export citation  
     
    My bibliography  
  8.  33
    A Modal Perspective on the Computational Complexity of Attribute Value Grammar.Patrick Blackburn & Edith Spaan - 1993 - Journal of Logic, Language and Information 2 (2):129-169.
    Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  9.  59
    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 (3 more)  
    Translate
     
     
    Export citation  
     
    My bibliography   2 citations  
  10.  30
    The Computational Complexity of Logical Theories.Jeanne Ferrante - 1979 - Springer Verlag.
    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 ...
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   11 citations  
  11. 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.
     
    Export citation  
     
    My bibliography   2 citations  
  12.  18
    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  
     
    My bibliography  
  13. Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer.Michael Cuffaro - forthcoming - In Sven Ove Hansson (ed.), Technology and Mathematics: Philosophical and Historical Investigations. Springer.
  14.  25
    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  
     
    My bibliography   1 citation  
  15.  6
    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  
     
    My bibliography   13 citations  
  16.  84
    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 (9 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  17. Lecture Notes on Term Rewriting and Computational Complexity.Harvey Friedman - manuscript
    The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.
     
    Export citation  
     
    My bibliography  
  18.  3
    A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories.J. Compton Kevin & C. Ward Henson - 1990 - Annals of Pure and Applied Logic 48 (1):1-79.
    A new method for obtaining lower bounds on the computational complexity of logical theories is presented. It extends widely used techniques for proving the undecidability of theories by interpreting models of a theory already known to be undecidable. New inseparability results related to the well known inseparability result of Trakhtenbrot and Vaught are the foundation of the method. Their use yields hereditary lower bounds . By means of interpretations lower bounds can be transferred from one theory to another. (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   10 citations  
  19.  9
    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 (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  20.  5
    The $Mu$-Measure as a Tool for Classifying Computational Complexity.Karl-Heinz Niggl - 2000 - Archive for Mathematical Logic 39 (7):515-539.
    Two simply typed term systems $\sf {PR}_1$ and $\sf {PR}_2$ are considered, both for representing algorithms computing primitive recursive functions. $\sf {PR}_1$ is based on primitive recursion, $\sf {PR}_2$ on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in $\sf {PR}_i$ , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  21.  40
    Epistemic Virtues, Metavirtues, and Computational Complexity.Professor 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  
     
    My bibliography   1 citation  
  22.  21
    Computational Complexity Analysis Can Help, but First We Need a Theory.Wareham Todd, Rooij Iris van & Müller Moritz - 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 (5 more)  
     
    Export citation  
     
    My bibliography  
  23.  14
    Delineating Classes of Computational Complexity Via Second Order Theories with Weak Set Existence Principles. I.Aleksandar Ignjatović - 1995 - Journal of Symbolic Logic 60 (1):103-121.
    Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).
    Direct download (12 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  24.  3
    On the Computational Complexity of Integral Equations.Ker-I. Ko - 1992 - Annals of Pure and Applied Logic 58 (3):201-228.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  25.  62
    Computational Vs. Causal Complexity.Matthias Scheutz - 2001 - Minds and Machines 11 (4):543-566.
    The main claim of this paper is that notions of implementation based on an isomorphic correspondence between physical and computational states are not tenable. Rather, ``implementation'' has to be based on the notion of ``bisimulation'' in order to be able to block unwanted implementation results and incorporate intuitions from computational practice. A formal definition of implementation is suggested, which satisfies theoretical and practical requirements and may also be used to make the functionalist notion of ``physical realization'' precise. The (...)
    Direct download (18 more)  
     
    Export citation  
     
    My bibliography   11 citations  
  26.  2
    Membrane Fission: A Computational Complexity Perspective.Luis F. Macías-Ramos, Bosheng Song, Luis Valencia-Cabrera, Linqiang Pan & Mario J. Pérez-jiménez - 2016 - Complexity 21 (6):321-334.
  27. 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 ). On the other hand, almost all finite binary sequences S satisfy L(S) > L(F ). The proof resembles Berry’s..
     
    Export citation  
     
    My bibliography  
  28.  19
    Computational Complexity of Stochastic Programming Problems.Martin Dyer & Leen Stougie - 2005 - Complexity 1 (13):21.
  29.  7
    On the Computational Complexity of Best L~1-Approximation.P. Oliva - 2002 - Mathematical Logic Quarterly 48 (S1):66-77.
    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].
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  30.  1
    Towards the Computational Complexity of ℘Rω-Terms.Karl-Heinz Niggl - 1995 - Annals of Pure and Applied Logic 75 (1-2):153-178.
    We investigate a simply typed term system ℘R ω aimed at defining partial primitive recursive functionals over arbitrary Scott domains . A hierarchy of complexity classes R n ω for functionals definable in ℘R ω is given based on a hierarchy of term classes ℘R n ωpn denoting the n th class of so-called prenormal terms . They come into play by the key observation that every term t can be transformed by what we call higher type modularization as (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  31.  1
    Towards the Computational Complexity of℘ Rω-Terms.Karl-Heinz Niggl - 1994 - Annals of Pure and Applied Logic 75 (1):153-178.
    We investigate a simply typed term system ℘R ω aimed at defining partial primitive recursive functionals over arbitrary Scott domains . A hierarchy of complexity classes R n ω for functionals definable in ℘R ω is given based on a hierarchy of term classes ℘R n ωpn denoting the n th class of so-called prenormal terms . They come into play by the key observation that every term t can be transformed by what we call higher type modularization as (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  32.  23
    The Computational and Experimental Complexity of Gene Perturbations for Regulatory Network Search.David Danks, Clark Glymour & Peter Spirtes - 2003 - In W. H. Hsu, R. Joehanes & C. D. Page (eds.), Proceedings of IJCAI-2003 workshop on learning graphical models for computational genomics.
    Various algorithms have been proposed for learning (partial) genetic regulatory networks through systematic measurements of differential expression in wild type versus strains in which expression of specific genes has been suppressed or enhanced, as well as for determining the most informative next experiment in a sequence. While the behavior of these algorithms has been investigated for toy examples, the full computational complexity of the problem has not received sufficient attention. We show that finding the true regulatory network requires (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  33.  1
    Control Structures in Programs and Computational Complexity.Karl-Heinz Niggl - 2005 - Annals of Pure and Applied Logic 133 (1-3):247-273.
    A key problem in implicit complexity is to analyse the impact on program run times of nesting control structures, such as recursion in all finite types in functional languages or for-do statements in imperative languages.Three types of programs are studied. One type of program can only use ground type recursion. Another is concerned with imperative programs: ordinary loop programs and stack programs. Programs of the third type can use higher type recursion on notation as in functional programming languages.The present (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  34.  17
    Demuth Randomness and Computational Complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  35.  10
    Computational Complexity of the Semantics of Some Natural Language Constructions.Marcin Mostowski & Dominika Wojtyniak - 2004 - Annals of Pure and Applied Logic 127 (1-3):219--227.
    We consider an example of a sentence which according to Hintikka's claim essentially requires for its logical form a Henkin quantifier. We show that if Hintikka is right then recognizing the truth value of the sentence in finite models is an NP-complete problem. We discuss also possible conclusions from this observation.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  36.  50
    Laplace's Demon Consults an Oracle: The Computational Complexity of Prediction.I. Pitowsky - 1996 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 27 (2):161-180.
  37.  3
    Computational Complexity and Human Decision-Making.Peter Bossaerts & Carsten Murawski - 2017 - Trends in Cognitive Sciences 21 (12):917-929.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  38.  19
    Computational Complexity, Speedable and Levelable Sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
  39.  8
    Laplace's Demon Consults an Oracle: The Computational Complexity of Prediction.Itamar Pitowsky - 1996 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 27 (2):161-180.
  40. Causal Vs. Computational Complexity?Matthias Scheutz - 2001 - Minds and Machines 11:534-566.
  41.  54
    Computational Complexity and the Universal Acceptance of Logic.Christopher Cherniak - 1984 - Journal of Philosophy 81 (12):739-758.
  42.  21
    Classifying the Computational Complexity of Problems.Larry Stockmeyer - 1987 - Journal of Symbolic Logic 52 (1):1-43.
  43. On the Computational Complexity of the Theory of Abelian Groups.Libo Lo - 1988 - Annals of Pure and Applied Logic 37 (3):205-248.
  44.  15
    Definability of Recursively Enumerable Sets in Abstract Computational Complexity Theory.Robert E. Byerly - 1984 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 30 (32-34):499-503.
  45.  16
    Binary Relations: Finite Characterizations and Computational Complexity[REVIEW]Vicki Knoblauch - 2008 - Theory and Decision 65 (1):27-44.
    A characterization of a property of binary relations is of finite type if it is stated in terms of ordered T-tuples of alternatives for some positive integer T. The concept was introduced informally by Knoblauch (2005). We give a clear, complete definition below. We prove that a characterization of finite type can be used to determine in polynomial time whether a binary relation over a finite set has the property characterized. We also prove a simple but useful nonexistence theorem and (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  46.  4
    Ramified Recurrence and Computational Complexity III: Higher Type Recurrence and Elementary Complexity.Daniel Leivant - 1999 - Annals of Pure and Applied Logic 96 (1-3):209-229.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  47.  13
    Computational Complexity in the Design of Voting Rules.Koji Takamiya & Akira Tanaka - 2016 - Theory and Decision 80 (1):33-41.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  48.  1
    Computational Complexity and the Universal Acceptance of Logic.Christopher Cherniak - 1984 - Journal of Philosophy 81 (12):739.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  49.  15
    Pavel Pudlák. Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction. Springer Monographs in Mathematics. Springer, 2013. ISBN: 978-3-319-00118-0 ; 978-3-319-00119-7 . Pp. Xiv + 695. [REVIEW]Alasdair Urquhart - 2015 - Philosophia Mathematica 23 (3):435-438.
  50.  16
    Remarks on Computational Complexity: Response to Abels.Norbert Hornstein - 2013 - Mind and Language 28 (4):430-434.
1 — 50 / 1000