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

CC BY-SA 4.0
2018-06-30T11:05:39.157Z
This 2017 paper, "Parameterized complexity classes beyond para-NP", seems relevant (it considers problems in the polynomial hierarchy): https://www.sciencedirect.com/science/article/pii/S0022000017300089. Also, this 2003 paper "Describing parameterized complexity classes", defines a parameterized complexity class corresponding to every classical class: https://www.sciencedirect.com/science/article/pii/S0890540103001615
Florent Foucaud
CC BY-SA 4.0
2018-06-30T13:20:55.863Z
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
CC BY-SA 4.0
2018-06-30T14:29:24.123Z
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
<cc.complexity-theory><reference-request><np><fixed-parameter-tractable>
Have people looked for parameterized algorithms for problems that are not in NP?
PHD candidate
# Have people looked for parameterized algorithms for problems that are not in NP?

(Asked by: username_0 on 2018-06-29)

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)?

**Tags:** cc.complexity-theory, reference-request, np, fixed-parameter-tractable
> **Comments:**
> **username_1**: This 2017 paper, "Parameterized complexity classes beyond para-NP", seems relevant (it considers problems in the polynomial hierarchy): https://www.sciencedirect.com/science/article/pii/S0022000017300089. Also, this 2003 paper "Describing parameterized complexity classes", defines a parameterized complexity class corresponding to every classical class: https://www.sciencedirect.com/science/article/pii/S0890540103001615  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 0 answers

