7
$\begingroup$

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

$\endgroup$
  • $\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 '15 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 '15 at 3:58
  • $\begingroup$ Related: Homomorphism erasing information $\endgroup$ – Hendrik Jan May 27 '15 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$ – Thomas Klimpel May 27 '15 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$ – Thomas Klimpel May 27 '15 at 14:05
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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