# Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the solution size)?

• This 2017 paper, "Parameterized complexity classes beyond para-NP", seems relevant (it considers problems in the polynomial hierarchy): sciencedirect.com/science/article/pii/S0022000017300089. Also, this 2003 paper "Describing parameterized complexity classes", defines a parameterized complexity class corresponding to every classical class: sciencedirect.com/science/article/pii/S0890540103001615 – Florent Foucaud Jun 30 '18 at 11:05
• I'm very interested the parameterized complexity classes XL, XNL, and XP. Complete parameterized problems for these classes correspond with classical PSPACE and EXPTIME complete problems. – Michael Wehar Jun 30 '18 at 13:20
• Model checking a first order formula $\phi$ on graphs of maximum degree $\Delta$ is FPT with combined parameter $\phi, \Delta$, but is PSPACE-complete when $\phi$ is not a parameter, even if the input graph consists of just two vertices. – daniello Jun 30 '18 at 14:29