<p>If I get it right, you are interested in those parameterized problems that can be verified by a bounded-time NTM (running in time $f(k)$ for some function of the parameter). Up to fpt-reduction, these are precisely the problems in the class $W[1]$, see "On the parameterized complexity of short computation and factorization" by Cai, Chen, Downey and Fellows.</p>

CC BY-SA 3.0
2014-03-09T15:23:46.443Z
I'm not sure I understand your answer.
FVS for example is even FPT, but it doesn't seem you can verify a feedback set without looking at all of the graph.
R B
CC BY-SA 3.0
2014-03-09T15:32:43.323Z
That's why I wrote "up to fpt-reduction", as $W[1]$ can defined as the class of problems fpt-reducible to _Short Nondeterministic Turing machine Computation_. If you focus on bounded-time verification, it may be possible to define a variant of $W[1]$ using a different type of reduction...
Super8
CC BY-SA 3.0
2014-03-08T20:10:10.457Z
2014-03-08T20:10:10.457Z
Super8
<p>In <a href="https://cstheory.stackexchange.com/questions/21409/what-relations-are-there-between-a-problem-hardness-and-the-hardness-of-verifyin">a related question</a> I've defined a class of graph problems which are verifiable using a time related only on the size of the witness:</p>

<p>$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.</p>

<p>You can assume that the verifier has random access to the graph adjacency matrix in $O(1)$ time.</p>

<p>Examples for $EasyVer$ problems will be $VC, Clique, IS$ and $Steiner Tree$.</p>

<p>Also, many packing and problems, $triangle-packing$, $k-path-packing$, or in general $H-packing$ for a graph $H$ with constant treewidth, are all in $EasyVer$.</p>

<p>Problems which aren't in (i.e. require more extensive interaction with the input) are also easily found: $VC, DominatingSet, FVS$(Feedback Vertex Set).</p>

<p>In order to get a sense of how $EasyVer$ relates to known complexity classes it would be useful to have a list of problem it contains.</p>

<p><strong>Which other NP-complete problem (or even better, problem classes) can be verified in $poly(k)$ time, where $k$ is the size of the problem witness?</strong></p>

CC BY-SA 3.0
2014-03-08T20:58:57.067Z
@RickyDemer - you can assume that the verifier has random access to the graph adjacency table, I've edited the question.
R B
CC BY-SA 3.0
2014-03-08T21:04:38.993Z
@RickyDemer, perhaps we should then go back to my previuous question, where I asked what's the right way to define this class: http://cstheory.stackexchange.com/questions/21409/what-relations-are-there-between-a-problem-hardness-and-the-hardness-of-verifyin.
R B
CC BY-SA 3.0
2014-03-08T21:59:22.607Z
You can resolve that issue by using an input-dependent verifier, i.e. a NTM whose alphabet/transitions depend on the input. See my reply below.
Super8
CC BY-SA 3.0
2014-03-09T02:34:14.667Z
@RickyDemer: Well, it depends what you mean by "word RAM". Technically, as the verifier is input-dependent you can encode the input directly in the machine states, hence no need for a random access to an external input.
Super8
CC BY-SA 3.0
2014-04-08T21:11:16.963Z
Maybe you could specify in more detail what you mean by $k$-clique being verifiable in poly($k$) time?  My first take was "but that's in $\Omega(n^k)$", and even after reading the comments above I remain confused about your model of computation.
András Salamon
<cc.complexity-theory><graph-theory><graph-algorithms><complexity-classes>
Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size
R B
# Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

(Asked by: username_0 on 2014-03-08)

In [a related question](https://cstheory.stackexchange.com/questions/21409/what-relations-are-there-between-a-problem-hardness-and-the-hardness-of-verifyin) I've defined a class of graph problems which are verifiable using a time related only on the size of the witness:

$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.

You can assume that the verifier has random access to the graph adjacency matrix in $O(1)$ time.

Examples for $EasyVer$ problems will be $VC, Clique, IS$ and $Steiner Tree$.

Also, many packing and problems, $triangle-packing$, $k-path-packing$, or in general $H-packing$ for a graph $H$ with constant treewidth, are all in $EasyVer$.

Problems which aren't in (i.e. require more extensive interaction with the input) are also easily found: $VC, DominatingSet, FVS$(Feedback Vertex Set).

In order to get a sense of how $EasyVer$ relates to known complexity classes it would be useful to have a list of problem it contains.

**Which other NP-complete problem (or even better, problem classes) can be verified in $poly(k)$ time, where $k$ is the size of the problem witness?**

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, complexity-classes
> **Comments:**
> **username_0**: @RickyDemer - you can assume that the verifier has random access to the graph adjacency table, I've edited the question.  
> **username_0**: @RickyDemer, perhaps we should then go back to my previuous question, where I asked what's the right way to define this class: http://cstheory.stackexchange.com/questions/21409/what-relations-are-there-between-a-problem-hardness-and-the-hardness-of-verifyin.  
> **username_1**: You can resolve that issue by using an input-dependent verifier, i.e. a NTM whose alphabet/transitions depend on the input. See my reply below.  
> **username_1**: @RickyDemer: Well, it depends what you mean by "word RAM". Technically, as the verifier is input-dependent you can encode the input directly in the machine states, hence no need for a random access to an external input.  
> **username_2**: Maybe you could specify in more detail what you mean by $k$-clique being verifiable in poly($k$) time?  My first take was "but that's in $\Omega(n^k)$", and even after reading the comments above I remain confused about your model of computation.  

---

## 1 answers

### Answer by username_1 on 2014-03-08. Score: 1

If I get it right, you are interested in those parameterized problems that can be verified by a bounded-time NTM (running in time $f(k)$ for some function of the parameter). Up to fpt-reduction, these are precisely the problems in the class $W[1]$, see "On the parameterized complexity of short computation and factorization" by Cai, Chen, Downey and Fellows.

> **Comments:**
> **username_0**: I'm not sure I understand your answer. FVS for example is even FPT, but it doesn't seem you can verify a feedback set without looking at all of the graph.  
> **username_1**: That's why I wrote "up to fpt-reduction", as $W[1]$ can defined as the class of problems fpt-reducible to _Short Nondeterministic Turing machine Computation_. If you focus on bounded-time verification, it may be possible to define a variant of $W[1]$ using a different type of reduction...  

---

