# Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations correspond to the operations that can be implemented by nondeterministic finite state transducers. This result becomes less surprising, if we consider that nondeterministic finite state transducers can provide certificates (or verifiers, or witness strings, I wrongly called this oracle strings initially) of length $O(n)$, where $n$ is the length of the input string.

The definition of the class $\mathsf{NP}$ allows for certificates of length $O(n^c)$, but many $\mathsf{NP}$-complete problems are perfectly happy with certificates of length $O(n)$. The transducer should not change the length of the input uncontrollably, so we need faithful cone operations. For $\mathsf P$, this should be equivalent to closure under e-free homomorphisms. (Intuitively, the homomorphism removes the certificate). Hence my question:

Is the closure of $\mathsf P$ under e-free homomorphisms equal to $\mathsf{NP}$?

As stated above, this question should be equivalent to the question whether certificates of length $O(n)$ (instead of $O(n^c)$) are enough for $\mathsf{NP}$.

• interesting, maybe better on Theoretical Computer Science? apparently "cones" used to be called "trios" eg in hopcroft/ ullman Intro to automata theory, languages, computation, where there is a long discussion. maybe it would help to sketch out more of what a (dis)proof might look like?
– vzn
May 27 '15 at 3:48
• of the 3 cone operations homomorphism, inverse homomorphism, intersection with regular language, arent 1/3 definitely in P? so the problem reduces to inverse homomorphisms?
– vzn
May 27 '15 at 3:58
• Related: Homomorphism erasing information May 27 '15 at 11:23
• @D.W. 1. (a) You are right, "oracle strings" is wrong terminology. I should have said "certificates" or "witness strings". It is basically just a restatement of the definition of non-determinism, which allows to count the number of non-deterministic choices used by the non-deterministic machine. 1 (b) "remove the oracle string" means just this, but... (next comment) 2. The linked "cone" article says "faithful cone operation" means that "closure under homomorphism" is replaced by "closure under e-free homomorphism". May 27 '15 at 14:01
• 1 (b) Is straightforward in a certain sense, but one has to change the alphabet. The letters of the larger alphabet contain both an original input letter, and an additional certificate letter. To "erase the oracle string" (or to "erase the certificate") means to replace this pair of "(original letter, certificate letter)" by "original letter", hence the certificate is removed. May 27 '15 at 14:05