Some Remarks on Generalized Spectra

DOI10.1002/malq.19770233608zbMath0398.03025OpenAlexW2053534720MaRDI QIDQ4182723

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

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 ComplexityNp-CompleteGeneralized Spectra

Mathematics Subject Classification ID

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

Related Items

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