Sun Mon Tue Wed Thu Fri Sat
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30
This morning, we got a letter from the government to tell us
that Q Fever
has been detected at a goat/sheep farm within 5 Km of our home
address. The letter did not specify the address, but I did
find some map on a web site about Q fever in the Netherlands. In the past
three Q Fever has grew into an epidemic in the Netherlands
with a growing number of cases each year. On the right it gives
a part of the map. The red dot is the location of the farm
and the circle around it is the 5 Km circle around it. Our home
address is near the blue cross and approxamitely 2 Km away from
the infected farm.
This afternoon, I went to bookshop
De Slegte and I bought two books. I paid them at 16:18:39.
I bought Dune by Frank Herbert,
published by New English Library, 1974, ISBN:0450027279. When I saw
this, I realized that I never read this book in English. I doubted
wheter I should buy th book, because it misspelled 'Arrakis' with
'Arrauis' on the first page. I payed € 4.00. The other book
I bought was Buiten is het maandag (Outside it is Monday)
by J. Bernlef,
ISBN:9021452782. I payed € 5.99 for it.
Today, our magnolia started to bloom
again. It was a warm and sunny day. By the end of the day many
flowers had opened.
Just before I wanted to leave from the office, some colleagues
mentioned the movie Avatar.
I already had been thinking about whether I should go to this
movie this weekend or not. When they mentioned it, I quickly became
enthousiastic and after some discussions we decided to go this
evening. I biked home, prepared some dinner (consisting of
tofu, leek, and eggs), and biked back. I arrived 50 minutes early
because we had to collect our reserved tickets. To save my time,
I did read some pages of Perfect
Rigor. The movie started around 21:25. They also showed
the trailer for the next Shrek movie in 3D. I found the movie
quite impressive, more than I had expected. Of course, we did
discussed some of the 'strange' plot changes and minor glitches
in the animation. We also noticed that you get used to the 3D
quite quickly and we felt that it was more prominent in the first
part of the movie.
The idea of trees communicating, and all the threes on the planet
forming a kind of collective 'brain' is interesting. But for organism
like a tree, who are stationary, and not being able to move there is
not much purpose in developing senses and a neural network. And
all the animals having antennae is also weird. Why would the animals
develop such an organ. In the later part of the film there also
seems to be a lot telepathic communication going on between the
'trees' and the animals.
De Slegte: Three books
This afternoon, at 12:10:21, I bought the following three
books from De Slegte:
The manager of the shop told me that they ready with the
reorganisation and that the top floor has been cleared.
They are going to use it as a storage area.
I just read the excing news (see Investigational Immune Intervention Slows Brain Shrinkage
in Alzheimer's Patients) about some objective effect of Gammagard
on the shrinkage of the brain of people with Alzheimer's Disease. At least this is the result of the phase II
trial. The phase III trial will soon start. As far as I know it will
only be held in the USA and Canada, which means that we could not join
- Hersenschimmen by J. Bernlef. Including DVD with
the movie Hersenschimmen. ISBN:9789021453194.
- Buiten is het maandag by J. Bernlef.
ISBN:9789021452784. € 5.99.
- Maak mij blij by Karin Giphart. Including DVD.
ISBN:9789038827285. € 4.99.
Today, we had a perfect blue sky without a single contrails. Not so
strange, because there was only one flight in the Netherlands, a test
flight with the PH-BGB, a Boeing 737. There was no sign of any ashes in the
sky. The test flight also did not encounter any serious problems.
I guess that normal flights will be resumed soon.
The Eyjafjallajökull is still producing ashes
(webcam: eyjafjallajökull frá valahnjúk). It is not clear
if and when these arrive in Europe. (See Meteosat 0 degree Dust Central Europe.)
If the Katla erupts far more ashes could be produced.
Going to China
This evening, I have booked our flights to China. After some
considerations, we decided that Li-Xia and I will be going to Urumqi
from Tuesday, July 13 till Thursday, July 29. We are flying with China
Southern (but some of the flights will be done by KLM). Our flight
Dusseldorf - Amsterdam 12/07 CZ 7786 18:25 19:20
Amsterdam - Beijing 12/07 CZ 346 20:55 12:40
Beijing - Urumqi 13/07 CZ 6908 15:45 19:45
Urumqi - Beijing 29/07 CZ 6911 08:10 11:45
Beijing - Amsterdam 29/07 CZ 345 14:20 18:35
Amsterdam - Dusseldorf 29/07 CZ 7781 21:40 22:30
The reason we are flying from Düsseldorf (Germany) is because this is
about 200 euro (per person) cheaper than flying from Amsterdam. We will
drive by car to Düsseldorf, which is less than two hours from where we
live and park our car there (which will cost about 100 euro). Traveling
by train from Enschede to Amsterdam would also cost more than 100 euro.
Is it true that after the eruption of the Eyjafjallajökull vulcano,
the 'big sister' Katla
will explode. The Eyjafjallajökull erupts less frequent than the
Katla and according recorded history every time it did erupt the Katla
erupted as well. Since yesterday the seismic activity below the Katla has increased and some locals
think it might erupt very soon. The eruptions of the Katla are on
average more violent and could last for months. One of the possible
least serious consequences could be that our trip to China is in danger.
Today, the book Dicionário ee Bandeirantes e Sertanistas
do Brasil by Francisco de Assis Carvalho Franco (ISBN:8531900212) arrived in the mail. I bought it through the
internet. On July 4, 1995, this book was bought by
Boudewijn Büch in Sao Paulo as says a note on the first page of the book.
Büch was, besides an author and television personality famous
for his documentary still of programs, a bibliophile, who during
his life collected about 100.000 books in his library, which he
called Bibliotheca Didina et Pinguina. The Dicionário
was part of this library. I also own the
three volumes of the auction catalogue of this library.
Difficult Exact Cover problems
The past days, I have been thinking about ways to construct
very difficult Exact Cover problems.
The idea is to construct a complex as possible Exact Cover
problem that only has one solution. The idea I am working
on is to start with the complete graph on n points.
A complete graph (with n > 2) has (n-1)!/2
acyclic Hamiltonian cycles. Lets define c as this number.
You need ceiling(log2(c)+2)
bits to encode these numbers (exclude representation
consisting of only zero's and one's). Lets define m as this
number plus one, than I think it is possible to construct an
Exact Cover with vectors of length nm with n+(n-1)c
vectors, such that it only has one solution, and that there
are n+(n-1)c over n combinations
of vectors to choose the one solution from. The idea is to
divide each vector in n segments of length m
where each segments represents one point in the graph. First
we create n vectors where everytime one of the segments
is filled with one's all other positions with zero's. This represents
the one solution. Then for each Hamiltonian Path we pick a
unique number a bigger than 0 and smaller than 2m-1)
such that both a and its complement are not used for any
other path. Next we remove an arbitrary edge from the path.
For each of the remaining (i,j) edges we create
a vector where segment i is filled with the representation
of a and segment j is filled with the complement of
a. Of course, the columns and the vectors can be scrambled
to hide the unique solution.
Furthermore, I believe that it is possible to select the unique
numbers and the edges that are left out in such a manner that
the one's are spread quite uniform over the columns. I also
believe it is possible to proof that there is but one solution.
Difficult Exact Cover problems
I just realized that instead of using Hamiltonian path with a
random edge removed for incomplete solutions, it is also possible
to use Hamiltonian paths for constructing very difficult
Exact Cover problems. A complete graph
(with n > 1) has n!/2 acyclic Hamiltonian paths.
Although this increases the number of vectors for the incomplete
solutions with n, it also increases the size of the vectors,
because the value for m also increases.
This afternoon, I finished reading the book
Perfect Rigor by Masha Gessen
about Grigory Perelman in which
I started reading on April 6, after I received it from Bol.com where
I order it on Sunday, March 28. I found this
book a little meager with respect to Perelman. If one would pick five
random pages and show it to a stranger, this stranger might not get
the idea that this book is about Perelman. I also feel it scarse on
biographic details. I do not share the opinion expressed in the the review
Nasty and petty book, but great information on Amazon.com.
The book has increased my doubts with respect to whether Perel man
will ever accept the one million dollar price
that has been awared to him by the Clay Mathematics Institute.
P versus NP
Now that Grigori Perelman has
solved one of the seven Millenium Problems from the Clay Mathematics Institute there are still six left. (There is
still no sign whether he had made up his mind with respect to accepting
the price.) Of these problems the P versus NP
problem is the one
that I think I understand best. NP is a class of problems for which
it is 'easy' to check if a solution is correct. But that does not
mean that it is also 'easy' to find a solution. Easy here means that
the number of steps required to find a solution (on a Turing machine)
is limited by some polynomial function to the size of the problem.
A large number of NP problems have been found for which no 'easy'
algorithm has been found yet. It also has been proven that many of
these problems are basically the same, because they can be mapped
upon each other. These are called NP-complete.
Not so long a go, it was proven (see The Complexity of Flood Filling Games) that the
Flood-It! game is
NP-hard, which means that it is at least NP-complete, but possibly
even more complex. Robert
Aubrey Hearn deals with the complexity of many games in his PhD
thesis Games, Puzzles and Computation.
The NP-complete problem that I have worked on the most is the
Exact Cover problem. This made me
think about answering the question whether there is an 'easy'
algorithm for solving Exact Cover problems. I am very strongly
inclined to believe that such an algorith does not exist and that
the complexity classes NP and P are not equal. Many computer
scientist and complexity expert share this opinion. The problem
is that it is very difficult to proof, because you have to show
that something does not exists, while there are an almost unlimited
number of 'easy' algorithms. Many people already have tried to
proof the equality or unequality of NP and P. For more information
P-versus-NP page by Gerhard J. Woeginger. The paper Faster Solutions for Exact Hitting Set and Exact SAT by
Limor Drori and David Peleg, seem to contain some interesting algoritms
that shows that Exact Cover problems can be solved in a rather
There are some more techniques which point to efficient algorithms
for solving NP-complete problems. These are found in:
Yesterday, at 15:28:31 there was an earthquake of magnitude 1.5
(only very minor) at a depth of 5.8 km below the Katla vulcano, which was followed by some hours of increased
tremors. In the past weeks there have been many earthquakes
around the Eyjafjallajökull vulcano. Is this the first sign that
something is hapening below Katla? Or is this one of the normal
earthquakes that occur along the fault line such as there has been
many in the past weeks.
Map with earthquakes in the past 48 hours.
Today, yesterday's earthquake was reclassified as two earthquakes:
one 1.0 earthquake at a depth of 7.1 km at 63.695, -19.149 and
one 1.5 earthquake at a depth of 0.8 km at 63.668, -19.141.
This very interesting because the later earthquake occured above
the magna chamber.
Update April 30: Above the 'Katla' tremor page it now says: "Katla is not erupting
and there are no indications that Katla is about to erupt.
Information on this page is for the Eyjafjallajökull eruption."
This months interesting links
| March 2010
| May 2010
| Random memories