Godel's theorem for layman

In mathematics we use:

1. a set of assumptions (axioms) and 
2. use a set of rules for deriving conclusions (inference)
3. Proofs are statements which are derivable from axioms using these rules.

A system is consistent if we can only prove true statements.  That is we can't prove a statement and its opposite.

For example, we can't prove both 2+2 = 4 and 2+2 != 4 in the system. Only one can be proven.

Now we know we can't prove both. Do we know we can prove the true one in all cases?

Godel theorem says no. In a consistent system, there will always be statements which are true but not provable! Sounds odd, but that's exactly the reason the theorem is puzzling and popular!

              THIS STATEMENT IS NOT PROVABLE


The implication is although mathematicians may be working on things like Fermat's last theorem they may not provable even if they are true. So they may be just wasting time [in some sense] trying to prove it. Of course Fermat's last theorem itself was provable and proved by Andrew Wiles.

Layman definition of P, NP and NP-complete

Here is my layman intuition for these important complexity classes:

1. P

All problems which are solvable in polynomial time.
Sorting for example.

2. NP

All problems which can be verified in polynomial time. That is given an instance of a problem and its 'solution' we can tell in polynomial time whether it is indeed a solution or not.
Integer factorization for example.

3. NP-hard

All problems which are harder than NP or at least as hard as NP. Any thing whose verification is exponential will trivially belong to this. 
For example factorial of n.  Or producing all permutations of n.
[Technical nit - problems have to be decision problems for them to be in P, NP etc. but we will ignore this for now]

4. NP-complete 

 

It is in NP - hard  as in 3) above and this can be reduced to a problem in NP. So in a sense NP-completeness brings down the complexity a notch from NP-hard to NP.
For example, subset sum problem. In general many optimization problems end up here.

 

In layman terms:

P <= NP

P+NP-Complete = NP

 

NP < NP-hard

NP-Complete < NP-hard [this follows from previous inequality]

Largest factored number

I was listening about Quantum computation in Quantum theory - lecture 15.

Suddenly I started wondering what is the biggest number [known publicly] to have been factored. As usual I turned to wikipedia.

This number known as RSA-768 is the hardest known number [having only 2 prime factors also called semiprime].

1 ]=> (* 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917)

;Value: 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413


If we purely go by digit size it is:

 1061

2   - 1 

it is 320 digits!