Some Remarks on Generalized Spectra

DOI10.1002/MALQ.19770233608MaRDI QIDQ4182723zbMATH OpenOpenAlexFDO

Authors Peter Gács, László Lovász

Publication date 1977

Published in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19770233608

zbMATH Keywords

Computational ComplexityGeneralized SpectraNp-Complete

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Cited in

(12)

• A restricted second order logic for finite structures
• Succinct representation, leaf languages, and projection reductions
• Capturing MSO with one quantifier
• Many Facets of Dualities
• Parameterized Complexity Classes under Logical Reductions
• Universal quantifiers and time complexity of random access machines
• On completeness for NP via projection translations
• Fifty years of the spectrum problem: survey and new results
• On spectra of sentences of monadic second order logic with counting
• A restricted second order logic for finite structures
• Methods for proving completeness via logical reductions
• NP-completeness by first-order and quantifier-free interpretations and related topics

This page was built for publication: Some Remarks on Generalized Spectra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4182723)