This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories

101 found
Order:
1 — 50 / 101
  1. Why Philosophers Should Care About Computational Complexity.Scott Aaronson - unknown
    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  
     
    My bibliography  
  2. Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi - 2001 - Journal of Symbolic Logic 66 (1):171-191.
    We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by (...)
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  3. Diversity of Speed-Ups and Embeddability in Computational Complexity.Donald A. Alton - 1976 - Journal of Symbolic Logic 41 (1):199-214.
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  4. On Second-Order Generalized Quantifiers and Finite Structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
    We consider the expressive power of second - order generalized quantifiers on finite structures, especially with respect to the types of the quantifiers. We show that on finite structures with at most binary relations, there are very powerful second - order generalized quantifiers, even of the simplest possible type. More precisely, if a logic is countable and satisfies some weak closure conditions, then there is a generalized second - order quantifier which is monadic, unary and simple, and a uniformly obtained (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  5. Eliminating Definitions and Skolem Functions in First-Order Logic.Jeremy Avigad - manuscript
    From proofs in any classical first-order theory that proves the existence of at least two elements, one can eliminate definitions in polynomial time. From proofs in any classical first-order theory strong enough to code finite functions, including sequential theories, one can also eliminate Skolem functions in polynomial time.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  6. 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.
  7. 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.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  8. 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.
  9. Remarks on Gregory's “Actually” Operator.Patrick Blackburn & Maarten Marx - 2002 - Journal of Philosophical Logic 31 (3):281-288.
    In this note we show that the classical modal technology of Sahlqvist formulas gives quick proofs of the completeness theorems in [8] (D. Gregory, Completeness and decidability results for some propositional modal logics containing "actually" operators, Journal of Philosophical Logic 30(1): 57-78, 2001) and vastly generalizes them. Moreover, as a corollary, interpolation theorems for the logics considered in [8] are obtained. We then compare Gregory's modal language enriched with an "actually" operator with the work of Arthur Prior now known under (...)
    Remove from this list   Direct download (9 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  10. A Modal Perspective on the Computational Complexity of Attribute Value Grammar.Patrick Blackburn & Edith Spaan - 1993 - Journal of Logic, Language and Information 2 (2):129-169.
    Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two main (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  11. Henkin Quantifiers and Complete Problems.A. Blass & Y. Gurevich - 1986 - Annals of Pure and Applied Logic 32 (1):1--16.
  12. 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  
     
    My bibliography  
  13. Computational Complexity of Solving Equation Systems.Przemysław Broniek - unknown
    We present conclusions and open problems raising from studying solving equations over unary algebras. We suggest areas that are most promising for expanding our knowledge.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  14. Lindström Quantifiers and Leaf Language Definability.Hans J. Burtschick & Heribert Vollmer - 1998 - International Journal of Foundations of Computer Science 9 (3):277--294.
  15. 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: Papers From the Ray Solomonoff 85th Memorial Conference, Melbourne, Vic, Australia, November 30 -- December 2, 2011. 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  
     
    My bibliography  
  16. Quantified Propositional Logic and the Number of Lines of Tree-Like Proofs.Alessandra Carbone - 2000 - Studia Logica 64 (3):315-321.
    There is an exponential speed-up in the number of lines of the quantified propositional sequent calculus over Substitution Frege Systems, if one considers proofs as trees. Whether this is true also for the number of symbols, is still an open problem.
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    My bibliography  
  17. Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
    We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  18. Computation Models for Parameterized Complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  19. Computational Complexity and Godel's Incompleteness Theorem.Gregory J. Chaitin - 1970 - [Rio De Janeiro, Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
    Remove from this list  
     
    Export citation  
     
    My bibliography   2 citations  
  20. Computational Complexity and the Universal Acceptance of Logic.Christopher Cherniak - 1984 - Journal of Philosophy 81 (12):739-758.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  21. On the Complexity of Finding Paths in a Two‐Dimensional Domain I: Shortest Paths.Arthur W. Chou & Ker‐I. Ko - 2004 - Mathematical Logic Quarterly 50 (6):551-572.
    The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: domains with polynomialtime computable boundaries, and polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type and type ; and it has a polynomial-space lower (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  22. Quantified Propositional Calculus and a Second-Order Theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  23. 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 (9 more)  
     
    Export citation  
     
    My bibliography  
  24. 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 (6 more)  
     
    Export citation  
     
    My bibliography  
  25. 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.
  26. A Completeness Proof for a Logic with an Alternative Necessity Operator.Stéphane Demri - 1997 - Studia Logica 58 (1):99-112.
    We show the completeness of a Hilbert-style system LK defined by M. Valiev involving the knowledge operator K dedicated to the reasoning with incomplete information. The completeness proof uses a variant of Makinson's canonical model construction. Furthermore we prove that the theoremhood problem for LK is co-NP-complete, using techniques similar to those used to prove that the satisfiability problem for propositional S5 is NP-complete.
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  27. Combinatorial Problems in Natural Sciences: Computational Complexity and Inherent Properties.Bruno Apolloni-Salvatore Di Gregorio - 1984 - Epistemologia 7:115-136.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  28. 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  
     
    My bibliography  
  29. Reducing Negative Complexity by a Computational Semiotic System.Gerd Doben-Henisch - 2007 - In R. Gudwin & J. Queiroz (eds.), Semiotics and Intelligent Systems Development. Idea Group. pp. 330.
  30. Computational Complexity of Stochastic Programming Problems.Martin Dyer & Leen Stougie - 2005 - Complexity 1 (13):21.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  31. Complexity of Judgment Aggregation.Ulle Endriss, Umberto Grandi & Daniele Porello - 2012 - Journal of Artificial Intelligence Research 45:481--514.
  32. The Computational Complexity of Logical Theories.Jeanne Ferrante - 1979 - Springer Verlag.
    This book asks not only how the study of white-collar crime can enrich our understanding of crime and justice more generally, but also how criminological ...
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography   11 citations  
  33. Lecture Notes on Term Rewriting and Computational Complexity.Harvey Friedman - manuscript
    The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  34. Some Decision Problems of Enormous Complexity.Harvey Friedman - manuscript
    We present some new decision and comparison problems of unusually high computational complexity. Most of the problems are strictly combinatorial in nature; others involve basic logical notions. Their complexities range from iterated exponential time completeness to (0 time completeness to ((((,0) time completeness to ((((,,0) time completeness. These three ordinals are well known ordinals from proof theory, and their associated com- plexity classes represent new levels of computational complexity for natural decision problems. Proofs will appear in an extended version of (...)
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  35. Implementation of Belief Change Operators Using BDDs.Nikos Gorogiannis & Mark D. Ryan - 2002 - Studia Logica 70 (1):131 - 156.
    While the theory of belief change has attracted a lot of interest from researchers, work on implementing belief change and actually putting it to use in real-world problems is still scarce. In this paper, we present an implementation of propositional belief change using Binary Decision Diagrams. Upper complexity bounds for the algorithm are presented and discussed. The approach is presented both in the general case, as well as on specific belief change operators from the literature. In an effort to gain (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  36. On the Decision Problem for Two-Variable First-Order Logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
    We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...)
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    My bibliography   15 citations  
  37. Quantum Computing.Amit Hagar & Michael Cuffaro - 2015 - Stanford Encyclopedia of Philosophy.
    Combining physics, mathematics and computer science, quantum computing has developed in the past two decades from a visionary idea to one of the most fascinating areas of quantum mechanics. The recent excitement in this lively and speculative domain of research was triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially "speed up" classical computation and factor large numbers into primes much more rapidly (at least in terms of the number of computational steps involved) than any known (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  38. Quantum Hypercomputation—Hype or Computation?Amit Hagar & Alex Korolev - 2007 - Philosophy of Science 74 (3):347-363.
    A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  39. Quantum Hypercomputability?Amit Hagar & Alexandre Korolev - 2006 - Minds and Machines 16 (1):87-93.
    A recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.
    Remove from this list   Direct download (13 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  40. 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  41. Computational Limitations of Small-Depth Circuits.Johan Håstad - 1987
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   3 citations  
  42. Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
    We consider the problem of finding a characterization for polynomial time computable queries on finite structures in terms of logical definability. It is well known that fixpoint logic provides such a characterization in the presence of a built-in linear order, but without linear order even very simple polynomial time queries involving counting are not expressible in fixpoint logic. Our approach to the problem is based on generalized quantifiers. A generalized quantifier isn-ary if it binds any number of formulas, but at (...)
    Remove from this list  
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography   6 citations  
  43. 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  
     
    My bibliography  
  44. Reducing Negative Complexity by a Computational Semiotic System.Gerd Döben Henisch - 2007 - In R. Gudwin & J. Queiroz (eds.), Semiotics and Intelligent Systems Development. Idea Group.
  45. Remarks on Computational Complexity: Response to Abels.Norbert Hornstein - 2013 - Mind and Language 28 (4):430-434.
  46. Connection Tableau Calculi with Disjunctive Constraints.Ortrun Ibens - 2002 - Studia Logica 70 (2):241 - 270.
    Automated theorem proving amounts to solving search problems in usually tremendous search spaces. A lot of research therefore focuses on search space reductions. Our approach reduces the search space which arises when using so-called connection tableau calculi for first-order automated theorem proving. It uses disjunctive constraints over first-order equations to compress certain parts of this search space. We present the basics of our constrained-connection-tableau calculi, a constraint extension of connection tableau calculi, and deal with the efficient handling of constraints during (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  47. Delineating Classes of Computational Complexity Via Second Order Theories with Weak Set Existence Principles. I.Aleksandar Ignjatović - 1995 - Journal of Symbolic Logic 60 (1):103-121.
    Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).
    Remove from this list   Direct download (12 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  48. Descriptive Complexity.N. Immerman - 1999 - Springer Verlag.
    This book is a relatively self-contained introduction to the subject, which includes the necessary background material, as well as numerous examples and exercises.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography   9 citations  
  49. On Generalized Computational Complexity.Barry E. Jacobs - 1977 - Journal of Symbolic Logic 42 (1):47-58.
  50. Definability of Second Order Generalized Quantifiers.Juha Kontinen - 2004 - Dissertation,
    We study second order generalized quantifiers on finite structures. One starting point of this research has been the notion of definability of Lindström quantifiers. We formulate an analogous notion for second order generalized quantifiers and study definability of second order generalized quantifiers in terms of Lindström quantifiers.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
1 — 50 / 101