scientific article
From MaRDI portal
Publication:3220555
zbMath0556.03012MaRDI QIDQ3220555
Publication date: 1984
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Boolean functionspectrum problemdegree complexityfinite satisfiabilityquantifier complexityregister machinesnetwork complexityreduction classesHorn complexitydecision problems for sets of prenex formulasfirst order spectralogical description of machine computationstime bounded Turing machine
Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items
Why Horn formulas matter in computer science: initial structures and generic examples, Subclasses of Presburger arithmetic and the polynomial-time hierarchy, Dominoes and the complexity of subclasses of logical theories, Descriptive characterizations of computational complexity, A uniform method for proving lower bounds on the computational complexity of logical theories, Simple sentences that are hard to decide
