This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories
Siblings:
84 found
Search inside:
(import / add options)   Order:
1 — 50 / 84
  1. Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi (2001). Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. 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 (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  2. Donald A. Alton (1976). Diversity of Speed-Ups and Embeddability in Computational Complexity. Journal of Symbolic Logic 41 (1):199-214.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  3. Anders Andersson (2002). On Second-Order Generalized Quantifiers and Finite Structures. 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 (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  4. Jeremy Avigad, Eliminating Definitions and Skolem Functions in First-Order Logic.
    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  
  5. Arnold Beckmann & Samuel R. Buss (2009). Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic. Journal of Mathematical Logic 9 (1):103-138.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  6. Patrick Blackburn & Maarten Marx (2002). Remarks on Gregory's “Actually” Operator. 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  
  7. Patrick Blackburn & Edith Spaan (1993). A Modal Perspective on the Computational Complexity of Attribute Value Grammar. Journal of Logic, Language and Information 2 (2):129-169.
    Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two main (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  8. A. Blass & Y. Gurevich (1986). Henkin Quantifiers and Complete Problems. Annals of Pure and Applied Logic 32 (1):1--16.
  9. Peter Bosch, David Gabelaia & Jérôme Lang (eds.) (2009). Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. [REVIEW] Springer.
    Remove from this list  
    Translate
     
     
    Export citation  
     
    My bibliography  
  10. Hans J. Burtschick & Heribert Vollmer (1998). Lindström Quantifiers and Leaf Language Definability. International Journal of Foundations of Computer Science 9 (3):277--294.
  11. Alessandra Carbone (2000). Quantified Propositional Logic and the Number of Lines of Tree-Like Proofs. 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  
  12. Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  13. Marco Cesati & Miriam Dilanni (1997). Computation Models for Parameterized Complexity. Mathematical Logic Quarterly 43 (2):179-202.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  14. 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.
    Remove from this list  
     
    Export citation  
     
    My bibliography   2 citations  
  15. Christopher Cherniak (1984). Computational Complexity and the Universal Acceptance of Logic. Journal of Philosophy 81 (12):739-758.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  16. Stephen Cook & Tsuyoshi Morioka (2005). Quantified Propositional Calculus and a Second-Order Theory for NC1. Archive for Mathematical Logic 44 (6):711-749.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  17. Michael E. Cuffaro (forthcoming). On the Significance of the Gottesman-Knill Theorem. British Journal for the Philosophy of Science:axv016.
    According to the Gottesman-Knill theorem, quantum algorithms which utilise 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 paper that this conclusion is misleading. First, the statement of the theorem (that the particular set of quantum operations in question can be simulated using a classical computer) (...)
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    My bibliography  
  18. Michael E. Cuffaro (2015). How-Possibly Explanations in Computer Science. 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  
  19. Cédric Dégremont, Lena Kurzen & Jakub Szymanik (2011). On theTractability of Comparing Informational Structures. In J. van Eijck & R. Verbrugge (eds.), Proceedings of the Workshop 'Reasoning about other minds: Logical and cognitive perspectives.
  20. Stéphane Demri (1997). A Completeness Proof for a Logic with an Alternative Necessity Operator. 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  
  21. Farzad Didehvar, A Contradiction and P=NP Problem.
    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  
  22. Martin Dyer & Leen Stougie (2005). Computational Complexity of Stochastic Programming Problems. Complexity 1 (13):21.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  23. Ulle Endriss, Umberto Grandi & Daniele Porello (2012). Complexity of Judgment Aggregation. Journal of Artificial Intelligence Research 45:481--514.
  24. Jeanne Ferrante (1979). The Computational Complexity of Logical Theories. Springer-Verlag.
    This book asks not only how the study of white-collar crime can enrich our understanding of crime and justice more generally, but also how criminological ...
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography   11 citations  
  25. Harvey Friedman, Lecture Notes on Term Rewriting and Computational Complexity.
    The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  26. Nikos Gorogiannis & Mark D. Ryan (2002). Implementation of Belief Change Operators Using BDDs. 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 (5 more)  
     
    Export citation  
     
    My bibliography  
  27. Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. 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 (6 more)  
     
    Export citation  
     
    My bibliography   10 citations  
  28. Amit Hagar & Michael Cuffaro, Quantum Computing. 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  
  29. Amit Hagar & Alex Korolev (2007). Quantum Hypercomputation—Hype or Computation? 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   1 citation  
  30. Amit Hagar & Alexandre Korolev (2006). Quantum Hypercomputability? 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  
  31. Amit Hagar & Giuseppe Sergioli (2015). Counting Steps: A Finitist Interpretation of Objective Probability in Physics. 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  
  32. Johan Håstad (1987). Computational Limitations of Small-Depth Circuits. Monograph Collection (Matt - Pseudo).
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   3 citations  
  33. Lauri Hella (1996). Logical Hierarchies in PTIME. 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  
  34. Norbert Hornstein (2013). Remarks on Computational Complexity: Response to Abels. Mind and Language 28 (4):430-434.
  35. Ortrun Ibens (2002). Connection Tableau Calculi with Disjunctive Constraints. 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 (4 more)  
     
    Export citation  
     
    My bibliography  
  36. Aleksandar Ignjatović (1995). Delineating Classes of Computational Complexity Via Second Order Theories with Weak Set Existence Principles. I. Journal of Symbolic Logic 60 (1):103-121.
    Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  37. N. Immerman (1999). Descriptive Complexity. 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  
  38. Barry E. Jacobs (1977). On Generalized Computational Complexity. Journal of Symbolic Logic 42 (1):47-58.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  39. Juha Kontinen (2004). Definability of Second Order Generalized Quantifiers. 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  
  40. Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. 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  
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  41. Juha Kontinen & Jakub Szymanik (2008). A Remark on Collective Quantification. Journal of Logic, Language and Information 17 (2):131-140.
    We consider collective quantification in natural language. For many years the common strategy in formalizing collective quantification has been to define the meanings of collective determiners, quantifying over collections, using certain type-shifting operations. These type-shifting operations, i.e., lifts, define the collective interpretations of determiners systematically from the standard meanings of quantifiers. All the lifts considered in the literature turn out to be definable in second-order logic. We argue that second-order definable quantifiers are probably not expressive enough to formalize all collective (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  42. Jan Krajíček & Pavel Pudlák (1989). Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations. Journal of Symbolic Logic 54 (3):1063-1079.
    We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in S whose length is ≤ n. We show the relation of this problem to some problems about propositional proof systems.
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  43. Theodor Leiber (1999). Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW] Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
    Some problems rarely discussed in traditional philosophy of science are mentioned: The empirical sciences using mathematico-quantitative theoretical models are frequently confronted with several types of computational problems posing primarily methodological limitations on explanatory and prognostic matters. Such limitations may arise from the appearances of deterministic chaos and high computational complexity in general. In many cases, however, scientists circumvent such limitations by utilizing reductional approximations or complexity reductions for intractable problem formulations, thus constructing new models which are computationally tractable. (...)
    Remove from this list   Direct download (10 more)  
     
    Export citation  
     
    My bibliography  
  44. Ted Lewis & Leslie Marsh (2016). Human-Human Stigmergy. Cognitive Systems Research 38 (June):1-60.
  45. McGraw-Hill, Computational Complexity and Godel's Incompleteness Theorem.
    Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n < L(F ). On the other hand, almost all finite binary sequences S satisfy L(S) > L(F ). The proof resembles Berry’s..
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  46. Albert R. Meyer & Patrick C. Fischer (1972). Computational Speed-Up by Effective Operators. Journal of Symbolic Logic 37 (1):55-68.
  47. Pascal Michel (2007). Computational Complexity of Logical Theories of One Successor and Another Unary Function. Archive for Mathematical Logic 46 (2):123-148.
    The first-order logical theory Th $({\mathbb{N}},x + 1,F(x))$ is proved to be complete for the class ATIME-ALT $(2^{O(n)},O(n))$ when $F(x) = 2^{x}$ , and the same result holds for $F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)$ , and F(x) = tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  48. Christopher Mole (2016). The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought. 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  
     
    My bibliography  
  49. Adam Morton (2004). Epistemic Virtues, Metavirtues, and Computational Complexity. Noûs 38 (3):481–502.
    I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.
    Remove from this list   Direct download (10 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  50. Professor Adam Morton (2004). Epistemic Virtues, Metavirtues, and Computational Complexity. Noûs 38 (3):481-502.
    I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    My bibliography   1 citation  
1 — 50 / 84