# How can the xor function be formed with a single hidden layer of neural network?

I was recently viewing Andrew Ng's deep learning specialization lectures and I came forward to the following image

It is pretty obvious how the above function( x1 XOR x2 XOR x3..... XOR xn) can be implemented using multiple layers of a neural network. Ng told in the lecture that it is also possible to implement the above function using just a single hidden layer of NN. Is it possible ? If so , how? Also , what will be the time complexity difference between a single hidden layer of NN vs multiple layers of NN for the above function?

• Not so obvious to me. Could you add some context? – generic_user Oct 20 '17 at 16:40
• What do you mean by complexity difference? The tag time-complexity is about computational complexity (roughly, computational time as a function of sample size). – Richard Hardy Oct 20 '17 at 16:47
• @generic_user Here is the link of the video I am talking about :-coursera.org/learn/neural-networks-deep-learning/lecture/rz9xJ/… – Anukarsh Singh Oct 20 '17 at 16:47
• @RichardHardy Sorry I was talking about with reference to time complexity only. – Anukarsh Singh Oct 20 '17 at 16:49
• I was asking about time complexity because Andrew Ng told that the time complexity for a multi- layered neural network for the above function will be less as compared to that of a single layer of NN. – Anukarsh Singh Oct 20 '17 at 16:56

He's "hand waving" here. The logic goes like this. You have N logical inputs, which means that the truth table has N dimensions with two values each, so its volume is $2^N$. Hence, he says, you need $2^n$ neurons in the hidden layer, followed by one output. Imagine multi-class classification network such as softmax.
That's how he's saying that you need a very wide $2^N$ node hidden layer, instead of a deep one with only $N\log_2 N$ nodes. What he's not talking about is the problem of separability, i.e. why would you need $2^N$ neurons in the hidden layer.
You can do a single hidden layer NN, or do a multi-layer NN. To do a single hidden layer, you need $2^N$ hidden units, each unit is matching with one of the possible enumerations of the $N$ inputs (each input can be $0$ or $1$, so total enumerations is $2^N$). For a multi-layer NN, you are building a binary tree so complexity is $O(\log N)$.
Note during the lecture Andrew Ng said for single layer you can technically only use $2^{N-1}$ hidden units. I believe this is a mistake but I hope someone can confirm.