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$ 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$ 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.