-
Geschrieben am 5.11.2008
This page collects links around papers that try to settle the "P versus NP" question (in either way).
-
Geschrieben am 25.2.2008
Wenn Informatiker über Topologier reden, dann kommt das heraus! Keine schlechte Idee.
Suppose I have some set X and a (possibly infinite) collection of machines. To each machine M is associated a subset of X, U. The idea is that given an element x of X, you can use the machine M to test to see if x is an element of U. The catch is that the machine can only reply “yes”, and that you don’t know how long to wait for the answer, only that if the answer is “yes”, the machine will eventually, after a finite time, give you an answer. If x isn’t in U, the machine sits there forever, neither saying “yes” nor “no”. We’ll call a set V “observable” if for every x in V, we can use a machine, or some combination of machines, to show (in a finite time of course) that x is in V. So all of the U’s associated to machines M are observable.
-
Geschrieben am 28.11.2007
-
Geschrieben am 20.11.2007
-
Geschrieben am 20.11.2007