1

I know the title may sound misleading as one class is for parameterized problems and the other not, but hear me out. Say I take a "naturally" parameterized problem (the parameter is part of the input), for example weighted SAT (call it $\operatorname{WSAT}$) asking whether given an instance $(\varphi,k)$ of $\operatorname{WSAT}$ there is a witnessing assignment to $\varphi$ of weight at most $k$ parameterized by $k$. Now here the parameter is part of the input so I can easily talk about the unparameterized problem resulting in the same question and restrictions.

Say I have a naturally parameterized problem $Q$ where an instance of $Q$ is $(x,k)$ and the parameter is $k$.

If I provide a non-deterministic polynomial-time algorithm for $Q$ viewed as an unparameterized problem, I have proven $Q \in NP$. Similarly this shows that $Q \in paraNP$ if viewed as a parameterized problem. \begin{equation} \textit{But I think containment in $Q$ is stronger in this case.} \end{equation}

The reason being that to prove containment in $paraNP$ I can provide a non-deterministic polynomial-time algorithm after a preprocessing algorithm using $k$, that is the running time may well be $2^kpoly(n)$ while when proving containment in $NP$ I'm only allowed to use $poly(k\cdot n)$ time.

Is this right? Are there naturally parameterized problems in $paraNP$ that, after moving to the unparameterized problem are not trivially contained in $NP$? Or may even (up to some complexity assumptions) be believed to not be in $NP$?

Thanks everyone!

0CT0
  • 140

1 Answers1

1

You are correct - paraNP is a bigger set. I think the favorite kind of problem that takes a long time wrt $k$ is 'Will the turing machine $T$ halt in $2^{2^k}$ steps?' (or whatever other terrifyingly large function of $k$ you like). If you fix $k,$ then this problem always takes just constant time, just run the program and find out. But if $k$ is an input, this problem becomes extremely hard.

Artimis Fowl
  • 1,882