Search results for 'Computational complexity' (try it on Scholar)

1000+ found
Order:
  1.  45
    Jakub Szymanik (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. 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 (...)
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography   9 citations  
  2.  56
    Jakub Szymanik (2010). Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language. 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   7 citations  
  3.  1
    Klaus Weirauch (2003). Computational Complexity on Computable Metric Spaces. 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 (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  4.  5
    Felix Brandt, Felix Fischer & Paul Harrenstein (2009). The Computational Complexity of Choice Sets. 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 (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  5.  24
    Fabian Schlotterbeck & Oliver Bott (2013). Easy Solutions for a Hard Problem? The Computational Complexity of Reciprocals with Quantificational Antecedents. 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  
  6.  30
    Theodor Leiber (1999). Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW] 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  
  7.  24
    Jakub Szymanik (2009). The Computational Complexity of Quantified Reciprocals. 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.
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography  
  8.  25
    Patrick Blackburn & Edith Spaan (1993). A Modal Perspective on the Computational Complexity of Attribute Value Grammar. 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.  49
    Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. 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 (...)
    Translate
      Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  10.  26
    Jeanne Ferrante (1979). The Computational Complexity of Logical Theories. 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.  17
    Pascal Michel (2007). Computational Complexity of Logical Theories of One Successor and Another Unary Function. 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  
  12. Gregory J. Chaitin (1970). Computational Complexity and Godel's Incompleteness Theorem. [Rio De Janeiro,Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
     
    Export citation  
     
    My bibliography   2 citations  
  13.  22
    Jarmo Kontinen (2013). Coherence and Computational Complexity of Quantifier-Free Dependence Logic Formulas. 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  
  14.  56
    Adam Morton (2004). Epistemic Virtues, Metavirtues, and Computational Complexity. 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 (10 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  15. Harvey Friedman, Lecture Notes on Term Rewriting and Computational Complexity.
    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  
  16.  1
    C. Areces, P. Blackburn & M. Marx (2000). The Computational Complexity of Hybrid Temporal Logics. 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   7 citations  
  17.  8
    Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. 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 (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  18.  5
    Karl-Heinz Niggl (2000). The $Mu$-Measure as a Tool for Classifying Computational Complexity. 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 (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  19.  34
    Professor Adam Morton (2004). Epistemic Virtues, Metavirtues, and Computational Complexity. 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 (8 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  20. Kevin J. Compton & C. Ward Henson (1990). A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories. 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 (2 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  21.  12
    Aleksandar Ignjatović (1995). Delineating Classes of Computational Complexity Via Second Order Theories with Weak Set Existence Principles. I. 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 (11 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  22.  3
    Ker-I. Ko (1992). On the Computational Complexity of Integral Equations. 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  
  23.  4
    Todd Wareham, Iris van Rooij & Moritz Müller (2008). Computational Complexity Analysis Can Help, but First We Need a Theory. 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  
     
    My bibliography  
  24.  16
    Todd Wareham, Iris van Rooij & Moritz Müller (2008). Computational Complexity Analysis Can Help, but First We Need a Theory. 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  25.  3
    Kevin J. Compton & C. Ward Henson (1990). A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories. 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  
  26.  57
    Matthias Scheutz (2001). Computational Vs. Causal Complexity. 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  
  27.  16
    Martin Dyer & Leen Stougie (2005). Computational Complexity of Stochastic Programming Problems. Complexity 1 (13):21.
  28. McGraw-Hill, Computational Complexity and Godel's Incompleteness Theorem.
    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  
  29.  7
    P. Oliva (2002). On the Computational Complexity of Best L~1-Approximation. 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].
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  30.  20
    David Danks, Clark Glymour & Peter Spirtes (2003). The Computational and Experimental Complexity of Gene Perturbations for Regulatory Network Search. 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  31.  1
    Karl-Heinz Niggl (1995). Towards the Computational Complexity of ℘Rω-Terms. 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  
  32.  1
    Karl-Heinz Niggl (1995). Towards the Computational Complexity of℘ Rω-Terms. 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  
  33. Karl-Heinz Niggl (2005). Control Structures in Programs and Computational Complexity. 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.  40
    I. Pitowsky (1996). Laplace's Demon Consults an Oracle: The Computational Complexity of Prediction. Studies in History and Philosophy of Science Part B 27 (2):161-180.
  35.  14
    Antonín Kučera & André Nies (2011). Demuth Randomness and Computational Complexity. 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   1 citation  
  36.  19
    Robert I. Soare (1977). Computational Complexity, Speedable and Levelable Sets. Journal of Symbolic Logic 42 (4):545-563.
  37. Matthias Scheutz (2001). Causal Vs. Computational Complexity? Minds and Machines 11:534-566.
  38.  46
    Christopher Cherniak (1984). Computational Complexity and the Universal Acceptance of Logic. Journal of Philosophy 81 (12):739-758.
  39.  10
    Alasdair Urquhart (2015). 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] Philosophia Mathematica 23 (3):435-438.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  40.  19
    Larry Stockmeyer (1987). Classifying the Computational Complexity of Problems. Journal of Symbolic Logic 52 (1):1-43.
  41.  9
    Marcin Mostowski Jakub Szymanik & M. Mostowski (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. Bulletin of Symbolic Logic 13:281-282.
    Direct download  
     
    Export citation  
     
    My bibliography  
  42.  4
    Koji Takamiya & Akira Tanaka (2016). Computational Complexity in the Design of Voting Rules. Theory and Decision 80 (1):33-41.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  43.  6
    Vicki Knoblauch (2008). Binary Relations: Finite Characterizations and Computational Complexity. [REVIEW] 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  
  44. Libo Lo (1988). On the Computational Complexity of the Theory of Abelian Groups. Annals of Pure and Applied Logic 37 (3):205-248.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  45.  4
    Robert E. Byerly (1984). Definability of Recursively Enumerable Sets in Abstract Computational Complexity Theory. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 30 (32-34):499-503.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  46.  10
    Norbert Hornstein (2013). Remarks on Computational Complexity: Response to Abels. Mind and Language 28 (4):430-434.
  47.  5
    Peter Gärdenfors, Computational Complexity and Cognitive Science : How the Body and the World Help the Mind Be Efficient.
    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  
     
    Export citation  
     
    My bibliography  
  48.  4
    Daniel Leivant (1999). Ramified Recurrence and Computational Complexity III: Higher Type Recurrence and Elementary Complexity. Annals of Pure and Applied Logic 96 (1-3):209-229.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  49.  16
    Donald A. Alton (1976). Diversity of Speed-Ups and Embeddability in Computational Complexity. Journal of Symbolic Logic 41 (1):199-214.
  50.  21
    Barry E. Jacobs (1977). On Generalized Computational Complexity. Journal of Symbolic Logic 42 (1):47-58.
1 — 50 / 1000