The Boolean hierarchy of NP-partitions (extended abstract)

DOI10.1007/3-540-46541-3_13MaRDI QIDQ4501530zbMATH OpenFDO

Authors Sven Kosub, K. W. Wagner

Publication date 3 May 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46541-3_13

zbMATH Keywords

Boolean hierarchy

Mathematics Subject Classification ID

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

Recommendations

• The Boolean hierarchy of NP-partitions
• NP-partitions over posets with an application to reducing the set of solutions of NP problems
• scientific article; zbMATH DE number 1759433
• The Boolean Hierarchy I: Structural Properties
• scientific article; zbMATH DE number 3988706

Cited in

(27)

• Definability in the \(h\)-quasiorder of labeled forests
• On the Wadge reducibility of \(k\)-partitions
• A comment on \('NP=P?'\) and restricted partitions
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Reducing the number of solutions of NP functions
• NP-partitions over posets with an application to reducing the set of solutions of NP problems
• Labeled posets are universal
• Complexity issues for preorders on finite labeled forests
• A Fine Hierarchy of ω-Regular k-Partitions
• Theories of orders on the set of words
• Partitioning 1-variable Boolean functions for various classification ofn-variable Boolean functions
• scientific article; zbMATH DE number 3988706 (Why is no real title available?)
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Fine hierarchies via Priestley duality
• scientific article; zbMATH DE number 2040953 (Why is no real title available?)
• scientific article; zbMATH DE number 1759433 (Why is no real title available?)
• scientific article; zbMATH DE number 2154085 (Why is no real title available?)
• On the difference hierarchy in countably based \(T_{0}\)-spaces
• On the Wadge reducibility of \(k\)-partitions
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• On the homomorphism order of labeled posets
• Clonoids of Boolean functions with a monotone or discriminator source clone
• Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms
• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• The Boolean hierarchy of NP-partitions
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: The Boolean hierarchy of NP-partitions (extended abstract)

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