Reductions parametriques La W hierarchie Deux exemples L'hypothese de complexite exponentielle ETH

Reductions parametriques La W -hierarchie. Deux exemples L'hypothese de complexite exponentielle (ETH) Complexite parametree (3) Reductions parametrees et classes de complexite Christophe PAUL (CNRS - LIRMM) November 5, 2010 Christophe PAUL (CNRS - LIRMM) Complexite parametree (3) Reductions parametrees et classes de complexite

• alphabet fini


• ?? ?


• complexite


• fpt


• ??


• parametres sur les alphabets respectifs


• hypothese de complexite exponentielle


• classe de complexite fpt


• reductions parametrees


• parametrisation de ??