scientific article; zbMATH DE number 4170888
From MaRDI portal
Publication:3496328
classification of prefix vocabulary classes in first order logicdecidabilityformulas with a model of bounded sizeNTIME-lower boundsPresburger arithmeticreductions from bounded domino problemsTrakhtenbrot's Inseparability Theoremundecidability
Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Recommendations
- scientific article; zbMATH DE number 4116512
- Dominoes and the complexity of subclasses of logical theories
- The quantifier structure of sentences that characterize nondeterministic time complexity
- A Natural NP-Complete Problem with a Nontrivial Lower Bound
- Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
Cited in
(4)- Halting time is predictable for large models: a universality property and average-case analysis
- Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
- scientific article; zbMATH DE number 517074 (Why is no real title available?)
- A model of \(\widehat{R}^2_3\) inside a subexponential time resource
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3496328)
