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.