Pages that link to "Item:Q917543"

The following pages link to A uniform method for proving lower bounds on the computational complexity of logical theories (Q917543):

Displaying 31 items.

• Model-checking hierarchical structures (Q414908) (← links)
• Practical algorithms for MSO model-checking on tree-decomposable graphs (Q473216) (← links)
• The most nonelementary theory (Q598194) (← links)
• Algorithmic uses of the Feferman-Vaught theorem (Q598280) (← links)
• Exact complexity bounds for ordinal addition (Q671516) (← links)
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness (Q673091) (← links)
• Simple sentences that are hard to decide (Q810009) (← links)
• Computational complexity of logical theories of one successor and another unary function (Q868664) (← links)
• Simple interpretations among complicated theories (Q923068) (← links)
• Nonconvergence, undecidability, and intractability in asymptotic problems (Q1095135) (← links)
• Dominoes and the complexity of subclasses of logical theories (Q1115859) (← links)
• Non-elementary lower bound for Propositional Duration Calculus (Q1129106) (← links)
• Complexity of logical theories involving coprimality (Q1202924) (← links)
• Algebras for querying text regions: Expressive power and optimization (Q1278037) (← links)
• Succinctness as a source of complexity in logical formalisms (Q1302307) (← links)
• Ehrenfeucht games and ordinal addition (Q1377635) (← links)
• Sorting, linear time and the satisfiability problem (Q1817067) (← links)
• On iterating linear transformations over recognizable sets of integers (Q1884908) (← links)
• Hyperfinite MV-algebras (Q2376570) (← links)
• Non-primitive recursive decidability of products of modal logics with expanding domains (Q2503403) (← links)
• Inverse monoids: decidability and complexity of algebraic questions. (Q2643082) (← links)
• COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA (Q3056281) (← links)
• Double-exponential inseparability of Robinson subsystem <i>Q</i>₊ (Q3083130) (← links)
• Automatic structures of bounded degree revisited (Q3107359) (← links)
• Automatic Structures of Bounded Degree Revisited (Q3644760) (← links)
• Model Checking FO(R) over One-Counter Processes and beyond (Q3644768) (← links)
• Probabilities of Sentences about Very Sparse Random Graphs (Q3989740) (← links)
• The theory of integer multiplication with order restricted to primes is decidable (Q4338318) (← links)
• Fifty years of the spectrum problem: survey and new results (Q4902770) (← links)
• Canonical Models and the Complexity of Modal Team Logic (Q5079755) (← links)
• First-order and counting theories of<i>ω</i>-automatic structures (Q5387304) (← links)