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

  • $\begingroup$ 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? $\endgroup$
    – vzn
    May 27, 2015 at 3:48
  • $\begingroup$ 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? $\endgroup$
    – vzn
    May 27, 2015 at 3:58
  • $\begingroup$ Related: Homomorphism erasing information $\endgroup$ May 27, 2015 at 11:23
  • $\begingroup$ @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". $\endgroup$ May 27, 2015 at 14:01
  • $\begingroup$ 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. $\endgroup$ May 27, 2015 at 14:05

1 Answer 1


As Ryan Williams explains on CSTheory.SE, the answer is probably no: certificates of linear size are probably not enough for NP; some NP problems seems to require certificates of super-linear size.

You can also find some examples of NP-problems that appear to require super-linear certificates over on CSTheory: see Natural NP-complete problems with “large” witnesses and Is the Witness Size of Membership for Every NP Language Already Known?. Also Problem unsolvable in 2o(n) on inputs with n bits, assuming ETH? might be relevant as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.