Languages

Problem:

Mixing it up: Let $F$ denote some finite language, $R$ denote some regular language, $C$ denote some context-free language, $D$ denote some decidable language, $E$ denote some
recognizable language, and $N$ denote some non-recognizable language. For each one of the
following statements, prove whether it always holds, sometimes holds, or never holds:


$N - D$ is recognizable

Short answer: never

Support I could enumerate $N - D$, I can also enumerate $D$ because $D$ is decidable. Now I can dovetail to enumerate $N = (N - D) \cup D$, therefore I should not be able to enumerate $N - D$.

$RE$ is context free 

Short answer: sometimes

A finite language is recursive enumerable and also context free.
A recursively enumerable language include $a^n b^n c^n$, which is not context free.

$N \cap F$ is decidable

Short answer: always

$N \cap F$ is finite, and a finite language is always decidable.

$E \cup F$ is recognizable

Short answer: sometimes

E is a recognizable language, it could be finite. F is finite, so E union F could be finite, and a finite language is regular.

E could be $a^n b^n$, and $F$ could be the empty language, so $E \cup F$ is $a^n b^n$ and is not regular.

$N^*$ is non recognizable

Short answer: always

If $N*$ is recognizable, we will have a Turing machine that halt on $N*$. We can modify that machine such that whenever it reach a final state, any input will go to a state that just consume the input and do nothing and never halt, that would become a recognizer for $N$.
Therefore $N^*$ is not recognizable.

$N \cup C$ is finite

Short answer: never

If $N \cup C$ is finite, then $N$ is finite, but finite language is always recognizable.

Coloring Cyborgs

Problem:

Two cyborgs walk into your home, both claiming to be oracles for the graph 3-colorability decision problem. They both always give a yes/no answer in constant time for any instance, and are each self-consistent (i.e. each always gives the same answer for the same instance). However, one is a true oracle and the other is a shameless impostor, and you have a large instance of 3-colorability upon which they disagree. Prove whether it is possible to expose the impostor within time polynomial in the size of that instance.

Short Answer:

The key idea is to use the oracle (that only tell me yes or no) to output the coloring. The one that gives a valid coloring is the right one.

Proof:

We need a gadget for that, first, we add three nodes (call them red - green - blue ) as a triangle to the graph. If we wanted to force a node to be red, simply connect green and blue to it.

Now we have a mechanism to force a node to have a certain color - now we can guess the color of the nodes. Here is an algorithm to extract the 3 coloring from it.

For the cyborg that said the graph is 3 colourable, we run this algorithm:

while (there exists uncolored node)
{
  color it red
  if (the colored graph is not 3 colourable)
  {
    color it green instead
    if (the colored graph is not 3 colourable)
    {
      color it blue instead
      if (the coloured graph is not colourable)
      {
        output "you are fake oracle!";
      }
    }
  }
}
output you are true oracle!

The algorithm do at most 3 coloring attempt for each node, so it is obviously polynomial time!

A Turing-recognizable language consisting of descriptions of Turing machines

Problem:

Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{(M_1 ), (M_2), \cdots \}$, where every $M_i$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_i$ whose description appears in $A$.
(Hint: You may find it helpful to consider an enumerator for $A$.)

Short answer: 

We can adopt the diagonalization argument to produce a decidable language that is not accepted by any of the $M_i$.

Proof:

Consider the language $D$ decided by the following Turing machine

Reject any input that is not a binary number.
Enumerate the ith Turing machine, where $i$ is the input string.
If $M_i$ accept the input string, reject it, otherwise accept it.

Apparently this is a Turing machine, and it is not accepted by any of the $M_i$ (there is always a string $i$ where $M_i$ does not agree with $D$)

Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.

Problem:

Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.

Proof idea:

The number of Boolean function is huge (i.e. exponential exponential) but the number of circuit you can make out of polynomial number of gates is smaller than that.

Proof:

The number of Boolean functions of n input can be counted by listing the output of the Boolean function output starting from

00000..000 = 0
00000..001 = 0
...

There are $2^n$ rows, therefore every unique bit string of length $2^n$ represents an unique Boolean function, so we have $2^{2^n}$ Boolean functions.

On the other hand, if we have a polynomial number of gates, they could be arranged in anyway, the number of circuits could be at most $(cn^s)! < 2^{cn^s} < 2^{2^n}$, therefore, most of the circuits do require more than polynomial number of gates.

Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.

Problem:

Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.

Short proof: 

If such an infinite subset exists, we can compress those strings using a Turing enumerator.

Proof:

If such an infinite subset exists, we build an enumerator of them. By the recursion theorem, we can build a Turing machine that enumerate the strings that infinite subset and stop on the first string that is larger than the representation of itself.

Such a machine must eventually halt because of the set must have a string with length larger than this finite machine.

Show that NP is closed under union and concatenation

Problem:

Show that NP is closed under union and concatenation

Short answer: 

We can build non-deterministic Turing machine to solve the union language and the concatenation language

Proof:

Assume language X and language Y are in NP, we wanted to show X union Y is in NP

Because X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively.

Rename the states in Y so that it does not have the same name as in X.

Build a new non-deterministic Turing machine U as follow:

Create a new start state, for each input symbol, it write the same symbol back to the tape, and non-deterministically go to the start state of X or the start state of Y. Take the union of state and transition function from both X and Y, that is a non-deterministic Turing machine U.

For any string in X, non-deterministic Turing machine U can take a non-deterministic jump to the start state of X, and follow the non-deterministic Turing machine X to finally get accepted.
For any string in Y, non-deterministic Turing machine U can take a non-deterministic jump to the start state of Y, and follow the non-deterministic Turing machine Y to finally get accepted.
For any string that is neither in X nor in Y, non-deterministic jump to either X or Y cannot lead to acceptance.

Therefore we showed the non-deterministic Turing machine U precisely accept X union Y.

Assume language X and language Y are in NP, we wanted to show X concatenate Y is in NP

Because X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively.

Rename the states in Y so that it does not have the same name as in X.

Build a new non-deterministic Turing machine C as follow:

For each final state in X, for each input symbol, write the same symbol back to the tape and jump to the start state of Y, and make it non-final.

For any string in X concatenate Y, it can follow the non-deterministic Turing machine X to go to final state of the original non-deterministic Turing machine X, jump to start state of Y, and then follow it to the final state of Y.

For any string, it cannot possibly go to a final state without going through a original final state of X. (All path to final state goes through it)

But if it goes through to final state through a original final state of X, the string could be split into two pieces where a prefix is in X and a suffix is in Y, that means the string has to be in X concatenate Y.
The contrapositive of this show if a string is not in X concatenate Y, it is not accepted.

Therefore we showed the non-deterministic Turing machine C precisely accept X concatenate Y.

Is NP countable?

Problem: 

Is NP countable?

Short answer: 

yes

Proof:

For each problem in NP - there exists a non-deterministic Turing machine as verifier.
As we can encode non-deterministic Turing machine as finite binary string, the set of non-deterministic Turing machine is countable, therefore the set NP is also countable.