Probabilistic Parameterized Polynomial Time

Nils Donselaar

We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parame…