Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR96-022 | 15th March 1996
Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

Many Boolean functions have short representations by OBDDs (ordered
binary decision diagrams) if appropriate variable orderings are used.
For tree-like circuits, which may contain EXOR-gates, it is proved
that some depth first traversal leads to an optimal variable ordering.
Moreover, an optimal variable ordering and the resulting OBDD
can ... more >>>


TR96-021 | 13th February 1996
Yongge Wang

NP-hard Sets Are Superterse unless NP Is Small

We show that the class of sets which can be polynomial
time truth table reduced to some $p$-superterse sets has
$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard
for $E$. Also we give a partial affirmative answer to
the conjecture by Beigel, Kummer and ... more >>>


TR96-020 | 6th March 1996
C.P. Schnorr, Carsten Rössner

An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension



previous PreviousNext next


ISSN 1433-8092 | Imprint