The Wayback Machine - https://web.archive.org/web/20210505051814/https://philpapers.org/browse/computational-complexity
This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories

0 found
Order:
  1. Is Classical Mathematics Appropriate for Theory of Computation?Farzad Didehvar - manuscript
    Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this paradox, it (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2. A Contradiction and P=NP Problem.Farzad Didehvar - manuscript
    Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  3. By Considering Fuzzy Time, P=BPP (P*=BPP*).Farzad Didehvar - manuscript
    The reason ability of considering time as a fuzzy concept is demonstrated in [7],[8]. One of the major questions which arise here is the new definitions of Complexity Classes. In [1],[2],…,[11] we show why we should consider time a fuzzy concept. It is noticeable to mention that that there were many attempts to consider time as a Fuzzy concept, in Philosophy, Mathematics and later in Physics but mostly based on the personal intuition of the authors or as a style of (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  4. Fuzzy Time, From Paradox to Paradox.Farzad Didehvar - manuscript
    Although Fuzzy logic and Fuzzy Mathematics is a widespread subject and there is a vast literature about it, yet the use of Fuzzy issues like Fuzzy sets and Fuzzy numbers was relatively rare in time concept. This could be seen in the Fuzzy time series. In addition, some attempts are done in fuzzing Turing Machines but seemingly there is no need to fuzzy time. Throughout this article, we try to change this picture and show why it is helpful to consider (...)
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  5. Strengthening Weak Emergence.Nora Berenstain - forthcoming - Erkenntnis:1-18.
    Bedau's influential (1997) account analyzes weak emergence in terms of the non-derivability of a system’s macrostates from its microstates except by simulation. I offer an improved version of Bedau’s account of weak emergence in light of insights from information theory. Non-derivability alone does not guarantee that a system’s macrostates are weakly emergent. Rather, it is non-derivability plus the algorithmic compressibility of the system’s macrostates that makes them weakly emergent. I argue that the resulting information-theoretic picture provides a metaphysical account of (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6. 1 Complexity of Computational Problems.D. B. Shmoys & E. Tardos - forthcoming - Complexity.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  7. Proof Theory for Positive Logic with Weak Negation.Marta Bílková & Almudena Colacito - 2020 - Studia Logica 108 (4):649-686.
    Proof-theoretic methods are developed for subsystems of Johansson’s logic obtained by extending the positive fragment of intuitionistic logic with weak negations. These methods are exploited to establish properties of the logical systems. In particular, cut-free complete sequent calculi are introduced and used to provide a proof of the fact that the systems satisfy the Craig interpolation property. Alternative versions of the calculi are later obtained by means of an appropriate loop-checking history mechanism. Termination of the new calculi is proved, and (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8. A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory.Vasil Penchev - 2020 - Information Theory and Research eJournal 1 (15):1-13.
    A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  9. Representation and Reality by Language: How to Make a Home Quantum Computer?Vasil Penchev - 2020 - Philosophy of Science eJournal (Elsevier: SSRN) 13 (34):1-14.
    A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having a remarkable (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  10. Two Strategies to Infinity: Completeness and Incompleteness. The Completeness of Quantum Mechanics.Vasil Penchev - 2020 - High Performance Computing eJournal 12 (11):1-8.
    Two strategies to infinity are equally relevant for it is as universal and thus complete as open and thus incomplete. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, thеse phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  11. Integrated Information Theory as a Conplexity Science Approach to Consciousness.L. H. Favela - 2019 - Journal of Consciousness Studies 26 (1-2):21-47.
    I claim that the integrated information theory of consciousness is a complexity science approach to consciousness. In general, complexity science investigates phenomena comprised of numerous non-linearly interacting parts, where global-scale behaviour and structures are irreducible to activities and properties of its constituent parts at local scales. I draw attention to some key features of IIT and complexity science in order to defend the claim that IIT is properly understood within the broader theoretical framework of complexity science. Doing so has the (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  12. Proof Compression and NP Versus PSPACE.L. Gordeev & E. H. Haeusler - 2019 - Studia Logica 107 (1):53-83.
    We show that arbitrary tautologies of Johansson’s minimal propositional logic are provable by “small” polynomial-size dag-like natural deductions in Prawitz’s system for minimal propositional logic. These “small” deductions arise from standard “large” tree-like inputs by horizontal dag-like compression that is obtained by merging distinct nodes labeled with identical formulas occurring in horizontal sections of deductions involved. The underlying geometric idea: if the height, h(∂), and the total number of distinct formulas, ϕ(∂), of a given tree-like deduction ∂ of a minimal (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13. Quantum Computing.Amit Hagar & Michael Cuffaro - 2019 - Stanford Encyclopedia of Philosophy.
    Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   4 citations  
  14. Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer.Michael Cuffaro - 2018 - In Sven Hansson (ed.), Technology and Mathematics: Philosophical and Historical Investigations. Springer. pp. 253-282.
    Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  15. Rational Analysis, Intractability, and the Prospects of ‘as If’-Explanations.Iris van Rooij, Cory Wright, Johan Kwisthout & Todd Wareham - 2018 - Synthese 195 (2):491-510.
    Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  16. On the Significance of the Gottesman–Knill Theorem.Michael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.
    According to the Gottesman–Knill theorem, quantum algorithms that utilize only the operations belonging to a certain restricted set are efficiently simulable classically. Since some of the operations in this set generate entangled states, it is commonly concluded that entanglement is insufficient to enable quantum computers to outperform classical computers. I argue in this article that this conclusion is misleading. First, the statement of the theorem is, on reflection, already evident when we consider Bell’s and related inequalities in the context of (...)
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  17. Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
    Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP ≠ coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  18. Human-Human Stigmergy.Ted Lewis & Leslie Marsh - 2016 - Cognitive Systems Research 38 (June):1-60.
  19. 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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  20. The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought.Christopher Mole - 2016 - Routledge.
    The relationship between intelligent systems and their environment is at the forefront of research in cognitive science. The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought shows how computational complexity theory and analytic metaphysics can together illuminate long-standing questions about the importance of that relationship. It argues that the most basic facts about a mind cannot just be facts about mental states, but must include facts about the dynamic, interactive mental occurrences that take place when a creature encounters (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  21. Solomonoff Prediction and Occam’s Razor.Tom F. Sterkenburg - 2016 - Philosophy of Science 83 (4):459-479.
    Algorithmic information theory gives an idealized notion of compressibility that is often presented as an objective measure of simplicity. It is suggested at times that Solomonoff prediction, or algorithmic information theory in a predictive setting, can deliver an argument to justify Occam’s razor. This article explicates the relevant argument and, by converting it into a Bayesian framework, reveals why it has no such justificatory force. The supposed simplicity concept is better perceived as a specific inductive assumption, the assumption of effectiveness. (...)
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  22. Quantifiers and Cognition: Logical and Computational Perspectives.Jakub Szymanik - 2016 - Springer.
    This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying the possible meanings and the inferential power of quantifier (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  23. How-Possibly Explanations in (Quantum) Computer Science.Michael E. Cuffaro - 2015 - Philosophy of Science 82 (5):737-748.
    A primary goal of quantum computer science is to find an explanation for the fact that quantum computers are more powerful than classical computers. In this paper I argue that to answer this question is to compare algorithmic processes of various kinds and to describe the possibility spaces associated with these processes. By doing this, we explain how it is possible for one process to outperform its rival. Further, in this and similar examples little is gained in subsequently asking a (...)
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  24. Visions de la complexité. Le démon de Laplace dans tous ses états.Guillaume Deffuant, Arnaud Banos, David Chavalarias, Cyrille Bertelle, Nicolas Brodu, Annick Lesne, Jean-Pierre Müller, Édith Perrier, Franck Varenne & Pablo Jensen - 2015 - Natures Sciences Sociétés 23 (1):42-53.
    Nous distinguons trois visions de la complexité afin de clarifier les contours de la recherche dans ce domaine. Nous utilisons le démon de Laplace comme référence pour présenter ces visions. La vision 1 brise le rêve du démon de Laplace en identifiant des systèmes particuliers qui lui résistent en mathématiques, physique et informatique. La vision 2 propose une nouvelle version du rêve de Laplace fondée sur la disponibilité récente de grandes quantités de données et de nouvelles technologies de programmation, de (...)
    Remove from this list   Direct download (4 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  25. Counting Steps: A Finitist Interpretation of Objective Probability in Physics.Amit Hagar & Giuseppe Sergioli - 2015 - Epistemologia 37 (2):262-275.
    We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the 'distance' (in terms of physical resources) from a physical state to another, and (3) the size of the set of time--complexity functions that are compatible with the physical (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26. Отвъд машината на Тюринг: квантовият компютър.Vasil Penchev - 2014 - Sofia: BAS: ISSK (IPS).
    Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum computer might (...)
    Remove from this list   Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  27. Why Philosophers Should Care About Computational Complexity.Scott Aaronson - 2013 - Computability: Turing, Gödel, Church, and Beyond:261--328.
    One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the resources needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction and Goodman's (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  28. The Semimeasure Property of Algorithmic Probability -- “Feature‘ or “Bug‘?Douglas Campbell - 2013 - In David L. Dowe (ed.), Algorithmic Probability and Friends: Bayesian Prediction and Artificial Intelligence. Springer Berlin Heidelberg. pp. 79--90.
    An unknown process is generating a sequence of symbols, drawn from an alphabet, A. Given an initial segment of the sequence, how can one predict the next symbol? Ray Solomonoff’s theory of inductive reasoning rests on the idea that a useful estimate of a sequence’s true probability of being outputted by the unknown process is provided by its algorithmic probability (its probability of being outputted by a species of probabilistic Turing machine). However algorithmic probability is a “semimeasure”: i.e., the sum, (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29. Remarks on Computational Complexity: Response to Abels.Norbert Hornstein - 2013 - Mind and Language 28 (4):430-434.
  30. Computational Complexity Reduction and Interpretability Improvement of Distance-Based Decision Trees.Marcin Blachnik & Mirosław Kordos - 2012 - In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. pp. 288--297.
  31. Complexity of Judgment Aggregation.Ulle Endriss, Umberto Grandi & Daniele Porello - 2012 - Journal of Artificial Intelligence Research 45:481--514.
    We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  32. Semantic Bounds for Everyday Language.Marcin Mostowski & Jakub Szymanik - 2012 - Semiotica 2012 (188):363-372.
    We consider the notion of everyday language. We claim that everyday language is semantically bounded by the properties expressible in the existential fragment of second–order logic. Two arguments for this thesis are formulated. Firstly, we show that so–called Barwise's test of negation normality works properly only when assuming our main thesis. Secondly, we discuss the argument from practical computability for finite universes. Everyday language sentences are directly or indirectly verifiable. We show that in both cases they are bounded by second–order (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  33. Intractability and the Use of Heuristics in Psychological Explanations.Iris Rooij, Cory Wright & Todd Wareham - 2012 - Synthese 187 (2):471-487.
  34. The Complexity of Industrial Ecosystems: Classification and Computational Modelling.James S. Baldwin - 2011 - In Peter Allen, Steve Maguire & Bill McKelvey (eds.), The Sage Handbook of Complexity and Management. Sage Publications. pp. 299.
  35. On theTractability of Comparing Informational Structures.Cédric Dégremont, Lena Kurzen & Jakub Szymanik - 2011 - In J. van Eijck & R. Verbrugge (eds.), Proceedings of the Workshop 'Reasoning about other minds: Logical and cognitive perspectives.
  36. Characterizing Definability of Second-Order Generalized Quantifiers.Juha Kontinen & Jakub Szymanik - 2011 - In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
    We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\star}_2$. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the monadic second-order majority quantifier $\most^1$ is not definable (...)
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  37. Thoughts on Complexity and Computational Models.Michael J. Prietula - 2011 - In Peter Allen, Steve Maguire & Bill McKelvey (eds.), The Sage Handbook of Complexity and Management. Sage Publications. pp. 93--110.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  38. Contribution of Working Memory in the Parity and Proportional Judgments.Jakub Szymanik & Marcin Zajenkowski - 2011 - Belgian Journal of Linguistics 25:189-206.
    The paper presents an experimental evidence on differences in the sentence-picture verification under additional memory load between parity and proportional quantifiers. We asked subjects to memorize strings of 4 or 6 digits, then to decide whether a quantifier sentence is true at a given picture, and finally to recall the initially given string of numbers. The results show that: (a) proportional quantifiers are more difficult than parity quantifiers with respect to reaction time and accuracy; (b) maintaining either 4 or 6 (...)
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   5 citations  
  39. A Computational Approach to Quantifiers as an Explanation for Some Language Impairments in Schizophrenia.Marcin Zajenkowski, Rafał Styła & Jakub Szymanik - 2011 - Journal of Communication Disorder 44:2011.
    We compared the processing of natural language quantifiers in a group of patients with schizophrenia and a healthy control group. In both groups, the difficulty of the quantifiers was consistent with computational predictions, and patients with schizophrenia took more time to solve the problems. However, they were significantly less accurate only with proportional quantifiers, like more than half. This can be explained by noting that, according to the complexity perspective, only proportional quantifiers require working memory engagement.
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   4 citations  
  40. Sense and Proof.Carlo Penco & Daniele Porello - 2010 - In M. D'agostino, G. Giorello, F. Laudisa, T. Pievani & C. Sinigaglia (eds.), New Essays in Logic and Philosophy of Science,. College Publicationss.
    In this paper we give some formal examples of ideas developed by Penco in two papers on the tension inside Frege's notion of sense (see Penco 2003). The paper attempts to compose the tension between semantic and cognitive aspects of sense, through the idea of sense as proof or procedure – not as an alternative to the idea of sense as truth condition, but as complementary to it (as it happens sometimes in the old tradition of procedural semantics).
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41. 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 results to investigate semantic (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  42. Comprehension of Simple Quantifiers: Empirical Evaluation of a Computational Model.Jakub Szymanik & Marcin Zajenkowski - 2010 - Cognitive Science 34 (3):521-532.
    We examine the verification of simple quantifiers in natural language from a computational model perspective. We refer to previous neuropsychological investigations of the same problem and suggest extending their experimental setting. Moreover, we give some direct empirical evidence linking computational complexity predictions with cognitive reality.<br>In the empirical study we compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and push-down automata is psychologically relevant. Our research improves upon hypothesis and (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  43. Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
    The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, the [Formula: (...)
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  44. Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. [REVIEW]Peter Bosch, David Gabelaia & Jérôme Lang (eds.) - 2009 - Springer.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    Bookmark  
  45. Hybrid Elections Broaden Complexity‐Theoretic Resistance to Control.Edith Hemaspaandra, Lane A. Hemaspaandra & Jörg Rothe - 2009 - Mathematical Logic Quarterly 55 (4):397-424.
    Electoral control refers to attempts by an election's organizer to influence the outcome by adding/deleting/partitioning voters or candidates. The important paper of Bartholdi, Tovey, and Trick [1] that introduces control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible.We introduce and study a method of combining two or more candidate-anonymous election schemes in such a way that the combined scheme possesses all the resistances to (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  46. Ockham’s Razor and Reasoning About Information Flow.Mehrnoosh Sadrzadeh - 2009 - Synthese 167 (2):391 - 408.
    What is the minimal algebraic structure to reason about information flow? Do we really need the full power of Boolean algebras with co-closure and de Morgan dual operators? How much can we weaken and still be able to reason about multi-agent scenarios in a tidy compositional way? This paper provides some answers.
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  47. 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 in polynomial time. (...)
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   12 citations  
  48. 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.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    Bookmark  
  49. Understanding Quantifiers in Language.Jakub Szymanik & Marcin Zajenkowski - 2009 - In N. A. Taatgen & H. van Rijn (eds.), Proceedings of the 31st Annual Conference of the Cognitive Science Society.
    We compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and pushdown automata is psychologically relevant. Our research improves upon hypothesis and explanatory power of recent neuroimaging studies as well as provides evidence for the claim that human linguistic abilities are constrained by computational complexity.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    Bookmark  
  50. Improving Methodology of Quantifier Comprehension Experiments.Jakub Szymanik & Marcin Zajenkowski - 2009 - Neuropsychologia 47 (12):2682--2683.
    Szymanik (2007) suggested that the distinction between first-order and higher-order quantifiers does not coincide with the computational resources required to compute the meaning of quantifiers. Cognitive difficulty of quantifier processing might be better assessed on the basis of complexity of the minimal corresponding automata. For example, both logical and numerical quantifiers are first-order. However, computational devices recognizing logical quantifiers have a fixed number of states while the number of states in automata corresponding to numerical quantifiers grows with the rank of (...)
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   4 citations  
  51. Nothing in this category. Everyone can categorize entries. Please help if you have the expertise.