The boolean hierarchy of NP-partitions
S Kosub, KW Wagner - Annual Symposium on Theoretical Aspects of …, 2000 - Springer
… boolean hierarchy of k-partitions over NP for k ≥ 3 as a generalization of the boolean hierarchy
… Whereas the structure of the latter hierarchy is rather simple the structure of the boolean …
… Whereas the structure of the latter hierarchy is rather simple the structure of the boolean …
The boolean hierarchy of NP-partitions
S Kosub, KW Wagner - Information and Computation, 2008 - Elsevier
… boolean hierarchy of k-partitions over NP for k ≥ 3 as a generalization of the boolean hierarchy
… Whereas the structure of the latter hierarchy is rather simple the structure of the boolean …
… Whereas the structure of the latter hierarchy is rather simple the structure of the boolean …
Complexity and partitions
S Kosub - 2001 - opus.bibliothek.uni-wuerzburg.de
… , in shape of the boolean hierarchy of NP-partitions and its … Boolean hierarchy of NP-partitions
is introduced as a generalization of the well-known and well-studied Boolean hierarchy …
is introduced as a generalization of the well-known and well-studied Boolean hierarchy …
On NP-partitions over posets with an application to reducing the set of solutions of NP problems
S Kosub - … Symposium on Mathematical Foundations of Computer …, 2000 - Springer
… boolean hierarchy of sets. The classes of this hierarchy are exactly those classes of NP-partitions …
We refine the boolean hierarchy of NP-partitions by considering partition classes which …
We refine the boolean hierarchy of NP-partitions by considering partition classes which …
NP-partitions over posets with an application to reducing the set of solutions of NP problems
S Kosub - Theory of Computing Systems, 2005 - Springer
… -known boolean hierarchy of sets (2-partitions). The classes of this hierarchy are exactly those
classes of NP-partitions … We generalize the boolean hierarchy of NP-partitions by studying …
classes of NP-partitions … We generalize the boolean hierarchy of NP-partitions by studying …
Boolean NP-partitions and projective closure
S Kosub - International Conference on Discrete Mathematics and …, 2003 - Springer
… In this paper we investigate projective closures of classes of boolean NP-partitions, ie,
partitions with components that have complexity upper-bounds in the boolean hierarchy over NP. …
partitions with components that have complexity upper-bounds in the boolean hierarchy over NP. …
Boolean hierarchies of partitions over a reducible base
VL Selivanov - Algebra and Logic, 2004 - Springer
… [3, 4] to a so-called refined Boolean hierarchy of k-partitions over L, denoted by … hierarchies
of partitions have a rather complex structure. In this article we consider Boolean hierarchies …
of partitions have a rather complex structure. In this article we consider Boolean hierarchies …
[PDF][PDF] Classifying omega-regular partitions.
VL Selivanov - LATA, 2007 - researchgate.net
… because it is intimately related to the Boolean hierarchy of k-partitions, see [Se04,Se06]. …
On NP-partitions over posets with an application to reducing the set of solutions of NP problems. …
On NP-partitions over posets with an application to reducing the set of solutions of NP problems. …
[PDF][PDF] On the relative complexity of Post's classes
E Bohler - 44. Workshopuber Komplexitätstheorie …, 2001 - fg-kp.gi.de
… Post identified all closures of Boolean functions under superposition, characterized their …
of the set of Boolean functions we utilize to build circuits, the set of Boolean functions that can …
of the set of Boolean functions we utilize to build circuits, the set of Boolean functions that can …
STACS 2000 [electronic resource]: 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17–19, 2000 Proceedings
H Reichel, S Tison - sidalc.net
… --The Boolean Hierarchy of NP-Partitions--Binary Exponential Backoff Is Stable for High
Arrival Rates--The Data Broadcast Problem with Preemption--An Approximate L p-Difference …
Arrival Rates--The Data Broadcast Problem with Preemption--An Approximate L p-Difference …