Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is coNP closed under Kleene star operation?

I have the answers, in which they say it is possible to build a graph that describes all possible divisions of the string in which the sub-words are in in the language, but how can you build this graph if you can only accept (and not both accept and reject) using an NTM?

share|improve this question
    
I think you can use dynamic programming to check the devisions of the string aswel. It's a frequently used method to show that some complexity class is closed under kleene closure. –  sxd Nov 16 '11 at 13:13

2 Answers 2

up vote 2 down vote accepted

I will use verifier based definition of NP and coNP (not that with NTM).

Given a word $w$ and a language $L$ consider a graph on $\{1,2,\dots,|w|+1\}$ where $(i,j)$ is an edge iff $w_{i\dots j-1}\in L$. Then, $w\in L^{\ast}$ iff there is a path from $1$ to $|w|+1$.

Is a complexity class closed under Kleene star?

For P the situation is easy; the machine can compute the graph and perform DFS.

For NP, the machine may guess $O(n^2)$ certificates, compute the graph and accept if there is a path. Every edge in the graph corresponds to an infix in the language. If you guess wrongly, you will incorrectly reject, but here the guesses are directed to accept if possible.

For coNP, the machine may also guess $O(n^2)$ certificates, compute the graph and reject if there is a path. Every edge in the graph also corresponds to an infix. If you guess wrongly, you will incorrectly accept, but here the guesses are directed to reject if possible.


Edit to clarify.

If the task was to show NP is closed under Kleene star, you could write ($L \in NP$):

$x \in L^{\ast}$ iff there exists a partition $x=x_1 x_2 \dots x_n$ such that there exist $n$ strings $y_i$, such that each string $y_i$ is a valid certificate for $x_i$.

And this is enough to show that $L^{\ast} \in NP$, since you can guess both the partition and certificates.

However, if you try to pull the same trick with $coNP$, you will get: ($L \in coNP$):

$x \in L^{\ast}$ iff there exists a partition $x=x_1 x_2 \dots x_n$ such that for all $n$ strings $y_i$, each string $y_i$ is a valid certificate for $x_i$.

this is bad, because you've got both existential and universal quantification, so $L^{\ast}$ is not in the form required for coNP.

The idea is to guess certificates for all $n^2$ infixes of the word at once. Some of them will not be valid, but we won't use them.

If $L \in NP$ you can write:

$x \in L^{\ast}$ iff there exists $O(n^2)$ strings, such that there exists a partition $x=x_1 x_2 \dots x_n$ such that each $x_i$ has a valid certificate.

and check existence of partition using the graph.

Given the $n^2$ certificates, the property "there exists a partition $x=x_1 x_2 \dots x_n$, such that..." is testable in polynomial time; you do not need to guess the partition.

For $L \in coNP$ you can pull the same trick now:

$x \in L^{\ast}$ iff for all $O(n^2)$ strings, there exists a partition $x=x_1 x_2 \dots x_n$, where each $x_i$ has a valid certificate.

and since "the exists a partition..." is testable in polynomial time, it shows that $L^{\ast}$ is in $coNP$.


Edit: Another way to think about it.

You've got a word $w$ and want to show that it is not in $K^{\ast}$, where membership in $K$ can be quickly falsified. To do it, you falsify membership of as many infixes of $w$ as you can. If there is no way the remaining infixes could be joined to get the whole $w$, surely $w \notin K^{\ast}$. On the other hand, if you supplied as many falsifications as possible and there is still a way to break $w$ to $w = w_1 w_2 \dots w_n$ where you cannot falsify membership of any $w_i$, then $w \in K^{\ast}$.


Formal proof.

Suppose $K$ is a $\mathsf{coNP}$ language. This means

$x \in K$ iff $\forall y. P(x,y)$

where $y$ is polynomial with respect to $x$ and $P$ is a polynomial time predicate.

I will show that $K^{\ast} \in \mathsf{coNP}$. So I will define a predicate $R$ such that

$x \in K^{\ast}$ iff $\forall y. R(x,y)$

Here is code of $R$. "Accept" means that $R(x,y)=true$ (in this case $y$ is useless) and "reject" means $R(x,y)=false$ (in this case $y$ certifies that $x \notin K^{\ast}$)

def R(x,y):

  1. Let $n = |x|$.
  2. Split $y$ into $c_{11} \# c_{12} \# \dots \# c_{1n} \# c_{22} \# c_{23} \# \dots \# c_{nn}$, where $c_{ij}$ are some strings, defined only when $i\leq j$. If $y$ is not of this form, we accept.
  3. Create a triangular binary matrix $A$ of size $n+1$. The entry $a_{ij}$ is 0 when $i \geq j$, otherwise it's $P(x[i,j-1], c_{i(j-1)})$
  4. Use $A$ as a matrix of a graph, and check if there is a path from 1 to $n+1$ (BFS).
  5. Accept if there is a path, reject if there is no path.

Clearly $R$ is polynomial time computable.

If $x \in K^{\ast}$ then $x=x_1 \dots x_m$, where $x_i \in K$, so $P(x_i,z)$ is always true. In this case there is a path in the graph for any $y$, so $\forall y. R(x,y)$.

If $x \notin K^{\ast}$ then for any $(i,j)$ such that $x[i,j] \notin K$ we define $c_{ij}$ such that $\neg P(x[i,j], c_{ij})$, and $c_{ij}=\epsilon$ otherwise. Let $y$ be a suitable concatenation of $c_{ij}$.

I claim for such defined $y$ the graph has no path from 1 to n+1, and the algorithm rightfully rejects. Namely, such path would give rise to a partition $x = x_1 x_2 \dots x_n$. However, since $x \notin K^{\ast}$, there exists $i$ such that $x_i \notin K$. Suppose $x_i = x[k,l]$. But in this case we supplied $c_{kl}$ such that this edge should not be present in the graph.

share|improve this answer
1  
Your algorithm for coNP does not work. A nondeterministic Turing machine for the complement of L* is required to certify the absence of a path, and your NTM is doing something else (what it is doing is unclear to me). Hint: Use the same graph, but try to find a cut in the graph. –  Tsuyoshi Ito Nov 16 '11 at 21:21
    
@Tsuyoshi Ito: I don't understand the objection, I'm not searching for complement of L*, but for (complement of L)* where L is in NP. –  sdcvvc Nov 16 '11 at 21:25
    
@Tsuyoshi Ito: Added clarification. –  sdcvvc Nov 16 '11 at 21:51
    
When L is in coNP, “certificate for L” is not well-defined. Now I see that you probably have a correct algorithm in mind (which is indeed simpler than what I was thinking), but it is not correctly stated in your answer. –  Tsuyoshi Ito Nov 16 '11 at 23:20
    
Now I think that I understand what you mean by certificate for a coNP-language, but is that a usual terminology? In what I am familiar with, it is a string which is not a certificate for the complement of L. –  Tsuyoshi Ito Nov 17 '11 at 0:10

This does not answer the question, but hopefully will be helpful in clarifying a few things.

Notation:

  • Let $y \preceq t$ mean that $y \in \{\lambda,0,1\}^{t}$, i.e. $y$ is a binary string of length at most $t$.
  • $\lambda$ is the empty sequence.
  • $L\# = \{ w\# : w\in L \}$ (where $\#$ is a new symbol).

Let $L \in \mathsf{coNP}$, i.e. there are a polynomial $p$ and a predicate $M(x,y)\in \mathsf{P}$ s.t.

$$ x \in L \text{ iff } \forall y\preceq p(|x|) \land M(x,y)$$

Then we have $L\# = \{ w\# : w\in L \} \in \mathsf{coNP}$ .

Now we show that $(L\#)^* \in \mathsf{coNP}$. It is easy since $x \in (L\#)^*$ iff

$$\forall k\leq |x| \ \forall z_1,\cdots,z_{k} \preceq |x| \ \forall c_1 \preceq p(|z_1|), \cdots, c_k\preceq p(|z_k|)$$ $$x\neq z_1\#z_2\#\cdots z_k\# \lor \exists i\leq k \ \lnot M(z_i,c_i)$$

and the second line is a polynomial decidable formula.

This doesn't work for $L^*$ because we don't know where are the partitions and going over all possible partitions will take too much time. The trick above works for $(L\#)^*$ because there is a unique decomposition for the input $x$. In fact an easier way would be just going over the string and for each part separated by $\#$ check co-nondeterministically that it is in $L$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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