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

1000+ 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  
     
    My bibliography  
     
    Export citation  
  9. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Felix Brandt, Felix Fischer & Paul Harrenstein (2009). The Computational Complexity of Choice Sets. Mathematical Logic Quarterly 55 (4):444-459.score: 210.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  11. 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  
  12. Klaus Weirauch (2003). Computational Complexity on Computable Metric Spaces. Mathematical Logic Quarterly 49 (1):3-21.score: 210.0
    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. 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  
  15. 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  
  16. 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  
  17. 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  
  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
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  26. P. Oliva (2002). On the Computational Complexity of Best L~1-Approximation. Mathematical Logic Quarterly 48 (S1):66-77.score: 154.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  27. 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
  28. Christopher Cherniak (1984). Computational Complexity and the Universal Acceptance of Logic. Journal of Philosophy 81 (12):739-758.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
    Direct download  
     
    My bibliography  
     
    Export citation  
  36. 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  
  37. 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  
  38. 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
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  39. 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  
  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
    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
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  42. Patrick Doyle (2003). Computability and Computational Complexity. In L. Nadel (ed.), Encyclopedia of Cognitive Science. Nature Publishing Group.score: 150.0
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  43. Norbert Hornstein (2013). Remarks on Computational Complexity: Response to Abels. Mind and Language 28 (4):430-434.score: 150.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  44. Karl-Heinz Niggl (1995). Towards the Computational Complexity Of. Annals of Pure and Applied Logic 75 (1-2):153-178.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  45. Karl-Heinz Niggl (1995). Towards the Computational Complexity of℘ Rω-Terms. Annals of Pure and Applied Logic 75 (1):153-178.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  46. 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  
  47. 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  
  48. 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  
  49. Robert E. Byerly (1984). Definability of Recursively Enumerable Sets in Abstract Computational Complexity Theory. Mathematical Logic Quarterly 30 (32‐34):499-503.score: 150.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  50. 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
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 1000