We give simple, self-contained proofs of the basic hardness results for the classes W[t] of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W[1, s] and the normalization of weft-t formulas arise as by-products of the proofs.
展开▼
机译:我们给出了纬纱等级W [t]的基本硬度结果的简单,独立的证明。我们将这些证明扩展到层次结构的更高级别,并阐明其类别之间的区别。 W [1,s]处的反单调塌陷和weft-t公式的归一化是证明的副产品。
展开▼