Prev: The ludicrous theories of official Geology ( Gogology in fact i.e. the science of Gogos) in the light of the findings of the True Geology
Next: Intro to "The Theory of Reality"
From: OsherD on 28 Mar 2010 03:07
From Osher Doctorow

Oleg Pikhurto, Joel Spencer (of N.Y.U. USA), and Oleg Verbitsky, in
"Succinct definitions in the first order theory of graphs." 41 pages,
arXiv: math/0401307 v2 [math.LO] 31 Mar 2004, define:

1) A 1st order sentence A "defines" a graph G if it is true on G and
flase on any graph not isomorphic to G.

2) L(G) = minimum length of all first order sentences A in (1).
3) D(G) = minimum quantifier length of all 1st order sentences A in
(1).
4) Succinctness Function s(n) = min L(G) over all graphs G on n
vertices.
5) Variant of s(n) called q(n) = like (4) but min D(G).

They then prove:

6) q(n) < log*(n) + 5, where log*(n) = minimum number of iterations of
the binary logarithm sufficient to lower n to 1 or below.

7) D(G) > = [1 - o(1)]log*(L(G))

Osher Doctorow

From: OsherD on 28 Mar 2010 03:12
From Osher Doctorow

In (1), "flase" should be "false".

Osher Doctorow
 | 
Pages: 1
Prev: The ludicrous theories of official Geology ( Gogology in fact i.e. the science of Gogos) in the light of the findings of the True Geology
Next: Intro to "The Theory of Reality"