On bijections vs. unary functions

DOI10.1007/3-540-60922-9_34MaRDI QIDQ4593949zbMATH OpenOpenAlexFDO

Authors Thomas Schwentick

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_34

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Subclasses of binary NP
• The expressive power of bijections over weakly arithmetized structures
• On monadic NP vs monadic co-NP
• One unary function says less than two in existential second order logic
• First-order spectra with one variable

Cited in

(3)

• Linear time and the power of one first-order universal quantifier
• The expressive power of bijections over weakly arithmetized structures
• Subclasses of binary NP

This page was built for publication: On bijections vs. unary functions

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