Theory of Computation

P, NP, NP-Complete, NP-Hard

July 9, 2016 by arjun Leave a Comment

It might be because of the name but many graduate students find it difficult to understand $NP$ problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)

$P$ Problems

As the name says these problems can be solved in polynomial time, i.e.; $O(n)$, $O(n^2)$ or $O(n^k)$, where $k$ is a constant.

$NP$ Problems

Some think $NP$ as Non-Polynomial. But actually it is Non-deterministic Polynomial time. i.e.; “yes/no” instances of these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if it is correct or wrong) in polynomial time by a deterministic Turing machine (or equivalently our computer). Examples include all P problems. One example of a problem not in $P$ but in $NP$ is Integer Factorization.

$NP$ Complete Problems$(NPC)$

Over the years many problems in $NP$ have been proved to be in $P$ (like Primality Testing). Still, there are many problems in $NP$ not proved to be in $P$. i.e.; the question still remains whether $P = NP$ (i.e.; whether all $NP$ problems are actually $P$ problems).

$NP$ Complete Problems helps in solving the above question. They are a subset of $NP$ problems with the property that all other $NP$ problems can be reduced to any of them in polynomial time. So, they are the hardest problems in $NP$, in terms of running time. If it can be showed that any $NPC$ Problem is in $P$, then all problems in $NP$ will be in $P$ (because of $NPC$ definition), and hence $P = NP = NPC$.

All $NPC$ problems are in $NP$ (again, due to $NPC$ definition). Examples of $NPC$ problems

$NP$ Hard Problems $(NPH)$

These problems need not have any bound on their running time. If any $NPC$ Problem is polynomial time reducible to a problem $X$, that problem $X$ belongs to $NP$ Hard class. Hence, all $NP$ Complete problems are also $NPH$. In other words if a $NPH$ problem is non-deterministic polynomial time solvable, it is a $NPC$ problem. Example of a $NP$ problem that is not $NPC$ is Halting Problem.

From the diagram, its clear that $NPC$ problems are the hardest problems in $NP$ while being the simplest ones in $NPH$. i.e.; $NP ∩ NPH = NPC$

Note

Given a general problem, we can say its in $NPC$, if and only if we can reduce it to some $NP$ problem (which shows it is in NP) and also some $NPC$ problem can be reduced to it (which shows all NP problems can be reduced to this problem).

Also, if a $NPH$ problem is in $NP$, then it is $NPC$

Some Reduction Inferences

18,854 total views, 8 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

P, NP, NPC, NPH

$P$ is a subset of $NP$, but whether $P = NP$ is still not known
$NPC$ is a subset of $NP$ (only if $P \neq NP$, $NPC$ is a proper subset of $NP$)
$NPC$ is a proper subset of $NPH$

Reduction

Reducing a problem $A$ to problem $B$ means converting an instance of problem $A$ to an instance of problem $B$. Then, if we know the solution of problem $B$, we can solve problem $A$ by using it.

Consider the following example:

You want to go from Bangalore to Delhi and you can get a ticket from Mumbai to Delhi. So, you ask your friend for a lift from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.

Some Inferences:

Consider problems $A$, $B$ and $C$.

Assume all reductions are done in polynomial time.

Two Important Points:

If $A$ is reduced to $B$ and $B$ $\in$ class $X$, then $A$ cannot be harder than $X$, because we can always do a reduction from $A$ to $B$ and solve $B$ instead of directly solving $A$. This reduction thus gives an upper bound for the complexity of $A$.
If $A$ is reduced to $B$ and $A$ $\in$ class $X$, then $B$ cannot be easier than $X$. The argument is exactly same as for the one above. This reduction is used to show if a problem belongs to $NPH$ – just reduce some known $NPH$ problem to the given problem. This reduction thus gives a lower bound for the complexity of $B$.

Somethings to take care of:

If $A$ is reduced to $B$ and $B$ $\in$ $NPC$, then $A$ $\in$ $NP$
- Here, we cannot say $A$ is $NPC$. All we can say is $A$ cannot be harder than $NPC$ and hence $NP$ (all $NPC$ problems are in $NP$). To belong to $NPC$, all $NP$ problems must be reducible to $A$, which we cannot guarantee from the given statement.
If $A$ is reduced to $B$, $C$ is reduced to $A$ , $B \in NP $ and $C \in$ $NPC$, then $A$ $\in$ $NPC$
- Here, the first reduction says that $A$ is in $NP$. The second reduction says that all $NP$ problems can be reduced to $A$ (because $C$ is in $NPC$, by definition of $NPC$, all problems in $NP$ are reducible to $C$ and now $C$ is reduced to $A$). Hence, the two necessary and sufficient conditions for $NPC$ are satisfied and $A$ is in $NPC$
If $A$ is reduced to $B$ and $B$ $\in$ $NPH$, then $A$ $\in$ $?$
- Here we can’t say anything about $A$. It can be as hard as $NPH$, or as simple as $P$.

6,899 total views, 7 views today

Grammar: Decidable and Undecidable Problems

December 7, 2015 by Arjun Suresh 9 Comments

Heads Up! Please do not by heart this table. This is just to check your understanding

Grammar: Decidable and Undecidable Problems
Grammar	$w \in L(G)$	$L(G) = \phi$	$L(G) = \Sigma^*$	$L(G_1) \subseteq L(G_2)$	$L(G_1) = L(G_2)$	$L(G_1) \cap L(G_2) = \phi$	$L(G)$ is regular?	$L(G)$ is finite?
Regular Grammar	D	D	D	D	D	D	D	D
Det. Context Free	D	D	D	UD	D	UD	D	D
Context Free	D	D	UD	UD	UD	UD	UD	D
Context Sensitive	D	UD	UD	UD	UD	UD	UD	UD
Recursive	D	UD	UD	UD	UD	UD	UD	UD
Recursively Enumerable	UD	UD	UD	UD	UD	UD	UD	UD

Checking if $L(CFG)$ is finite is decidable because we just need to see if $L(CFG)$ contains any string with length between $n$ and $2n-1$, where $n$ is the pumping lemma constant. If so, $L(CFG)$ is infinite otherwise it is finite.

Closure Property of Language Families

December 7, 2015 by Arjun Suresh 9 Comments

Closure property is a helping technique to know the class of the resulting language when we do an operation on two languages of the same class. That is, suppose $L_1$ and $L_2$ belong to CFL and if CFL is closed under operation $\cup$, then $L_1 \cup L_2$ will be a CFL. But if CFL is not closed under $\cap$, that doesn’t mean $L_1 \cap L_2$ won’t be a CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed under an operation, we cannot say anything about the class of the resulting language of the operation – it may or may not belong to the class of the operand languages. In short, closure property is applicable, only when a language is closed under an operation.

Now, while applying closure property do remember the language hierarchy.

Regular $\subset$ DCFL $\subset$CFL $\subset$ REC $\subset$ RE.

So, if CFL is closed under Union, and $L_1$ and $L_2$ belong to CFL, then $L_1\cup L_2$ will be a CFL. But $L_1 \cup L_2$ can also be a regular language, which closure property can’t tell. For this we need to see $L_1$ and $L_2$.

Heads Up! Please don’t learn this table by heart . This is just to check your understanding and some of them are not required for GATE

Closure properties of language families

Operation	Regular	DCFL	CFL	CSL	Recursive	RE
Union	yes	no	yes	yes	yes	yes
Intersection	yes	no	no	yes	yes	yes
Complement	yes	yes	no	yes	yes	no
Concatenation	yes	no	yes	yes	yes	yes
Kleene star	yes	no	yes	yes	yes	yes
Homomorphism	yes	no	yes	no	no	yes
$\epsilon$-free Homomorphism	yes	no	yes	yes	yes	yes
Substitution ($\epsilon$-free)	yes	no	yes	yes	no	yes
Inverse Homomorphism	yes	yes	yes	yes	yes	yes
Reverse	yes	no	yes	yes	yes	yes
Intersection with a regular language	yes	yes	yes	yes	yes	yes

32,855 total views, 28 views today

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

Direct Link

7,696 total views, 6 views today

Identify the Class of a Given Language

September 26, 2015 by Arjun Suresh 4 Comments

1 Given a description of a language $L$, how to find the class of $L$?
2 Some Facts
3 Some Twisted Examples

Given a description of a language $L$, how to find the class of $L$?

Find the set of strings generated by $L$

If the set of strings in $L$ is finite, $L$ is regular since all finite languages are regular
If the set of strings in $L$ is infinite, check if we can draw an NFA for recognizing $L$. If so, $L$ is regular
If $NFA$ is not possible for $L$, check if we can recognize $L$ using a $PDA$, that is with a stack in addition to set of states. If so, $L$ is $CFL$.
If the moves of $PDA$ are all deterministic, then $L$ is a $DCFL$
If $PDA$ is not possible for $L$, see if we can get a $TM$ for $L$
If $TM$ takes only a linear space (in terms of length of input string), then $L$ is $CSL$. otherwise its just recursive
If $L$ is a decision problem and $TM$ can just say “yes” and may not halt in case of “no”, then $L$ is recursively enumerable (partially decidable).
If $TM$ can say both “yes” and “no” then $L$ is recursive
If no $TM$ is possible for $L$, then $L$ is undecidable

Some Facts

Partially undecidable or semi-undecidable is considered undecidable. For example halting problem is considered undecidable but is semi-decidable.
$P$, $NP$ and $NPC$ problems can all be decided by a $TM$ and hence are recursive.
All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable.
Turing decidable problems are recursive but Turing recognizable (Turing acceptable) problems are only recursively enumerable.

Some Twisted Examples

1. $L = \{ww \mid w ∈ (a+b)^*\}$

The set of strings in $L$ are $\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, …\}$. We cannot accept these strings using an $NFA$. Now, even a $PDA$ is not possible as once we store $w$ on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize $L$. Now, $L$ can be accepted by a $TM$ in linear space and hence $L$ is $CSL$.

2. $L = \{ww\mid w ∈ (a+b)^+\}$

Same explanation as above, $L$ is $CSL$.

3. $L = \{ww_R\mid w ∈ ({a+b})^*\}$

$ww_R$ can be accepted by a $PDA$ and hence is $CFL$. But we need a $NPDA$ for this as there is no deterministic way to identify where $w$ ends and $w_R$ starts. $wcw_R, w\in(a+b)^*$ is accepted by a $DPDA$ and hence is $DCFL$.

4. $L = \{ww_R\mid w ∈ ({a+b})^+\}$

Same explanation as above. $L$ is $CFL$.

5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $

$L$ is regular since $ L = \Sigma^*$, by making $x = (a+b)^*$ and $w = \epsilon$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, …\} = \Sigma^*$

This language is different from the $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.

6. $L = \{wxw\mid w,x ∈ ({a+b})^+\}$

$L$ doesn’t contain all strings in $\Sigma^*$ as the strings like $abab$ are not contained in $L$. All words starting and ending in $a$ or starting and ending in $b$ are in $L$. But $L$ also contains words starting with $a$ and ending in $b$ like $abbab, aabbbabaab$ etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings we need a $TM$ with linear space (this is at least as hard as accepting $ww, w \in (a+b)^*$), making $L$, a $CSL$.

7. $L = \{wxw_R\mid w,x ∈ ({a+b})^*\}$

$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, …\} = \Sigma^*$

This language is different from the $L = \{wcw_R \mid w ∈ \{{a,b}\}^*\} $ which is clearly a DCFL. Here, we cannot do any reduction and hence there is no way to accept a string without checking that the string after c is the reverse of the string before c, which requires a DPDA.

8. $L = \{wxw_R\mid w,x ∈ ({a+b})^+\}$

The set of strings in $L$ are $\{aaa, aba, aaaa, aaba, abaa, abba, baab, …\}$ i.e.; $L$ contains all strings starting and ending with $a$ or starting and ending with $b$ and containing at least 3 letters. Moreover, $L$ doesn’t contain any other strings. Thus $L$ can be accepted by a finite automata making $L$ regular . Regular expression for $L$ is $a(a+b)^+a + b(a+b)^+b$.

9. $L = \{wxwy \mid w,x,y ∈ ({a+b})^+\}$

For any string to be in $L$, the beginning part of the string ($w$) must repeat at some other point (between the second and last characters) of the string (next $w$). Since $y$ is there at the end which can generate any string, we can make $w$ as small as possible as per the given condition. So, $w$ can be either $a$ or $b$. We can thus write regular expression for $L$ as $a(a+b)^+a(a+b)^+ + b(a+b)^+b(a+b)^+$

10. $L = \{xwyw \mid w,x,y ∈ ({a+b})^+\}$

Similar explanation for example 9, except that instead of first character being $a$ or $b$ we have the last character. So, regular expression for $L$ will be
$(a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+b$

11. $L = \{wxyw \mid w,x,y ∈ ({a+b})^+\}$

Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab$ and $x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.

12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$

$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, …\} = \Sigma^*$

13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$

Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of an LBA making $L$ a CSL.

14. $L = \{xww_R \mid w,x ∈ ({a+b})^+\}$

Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of a PDA making $L$ a NCFL (non-determinism is required to guess the start of $w$).

16,000 total views, 17 views today

Rice’s Theorem with Examples

September 23, 2015 by Arjun Suresh 21 Comments

Some Confusing Terms

Language Decided

We say a TM decide a language $L$ if it accepts all strings in $L$ and rejects all strings not in $L$. (Here, the TM should not accept any string not in $L$, but when we say a TM accept a word $w$, it may accept any other word also)

Language Recognized

We say a TM recognizes language L if it accepts all strings in L. It may or may not reject any string not in L- i.e., it might go into an infinite loop in case of non-acceptance. (It will never accept a string not in L)

Please go through the below videos first, then the given examples and for more examples see the reference link

Rice’s Theorem

Part 1 (For some undecidable languages)

Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable

1	Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable

For a property of recursively enumerable set to be non-trivial, there should exist at least recursively enumerable languages, (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM).

Thus, as per Rice’s theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. (Obviously there are also other languages which are not recursive).

PS: Any “trivial” property is always decidable – because the decision is known ahead and that is why the property is trivial.

Examples

(1) $L(M)$ has at least 10 strings

We can have $T_{yes}$ for $\Sigma^*$ and $T_{no}$ for $\phi$. Hence, $L = \left\{M \mid L(M) \text{ has at least 10 strings}\right\}$ is not Turing decidable (not recursive). (Any other $T_{yes}$ and $T_{no}$ would also do. $T_{yes}$ can be any TM which accepts at least 10 strings and $T_{no}$ any TM which doesn’t accept at least 10 strings )

(2) $L(M)$ has at most 10 strings

We can have $T_{yes}$ for $\phi$ and $T_{no}$ for $\Sigma^*$. Hence, $L = \{M\mid L(M)$ has at most 10 strings$\}$ is not Turing decidable (not recursive).

(3) $L(M)$ is recognized by a $TM$ having even number of states

This is a trivial property because for any r.e. language we have a TM and even if that TM is having odd number of states we can make an equivalent TM having even number of states by adding one extra state. Thus this set equals the set of recursively enumerable languages and hence decidable.

(4) $L(M)$ is a subset of $\Sigma^{*}$

This is a trivial property. All languages are subset of $\Sigma^{*}$ and hence this set contains all languages including all recursively enumerable languages.

Part 2 (For some unrecognizable language)

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable

1	Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable

For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM) and the property holding set (language of $T_{yes}$) must be a proper subset of the set not having the property (language of $T_{no}$).

Examples

(1) $L(M)$ is finite

We can have $T_{yes}$ for $\phi$ and $T_{no}$ for $\Sigma^*$ ($\phi \subset \Sigma^*$). Hence, $L = \{M\mid L(M)$ is finite$\}$ is not Turing recognizable (not recursively enumerable)

(2) $L(M) = \{0\}$

We can have $T_{yes}$ for $\{0\}$ and $T_{no}$ for $\Sigma^*$ ($\{0\} \subset \Sigma^*$). Hence, $L = \{M\mid L(M) = \{0\}\}$ is not Turing recognizable (not recursively enumerable)

(3) $L(M)$ is regular

We can have $T_{yes}$ for $\phi$ and $T_{no}$ for any non-regular language. Hence, $L = \{M\mid L(M)$ is regular$\}$ is not Turing recognizable (not recursively enumerable)

(4) $L(M)$ is not regular

We can have $T_{yes}$ for $\{a^nb^n\mid n\ge0\}$ and $T_{no}$ for $\Sigma^*$ ($\{a^nb^n\mid n\ge0\}\subset \Sigma^*$). Hence, $L = \{M\mid L(M)$ is not regular$\}$ is not Turing recognizable (not recursively enumerable)

(5) $L(M)$ is infinite

We cannot have $T_{yes}$ and $T_{no}$ such that $L(T_{yes}) \subset L(T_{no})$. Hence, this is not a non-monotonic property and Rice’s $2^{nd}$ theorem is not applicable. Still, $L = \{M\mid L(M)$ is infinite $\}$ is not Turing recognizable (not recursively enumerable)

(6) $L(M)$ has at least 10 strings

We cannot have $T_{yes}$ and $T_{no}$ such that $L(T_{yes}) \subset L(T_{no})$. Hence, this is not a non-monotonic property and Rice’s $2^{nd}$ theorem is not applicable.

This language is in fact Turing recognizable. See here

(7) $L(M)$ has at most 10 strings

We can have $T_{yes}$ for $\phi$ and $T_{no}$ for $\Sigma^*$($\phi \subset \Sigma^*$). Hence, $L = \{M\mid L(M)$ has at most 10 strings$\}$ is not Turing recognizable (not recursively enumerable)

Reference

More Examples can be seen here

29,511 total views, 89 views today