Why a digital computer is just a DFA?

Pedantically speaking of course!

A digital computer is just a Deterministic finite automaton, which of course is equivalent to the complexity [or power] of Regular expressions.

How?

A digital computer just has 2^[memory size] states it can go to. So it is equivalent to a DFA having 2^[memory size] states. So in that sense it is no more powerful than a DFA.

But given that these 2^memory size states are huge, it does approximate a universal Turing Machine!

But to reiterate pedantically speaking it is just a DFA with huge number of states!

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!