Is Determining Whether a Regular Expression Denotes 0* an NP-Complete Problem?

[mathmari]

Hey!

Show that the problem of determining whether a regular expression over the alphabet $\{0\}$ does not denote $0^*$ is NP-complete.

Could you give me some hints how I could do that?? (Wondering)

 

[mathmari]

In general, to show that a problem is NP-complete we have to show that it is polynomially transformable to an other problem that we know that it is NP-complete, right?? (Wondering)

How do we know which problem we have to use?? (Wondering)

 

[Evgeny.Makarov]

In general, to show that a problem is NP-complete we have to show that it is polynomially transformable to an other problem that we know that it is NP-complete, right?

No, it's the other way around. And it is usually called "polynomial time reducible".

 

[mathmari]

In my book there is the following definition:

A language $L_0$ in $\mathcal{NP}$ is nondeterministic polynomial-time complete (NP-complete for short) if the following condition is satisfied:
If we are given a deterministic algorithm of time complexity $T(n)\geq n$ to recognize $L_0$, then for every language $L$ in $\mathcal{NP}$ we can effectively find a deterministic algorithm of time complexity $T(p_L(n))$, where $p_L$ is a polynomial that depends on $L$. We say $L$ is reducible to $L_0$.

One way to prove that a language $L_0$ is NP-complete is to show that $L_0$ is in $\mathcal{NP}$ and that every language $L$ in $\mathcal{NP}$ can be ``polynomially transformed`` to $L_0$.

First of all, could you explain me the definition oif NP-complete?? (Wondering)

 

[Evgeny.Makarov]

$L$ is NP-complete if (1) $L\in NP$ and (2) every $L'\in NP$ is polynomial time reducible to $L$. Condition (2) means that there is a function $f$ that is computable in polynomial time on a deterministic Turing machine (DTM) (i.e., there is a DTM that makes at most $p(n)$ steps on any input of length $n$ for some polynomial $p$, and the content of the tape after the machine stops on input $w$ is considered $f(w)$) such that $\forall w\in\Sigma^*\;w\in L'\iff f(w)\in L$.

 

[mathmari]

$L$ is NP-complete if (1) $L\in NP$ and (2) every $L'\in NP$ is polynomial time reducible to $L$. Condition (2) means that there is a function $f$ that is computable in polynomial time on a deterministic Turing machine (DTM) (i.e., there is a DTM that makes at most $p(n)$ steps on any input of length $n$ for some polynomial $p$, and the content of the tape after the machine stops on input $w$ is considered $f(w)$) such that $\forall w\in\Sigma^*\;w\in L'\iff f(w)\in L$.

Ok! I see... Thanks for the explanation! (Smile)

Could you explain me what it means that for example the Hamilton circuit is NP-complete?? (Wondering)

 

[Evgeny.Makarov]

Could you explain me what it means that for example the Hamilton circuit is NP-complete?

Intuitively, it means that Hamilton circuit is the hardest problem in NP (but there are many other hardest problems). Do you want a proof (I can't go into it right now, but it can be found in standard textbooks, such as Lewis & Papadimitriou), or do you want me express the definition in different words?

If you are studying polynomial reducibility, you should have covered m-reducibility used for proving that some languages are undecidable. Usually textbooks, such as the one by Sipser, have a good description of m-reducibility and the idea behind it. Polynomial reducibility has the same idea, but an additional requirement that it should be done in polynomial time.

 

[mathmari]

Intuitively, it means that Hamilton circuit is the hardest problem in NP (but there are many other hardest problems). Do you want a proof (I can't go into it right now, but it can be found in standard textbooks, such as Lewis & Papadimitriou), or do you want me express the definition in different words?

I want to know what it means that the Hamilton circuit is NP-complete.

 

[Evgeny.Makarov]

Replace $L$ in post #5 with "Hamilton circuit", and you will get the meaning of the phrase "Hamilton circuit is NP-complete".

 

[mathmari]

Replace $L$ in post #5 with "Hamilton circuit", and you will get the meaning of the phrase "Hamilton circuit is NP-complete".

To check if the given graph has a hamilton circuit, we have to check if the vertices except from the first one, is appeared once, right?? To do that, is polynomial time complexity needed?? (Wondering)

What does the second condition mean in this case?? (Wondering)

 

[Evgeny.Makarov]

To check if the given graph has a hamilton circuit, we have to check if the vertices except from the first one, is appeared once, right?

What you said is not precise enough to be true or false. A circuit is called Hamilton if it contains every vertex of the graph exactly once (with the exception of the initial vertex, which may be counted twice depending on the definition). But this describes what it means for a graph to have a Hamiltonian circuit, not what it means for the "Hamiltonian circuit" problem to be NP-complete.

To do that, is polynomial time complexity needed?

This is not precise enough, either. Needed for what?

What does the second condition mean in this case?

You have a definition. What more do you want? I asked you if you want me to express it in different words (which I can't really do right now), but you did not answer.

I don't mind giving quick answers (due to lack of time), but you don't seem to have the grasp of the background knowledge needed to discuss this. You need to understand the following concepts: Hamilton circuit (preferably with examples), language HAMGRAPH, m-reducibility and polynomial time reducibility.

 

[mathmari]

What you said is not precise enough to be true or false. A circuit is called Hamilton if it contains every vertex of the graph exactly once (with the exception of the initial vertex, which may be counted twice depending on the definition). But this describes what it means for a graph to have a Hamiltonian circuit, not what it means for the "Hamiltonian circuit" problem to be NP-complete.

The "Hamiltonian circuit" problem is NP-complete, does it mean that p(n) steps are needed to check if the property of a hamiltonian circuit is satisfied, for some polynomial p?? (Wondering)

 

[Evgeny.Makarov]

The "Hamiltonian circuit" problem is NP-complete, does it mean that p(n) steps are needed to check if the property of a hamiltonian circuit is satisfied, for some polynomial p?

Yes, but on a nondeterministic Turing machine. As for deterministic TMs, no polynomial algorithm is known and most people believe that it does not exist.

Edit: This is what it means that "Hamiltonian circuit" is in NP. The second condition of NP-completeness additionally says that every other problem in NP is polynomial time reducible to "Hamiltonian circuit".