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}$.
Asked By : Thomas Klimpel
Answered By : D.W.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42983
0 comments:
Post a Comment
Let us know your responses and feedback