Pages that link to "Item:Q4154070"

The following pages link to Rudimentary Predicates and Relative Computation (Q4154070):

Displaying 37 items.

• Extensions of MSO and the monadic counting hierarchy (Q617710) (← links)
• Observations on complete sets between linear time and polynomial time (Q627129) (← links)
• On quasilinear-time complexity theory (Q672330) (← links)
• Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem (Q731897) (← links)
• Representations of language families by homomorphic equality operations and generalized equality sets (Q1099633) (← links)
• Alternating real-time computations (Q1111386) (← links)
• Rudimentary relations and primitive recursion: A toolbox (Q1127532) (← links)
• Complexity of Boolean algebras (Q1137036) (← links)
• Bounded query machines: on NP and PSPACE (Q1158751) (← links)
• Bounded query machines: on NP( ) and NPQUERY( ) (Q1158752) (← links)
• Rudimentary reductions revisited (Q1183444) (← links)
• On languages specified by relative acceptance (Q1249438) (← links)
• Bounded arithmetic, proof complexity and two papers of Parikh (Q1295443) (← links)
• Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) (Q1392020) (← links)
• A descriptive complexity approach to the linear hierarchy. (Q1401413) (← links)
• Time-space tradeoffs for satisfiability (Q1567402) (← links)
• Nonerasing, counting, and majority over the linear time hierarchy (Q1854524) (← links)
• Arithmetical definability and computational complexity (Q1885035) (← links)
• \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\) (Q1899142) (← links)
• The minimum oracle circuit size problem (Q2410683) (← links)
• A generalization of the second incompleteness theorem and some exceptions to it (Q2500470) (← links)
• Self-verifying axiom systems, the incompleteness theorem and related reflection principles (Q2747704) (← links)
• END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS (Q2976370) (← links)
• Bounded minimalisation and bounded counting in argument-bounded idc's (Q3060189) (← links)
• The role of rudimentary relations in complexity theory (Q3347299) (← links)
• On the available partial respects in which an axiomatization for real valued arithmetic can recognize its consistency (Q3416110) (← links)
• European Summer Meeting of the Association for Symbolic Logic, (Logic Colloquium '87), Granada, Spain, 1987 (Q3476783) (← links)
• A Characterisation of the Relations Definable in Presburger Arithmetic (Q3502652) (← links)
• Logical Closure Properties of Propositional Proof Systems (Q3502657) (← links)
• Extensional Uniformity for Boolean Circuits (Q3540171) (← links)
• On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
• Characterizations of reduction classes modulo oracle conditions (Q3763590) (← links)
• How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q (Q4532626) (← links)
• A theory for Log-Space and NLIN versus co-NLIN (Q4650271) (← links)
• Fifty years of the spectrum problem: survey and new results (Q4902770) (← links)
• Regular Graphs and the Spectra of Two-Variable Logic with Counting (Q5258916) (← links)
• An exploration of the partial respects in which an axiom system recognizing solely addition as a total function can verify its own consistency (Q5486248) (← links)