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

998 found
Sort by:
  1. 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.score: 242.0
    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 to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  2. Jakub Szymanik (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. Dissertation, University of Amsterdamscore: 240.0
    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 to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  3. Theodor Leiber (1999). Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW] Journal for General Philosophy of Science 30 (1):87-101.score: 240.0
    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 (...)
    Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  4. Jakub Szymanik (2010). Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language. Linguistics and Philosophy 33 (3):215-250.score: 240.0
    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)  
     
    My bibliography  
     
    Export citation  
  5. 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.score: 240.0
    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)  
     
    My bibliography  
     
    Export citation  
  6. 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.score: 234.0
    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 (5 more)  
     
    My bibliography  
     
    Export citation  
  7. Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. Bulletin of Symbolic Logic 13:281--282.score: 228.0
    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 to English
    | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Jeanne Ferrante (1979). The Computational Complexity of Logical Theories. Springer-Verlag.score: 210.0
    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)  
     
    My bibliography  
     
    Export citation  
  9. 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.score: 210.0
     
    My bibliography  
     
    Export citation  
  10. Pascal Michel (2007). Computational Complexity of Logical Theories of One Successor and Another Unary Function. Archive for Mathematical Logic 46 (2):123-148.score: 210.0
    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)  
     
    My bibliography  
     
    Export citation  
  11. Felix Brandt, Felix Fischer & Paul Harrenstein (2009). The Computational Complexity of Choice Sets. Mathematical Logic Quarterly 55 (4):444-459.score: 210.0
    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)  
     
    My bibliography  
     
    Export citation  
  12. Klaus Weirauch (2003). Computational Complexity on Computable Metric Spaces. Mathematical Logic Quarterly 49 (1):3-21.score: 210.0
    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)  
     
    My bibliography  
     
    Export citation  
  13. Jarmo Kontinen (2013). Coherence and Computational Complexity of Quantifier-Free Dependence Logic Formulas. Studia Logica 101 (2):267-291.score: 192.0
    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)  
     
    My bibliography  
     
    Export citation  
  14. Harvey Friedman, Lecture Notes on Term Rewriting and Computational Complexity.score: 180.0
    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.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Adam Morton (2004). Epistemic Virtues, Metavirtues, and Computational Complexity. Noûs 38 (3):481–502.score: 180.0
    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)  
     
    My bibliography  
     
    Export citation  
  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.score: 180.0
    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)  
     
    My bibliography  
     
    Export citation  
  17. Professor Adam Morton (2004). Epistemic Virtues, Metavirtues, and Computational Complexity. Noûs 38 (3):481-502.score: 180.0
    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)  
     
    My bibliography  
     
    Export citation  
  18. 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.score: 180.0
    Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).
    Direct download (11 more)  
     
    My bibliography  
     
    Export citation  
  19. Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. Bulletin of Symbolic Logic 14 (1):1-28.score: 180.0
    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)  
     
    My bibliography  
     
    Export citation  
  20. Karl-Heinz Niggl (2000). The $Mu$-Measure as a Tool for Classifying Computational Complexity. Archive for Mathematical Logic 39 (7):515-539.score: 180.0
    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)  
     
    My bibliography  
     
    Export citation  
  21. 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.score: 180.0
    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)  
     
    My bibliography  
     
    Export citation  
  22. Matthias Scheutz (2001). Computational Vs. Causal Complexity. Minds and Machines 11 (4):543-566.score: 174.0
    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 (19 more)  
     
    My bibliography  
     
    Export citation  
  23. McGraw-Hill, Computational Complexity and Godel's Incompleteness Theorem.score: 162.0
    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..
    Direct download  
     
    My bibliography  
     
    Export citation  
  24. 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.score: 156.0
    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)  
     
    My bibliography  
     
    Export citation  
  25. Martin Dyer & Leen Stougie (2005). Computational Complexity of Stochastic Programming Problems. Complexity 1 (13):21.score: 156.0
  26. P. Oliva (2002). On the Computational Complexity of Best L~1-Approximation. Mathematical Logic Quarterly 48 (S1):66-77.score: 154.0
    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 (5 more)  
     
    My bibliography  
     
    Export citation  
  27. Christopher Cherniak (1984). Computational Complexity and the Universal Acceptance of Logic. Journal of Philosophy 81 (12):739-758.score: 150.0
  28. 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.score: 150.0
  29. Robert I. Soare (1977). Computational Complexity, Speedable and Levelable Sets. Journal of Symbolic Logic 42 (4):545-563.score: 150.0
  30. Donald A. Alton (1976). Diversity of Speed-Ups and Embeddability in Computational Complexity. Journal of Symbolic Logic 41 (1):199-214.score: 150.0
  31. Barry E. Jacobs (1977). On Generalized Computational Complexity. Journal of Symbolic Logic 42 (1):47-58.score: 150.0
  32. Frank Wimberly, David Danks, Clark Glymour & Tianjiao Chu, Problems for Structure Learning: Aggregation and Computational Complexity.score: 150.0
  33. Larry Stockmeyer (1987). Classifying the Computational Complexity of Problems. Journal of Symbolic Logic 52 (1):1-43.score: 150.0
  34. Viggo Stoltenberg-Hansen (1980). On Computational Complexity in Weakly Admissible Structures. Journal of Symbolic Logic 45 (2):353-358.score: 150.0
  35. 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.score: 150.0
    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)  
     
    My bibliography  
     
    Export citation  
  36. Antonín Kučera & André Nies (2011). Demuth Randomness and Computational Complexity. Annals of Pure and Applied Logic 162 (7):504-513.score: 150.0
    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)  
     
    My bibliography  
     
    Export citation  
  37. Peter van Emde Boas (1989). Review: K. Wagner, G. Wechsung, Computational Complexity. [REVIEW] Journal of Symbolic Logic 54 (2):622-624.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  38. Jiri Becvar (1967). Review: J. Hartmanis, R. E. Stearns, On the Computational Complexity of Algorithms. [REVIEW] Journal of Symbolic Logic 32 (1):120-121.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  39. Fernando Ferreira (1995). Arithmetic, Proof Theory, and Computational Complexity, Edited by Clote Peter and Jan Krajíček, Oxford Logic Guides, No. 23, Clarendon Press, Oxford University Press, Oxford and New York 1993, Xiii+ 428 Pp. [REVIEW] Journal of Symbolic Logic 60 (3):1014-1017.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  40. Klaus Aehlig & Arnold Beckmann (2010). On the Computational Complexity of Cut-Reduction. Annals of Pure and Applied Logic 161 (6):711-736.score: 150.0
    Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. Explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  41. Marcin Blachnik & Mirosław Kordos (2012). Computational Complexity Reduction and Interpretability Improvement of Distance-Based Decision Trees. In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. 288--297.score: 150.0
  42. Patrick Doyle (2003). Computability and Computational Complexity. In L. Nadel (ed.), Encyclopedia of Cognitive Science. Nature Publishing Group.score: 150.0
  43. Norbert Hornstein (2013). Remarks on Computational Complexity: Response to Abels. Mind and Language 28 (4):430-434.score: 150.0
  44. Nikolai Kossovski (2001). Computational Complexity of Quantifier-Free Negationless Theory of Field of Rational Numbers. Annals of Pure and Applied Logic 113 (1-3):175-180.score: 150.0
    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 (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  45. 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.score: 150.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  46. Karl-Heinz Niggl (1995). Towards the Computational Complexity Of. Annals of Pure and Applied Logic 75 (1-2):153-178.score: 150.0
    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)  
     
    My bibliography  
     
    Export citation  
  47. Karl-Heinz Niggl (1995). Towards the Computational Complexity of℘ Rω-Terms. Annals of Pure and Applied Logic 75 (1):153-178.score: 150.0
    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)  
     
    My bibliography  
     
    Export citation  
  48. Uwe Schöning (1991). Computational Complexity Theory, Edited by Hartmanis Juris, Proceedings of Symposia in Applied Mathematics, Vol. 38, American Mathematical Society, Providence 1989, Ix+ 128 Pp. [REVIEW] Journal of Symbolic Logic 56 (1):335-336.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  49. Jiri Becvar (1967). Review: J. Hartmanis, R. E. Stearns, Computational Complexity of Recursive Sequences. [REVIEW] Journal of Symbolic Logic 32 (1):121-122.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  50. Peter van Emde Boas (1989). Wagner K. And Wechsung G., Computational Complexity, Mathematics and its Applications. VEB Deutscher Verlag der Wissenschaften, Berlin, and D. Reidel Publishing Company, Dordrecht Etc., 1986, 551 Pp. [REVIEW] Journal of Symbolic Logic 54 (2):622-624.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
1 — 50 / 998