<p>I had some hard times trying to formulate the question, so I'll start with some examples:</p>

<p>Suppose you are given a Dominating Set instance, $&lt;G,k&gt;$.</p>

<p>Now suppose I give you a set of vertices $D$ of size $k$. Deciding whether $D$ is a dominating set of $G$ requires linear time in the size of $G$, and doesn't seem to be possible only by looking at the vertices of $D$.</p>

<p>In contrast, if we have a $k-path$ instance $&lt;G,k&gt;$ (asking whether a simple path of length $k$ exists in $G$), and I give you a tuple $P$ of $k$ vertices, you can verify that $P$ is a k-path by reading merely $k$ bits of the adjacency table.</p>

<hr>

<p>In general, assume you have some graph problem that includes a parameter$L\subset \mathcal{G}\times \mathbb{N}$, <strong>whose witness is a set of $k$ vertices/edges</strong> ($k$ is the parameter of the problem).</p>

<p>Now we can define the set of problems which are "easy" to verify as:</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>It seems, for example, that $EasyVer \not\subset FPT$ and $FPT \not\subset EasyVer$, as </p>

<ol>
<li>$VC\in FPT, VC \notin EasyVer$.</li>
<li>$Clique\in EasyVer$, while Clique is $W[1]-hard$.</li>
</ol>

<hr>

<ul>
<li>Does my definition even make sense?</li>
<li><strong>Are there known complexity classes with similar meaning?</strong></li>
<li>Any other complexity relations to known classes?</li>
<li>Does it makes more sense to define $EasyVer$ in terms of the number of bits a verification algorithm needs to read from the adjacency matrix?</li>
<li>Does generalizing the definition to $Ver_{f(n,k)}=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in time $O(f(|G|,k))$ $\}$ makes sense?</li>
</ul>

CC BY-SA 3.0
2014-03-06T20:28:40.303Z
This is a neat observation and a nice question. Perhaps explicitly state that poly(k) in the definition of EasyVer should be independent of n and m. Also maybe observe that parameterized hardness does not imply anything about EasyVer. Clique in W[1] is in EasyVer, but DomSet in W[2] is not in EasyVer. Also, don't state that Clique is not in FPT since it is dependent on the open problem of whether FPT = W[i] for any i>0.
JimN
CC BY-SA 3.0
2014-03-07T06:09:52.757Z
If you're willing to relax "independent of n" to "only weakly interacting with the input" there's an active body of work on this topic.
Suresh Venkat
CC BY-SA 3.0
2014-03-07T08:49:57.490Z
@SureshVenkat, can you please elaborate?
R B
CC BY-SA 3.0
2014-03-07T22:05:55.183Z
Just some quick thoughts: (1) This seems related to the PCP theorem, but without any randomness. (2) I think that asking about witness size is very close to asking about the nondeterministic time complexity of the algorithm, i.e. you want those problems solvable in sublinear nondeterministic time and space (in fact time/space parameterized by k) in RAM or some such model. This maybe relates to your final question (#5), depending on if your model of computation requires you to scroll all the way through the adjacency list to get to some particular entry.
usul
CC BY-SA 3.0
2014-03-08T06:10:30.840Z
There are two ways people have studied to reduce interaction with the input: (1) only allow sublinear number of probes of the input (2) only allow streaming access to the input (with sublinear working space). In these cases, there are results characterizing what you can compute in a single round or even in multiple prover/verifier rounds. In all cases the verifier is randomized though.
Suresh Venkat
<cc.complexity-theory><np-hardness><complexity-classes>
What relations are there between a problem hardness and the hardness of verifying a witness?
R B
# What relations are there between a problem hardness and the hardness of verifying a witness?

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

I had some hard times trying to formulate the question, so I'll start with some examples:

Suppose you are given a Dominating Set instance, $$.

Now suppose I give you a set of vertices $D$ of size $k$. Deciding whether $D$ is a dominating set of $G$ requires linear time in the size of $G$, and doesn't seem to be possible only by looking at the vertices of $D$.

In contrast, if we have a $k-path$ instance $$ (asking whether a simple path of length $k$ exists in $G$), and I give you a tuple $P$ of $k$ vertices, you can verify that $P$ is a k-path by reading merely $k$ bits of the adjacency table.

---

In general, assume you have some graph problem that includes a parameter$L\subset \mathcal{G}\times \mathbb{N}$, **whose witness is a set of $k$ vertices/edges** ($k$ is the parameter of the problem).

Now we can define the set of problems which are "easy" to verify as:

$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|$.

It seems, for example, that $EasyVer \not\subset FPT$ and $FPT \not\subset EasyVer$, as

1. $VC\in FPT, VC \notin EasyVer$.
2. $Clique\in EasyVer$, while Clique is $W[1]-hard$.

---

* Does my definition even make sense?
* **Are there known complexity classes with similar meaning?**
* Any other complexity relations to known classes?
* Does it makes more sense to define $EasyVer$ in terms of the number of bits a verification algorithm needs to read from the adjacency matrix?
* Does generalizing the definition to $Ver\_{f(n,k)}=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in time $O(f(|G|,k))$ $\}$ makes sense?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes
> **Comments:**
> **username_1**: This is a neat observation and a nice question. Perhaps explicitly state that poly(k) in the definition of EasyVer should be independent of n and m. Also maybe observe that parameterized hardness does not imply anything about EasyVer. Clique in W[1] is in EasyVer, but DomSet in W[2] is not in EasyVer. Also, don't state that Clique is not in FPT since it is dependent on the open problem of whether FPT = W[i] for any i>0.  
> **username_2**: If you're willing to relax "independent of n" to "only weakly interacting with the input" there's an active body of work on this topic.  
> **username_0**: @SureshVenkat, can you please elaborate?  
> **username_3**: Just some quick thoughts: (1) This seems related to the PCP theorem, but without any randomness. (2) I think that asking about witness size is very close to asking about the nondeterministic time complexity of the algorithm, i.e. you want those problems solvable in sublinear nondeterministic time and space (in fact time/space parameterized by k) in RAM or some such model. This maybe relates to your final question (#5), depending on if your model of computation requires you to scroll all the way through the adjacency list to get to some particular entry.  
> **username_2**: There are two ways people have studied to reduce interaction with the input: (1) only allow sublinear number of probes of the input (2) only allow streaming access to the input (with sublinear working space). In these cases, there are results characterizing what you can compute in a single round or even in multiple prover/verifier rounds. In all cases the verifier is randomized though.  

---

## 0 answers

