Let me first explain the background of this research.
Theoretical computer science started for better understanding of the nature of computation. Just as with any other mathematical science theory, such an understanding takes a model for performance analysis. The most standard model of computation for a traditional Von Neumann computer is no doubt Turing machines.
A Turing machine models a hard drive by a tape of any length and CPU by its tape reader with finite states in its memory and transition functions between the states. This mimics conventional computer algorithms pretty well – because it’s not hard to convert any given algorithm into a Turing machine. Due to the model’s simplicity, you could do some vigorous mathematical analyses on questions such as “what’s its running time?” or “how much memory does it use?”.
On the other hand, you cannot help some modeling overhead arising from that simplicity. For example, it practically takes just one step to retrieve some small information stored in a hard drive. On a Turing machine, you must travel to that location on the tape spending some substantial extra time, probably after you identify the storage location in the directory portion of the tape.
It’s common to ignore a polynomial overhead in computational analysis. Here “polynomial” means \( n^c \) where \( n \) is the number of used slots of the tape before running it (the input size of the Turing machine), and \(c>0 \) a given fixed constant independent of \( n\). We can say Turing machines are equivalent to algorithms if there is a Turing machine for any given algorithm to compute the same result with running time and used memory each \( < n^c \) times that of the algorithm.
We just acknowledge the equivalence because we are in search of a good mathematical definition of an algorithm and a Turing machine is its immediate answer. This is called the Church-Turing thesis. The P vs NP problem is defined on some special Turing machines, practically asking if there exists a polynomial-time algorithm for any in the group of computational problems known to persistently resist analyses of their essential minimum running times. This problem group is called the Class NPC and each included problem NP-complete (NP-completeness).
There is another mathematical object equivalent to a Turing machine, called Boolean circuit. Let me show an example taken from Paper 4 posted on the left.
This one is said to be a De Morgan circuit because there is no logical negation \( \neg \) in the internal layers (the top and 2nd layers). The negations have been all shifted down to the leaf level on the bottom by the De Morgan law, where the leaves mean the existence and non-existence of some edges; the circuit is defined on a graph of three vertices 1, 2, and 3, and edges between them.
It’s well-known De Morgan circuits are equivalent to Turing machines in the above sense ignoring polynomial overheads, so we can use them for mathematical analysis of an algorithm. Now we suddenly need to deal with a collection of sets of edges and/or non-edges attached to each internal node \( \wedge \) (logical AND) or \(\vee \) (logical OR).
In other words, it has become a matter of a family of sets where we could use combinatorial knowledge on objects such as sunflowers. I’ll continue this topic next time.
Links for mobile devices
- Index page
- Paper 1 Ver 1 (It has a major error that I am trying to fix now.)