# What relations are there between a problem hardness and the hardness of verifying a witness?

Suppose you are given a Dominating Set instance, $<G,k>$.

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 $<G,k>$ (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-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?
• 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 is in EasyVer, but DomSet in W 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 Mar 6 '14 at 20:28
• 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 Mar 7 '14 at 6:09
• @SureshVenkat, can you please elaborate? – R B Mar 7 '14 at 8:49
• 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 Mar 7 '14 at 22:05
• 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 Mar 8 '14 at 6:10