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

  • 2
    $\begingroup$ 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 $\endgroup$ – Florent Foucaud Jun 30 '18 at 11:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Michael Wehar Jun 30 '18 at 13:20
  • 1
    $\begingroup$ 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. $\endgroup$ – daniello Jun 30 '18 at 14:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.