首页 | 本学科首页   官方微博 | 高级检索  
     


Simplifying the weft hierarchy
Authors:Jonathan F Buss  Tarique Islam
Affiliation:School of Computer Science, University of Waterloo, Ont., Canada N2L 3G1
Abstract:We give simple, self-contained proofs of the basic hardness results for the classes Wt]Wt] 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 W1,s]W1,s] and the normalization of weft-tt formulas arise as by-products of the proofs.
Keywords:Fixed-parameter complexity  WW-hierarchy" target="_blank">gif" overflow="scroll">W-hierarchy  Weft
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号