Closure properties and witness reduction

DOI10.1006/JCSS.1995.1032MaRDI QIDQ1894449zbMATH OpenOpenAlexFDO

Authors Sanjay Gupta

Publication date 29 April 1996

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/4dca91bc5d804785ad5df93ebe87778b4bbc0560

zbMATH Keywords

complexity theoryWitness reduction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A complexity theory for feasible closure properties
• scientific article; zbMATH DE number 770278
• Distinguishability operations and closures
• scientific article; zbMATH DE number 3902629
• Closedness properties in ex-identification
• Closure properties of constraints
• Compactification and Closure
• Closure properties associated to natural equivalences
• A dual to tight closure theory
• On the succinctness of closure operator representations

Cited in

(10)

• A note on unambiguous function classes
• Comparing action descriptions based on semantic preferences
• LWPP and WPP are not uniformly gap-definable
• Cluster computing and the power of edge recognition
• The consequences of eliminating NP solutions
• Closedness properties in ex-identification
• Weighted automata and logics meet computational complexity
• Logical characterizations of weighted complexity classes
• Descriptive complexity and weighted Turing machines
• On the autoreducibility of functions

This page was built for publication: Closure properties and witness reduction

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