Parameterized Random Complexity

作     者：Andres Montoya, Juan Mueller, Moritz 

作者机构：Univ Ind Santander Escuela Matemat Bucaramanga Colombia Univ Vienna Kurt Godel Res Ctr Vienna Austria 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2013年第52卷第2期

页      面：221-270页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：John Templeton Foundation Myriad Aspects of Infinity FWF (Austrian Research Fund) [P23989-N13] Austrian Science Fund (FWF) [P23989] Funding Source: Austrian Science Fund (FWF) 

主　　题：Parameterized complexity theory Random complexity Probability amplification Derandomization Parameterized counting complexity Uniqueness problems 

摘      要：The classes W[P] and W[1] are parameterized analogues of NP in that they can be characterized by machines with restricted existential nondeterminism. These machine characterizations give rise to two natural notions of parameterized randomized algorithms that we call W[P]-randomization and W[1]-randomization. This paper develops the corresponding theory.