Parameterized Random Complexity |
| |
| Authors: | Juan Andrés Montoya Moritz Müller |
| |
| Affiliation: | 1. Escuela de Matemáticas, Universidad industrial de Santander, Bucaramanga, Colombia
2. Kurt G?del Research Center, University of Vienna, Vienna, Austria
|
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
