| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436722 | Theoretical Computer Science | 2006 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
