Probe Machine Based Computing Model for Maximum Clique Problem

I.   Introduction

Life is an extremely complicated organism. Organs, tissues, and systems within living things are closely interrelated and interacted on each other. At the same time, the surroundings of life are undergoing constant variations. Functions of every system are bound to be regulated in order to adapt to changes in the external surroundings, for example, the regulation of body temperature. The realization of this regulation relies on three regulatory mechanisms, nervous, humoral and auto-regulation, among which nervous regulation plays the leading role. In Ref.[1], a staggered grid scheme was proposed to reduce both the total memory requirement and the CPU time of generating the corrected near matrix in the FFT-based methods. Some numerical experiments were provided to demonstrate both the correctness and the efficiency of the proposed method. In Ref.[2], authors are concerned with a kind of iterative method for computing the Moore-Penrose inverse, which can be considered as a discrete-time form of recurrent neural networks. Numerical tests demonstrated the effectiveness of authors’ new acceleration algorithm. In Ref.[3], this paper according to the principle of PD-IPM, the UC model was pretreated by continuous relaxation, and the Newton correction equation was decoupled by fast decoupling technology. The experimental results show that the proposed algorithm can obtain better speedup for two different types of structured nonlinear programming. In Ref.[4], a micro-architecture definition of digital signal processing system suitable for motor vector control algorithm was designed, including its instruction set definition, memory model and interaction mode with the main CPU. In Ref.[5], aiming at the problems of high complexity and large amount of calculation of convolution operation in convolutional neural network and the delay and power consumption limitation of algorithm calculation on CPU and GPU, a reconfigurable neural network acceleration system with high throughput and low power consumption based on ZYNQ was designed from the perspective of improving the calculation speed and reducing power consumption of existing hardware platforms.

The building blocks of structure and function of nervous system are neurons. A neuron consists of a cell body, dendrites, and an axon. Dendrites are thin structures that arise from the cell body. An axon is a special cellular extension that arises from the cell body as well. When axon extended from cell body for a distance and coated in myelin, it often called nerve fiber. The function of the dendrites is to accept the nerve impulses transmitted from other neurons, and conduct the impulse to the cell body. The main function of the nerve fiber is the conduction of nerve impulse.

The connection between neurons via synapse forms neural networks. A synapse is a structure that permits a neuron to conduct nerve impulse to another neuron along nerve fiber. Synapse is essential to neuronal function: neurons are cells that are specialized to conduct nerve impulse to another neuron, and synapse is the mean by which they do so. Researches have shown that nearly 100 billion neurons in human brain are almost functionally ready prior to everyone’s birth, but the connections between neurons are relatively sparse. A newborn baby fails to think, he will only establish connections between neurons as result of external stimuli. Any external stimulus, as long as it is new, will promote the growth of dendrites and nerve fibers of certain neurons in the brain, and connection with other neurons to form a new network. When the same stimulus occurs again, the established network is active again. During the course of human life, new networks are unceasingly produced while old ones gradually shrinked and disappeared.

We now analyze the formation of a neural network, from the computing perspective. Neurons can be seen as data, synapses can be seen as a kind of operators in the computing. Under the action of operators, data are operated. Therefore, individual neurons are connected. Neural network is thus formed as result of the computing. We call the operator the connective operator. In Ref.[6], it presented an efficient GPU-based parallel tabu search algorithm (GPTS) for HW/SW partitioning. A single GPU kernel of compacting neighborhood was proposed to reduce the amount of GPU global memory accesses theoretically. A kernel fusion strategy was further proposed to reduce the amount of GPU global memory accesses of GPTS. In Ref.[7], author presented and evaluated a model of vector parallel ACO for multi-core SIMD CPU architecture. The proposed algorithm was tested on standard TSP instances ranging from 198 to 4,461 cities and showed a speedup factor of 57.8x compared to the single-threaded CPU counterpart. In Ref.[8], the authors exploited the parallel processing power of vector instructions on a CPU and made it collaboratively function with the on-chip GPU. The experimental results demonstrated that authors can achieve 146 GFLOP/s at best using a quad-core CPU and the performance is 2.5 to 4.8 times faster than that of the single-GPU version of the Open CV library. In Ref.[9], this article presented ideas to optimize existing GPU-based ACO algorithms for the TPS. Authors extended previous GPU-based ACO algorithms in two aspects: problem scale and computational efficiency. To solve larger problems, authors presented and evaluated two kernel strategies. To fully exploit GPU computing power, authors propose a new algorithm in the tour-construction stage.

Does the connective operator exist elsewhere? We think that the hybridization probe, which is commonly used in molecular biology, is another type of connective operator. In molecular biology, hybridization probes are variable length of deoxyribonucleic acids or ribonucleic acids labeled with radioactive or fluorescent dyes, which are used to detect the presence of nucleic acid sequences that are complementary to the probe sequences in the sample. When performing detection, in the presence of target sequences in the sample, the probes firstly hybridize with target sequences according to Watson-Crick complementary pairing rule to form double-stranded sequences. Then probes that hybridized are separated from the sample. Finally, determine the presence or absence of target sequence according to the labeled type of probe, for example, autoradiograph, fluorescence microscopy, etc. If the probe is designed as complement of two target deoxyribonucleic acids, in the presence of probe, two deoxyribonucleic acids both hybridize with their complements of the probe. Therefore, two deoxyribonucleic acids are connected by means of probe. Moreover, the concept of probe occurs in a variety of fields, computer science, electronics, information security, archeology, and so on. For example, light circuit board test probe is used to test circuit board or detect short circuits.

So far, we have introduced the concepts of data and probe in the PM, and their biological inspirations originated from neural network. Apparently, the concept of data in PM originated from neuron, whereas the probe in PM was the realization of the connective operator. Now, we presented the formal definition of PM as the following nine-tuple:

where each element corresponded to data library ($X$), probe library ($Y$), data controller (${\sigma _1}$), probe controller (${\sigma _2}$), probe operation ($\tau$), computing platform ($\lambda$), detector ($\eta$), true solution storage ($Q$), and residue collector ($C$), respectively. Data controller and probe controller are abstracts for controllers that are able to take data and probes from data library and probe library, place them into computing platform. Probe operation is the abstract for a process of executing many basic probe operations simultaneously. Computing platform is the abstract for an environment that is designated for performing probe operations. It can assist probes to find target data fibers rapidly and then perform (basic) probe operations. Detector is the abstract for a tool or method that is able to detect the solution from all generated solutions and outputs them correctly. True solution storage is the abstract for the device that stores true solution. Residue collector is the abstract for the device that collects non-solutions and decomposes them back into the form of data, and then returns these data to data sub-libraries.

We next presented schematic diagram of PM in the following Fig.1.

Figure  1.  Schematic diagram of PM

DownLoad: Full-Size Img PowerPoint

For a problem to be solved, the computing paradigm of PM can be briefly summarized into the following steps:

1) Encode the given problem into data fibers, fabricate data, and construct data library;

2) Devise probes and construct probe library;

3) Perform probe operation;

4) Detect products resulting from probe operation, output solution (solutions) to the given problem;

5) Collect solution (solutions) into true solution storage;

6) Collect non-solutions into residue collector.

For the past decades, substantial efforts have been devoted to exploring brand new computing model, for example, quantum turing machine (QTM)^[10-12], artificial neural network (ANN)^[13-15], and biologically inspired computing (BIC)^[16-20], etc. Research on TM gave birth to modern general purpose electronic computer, and left up-till-now unsolved problem in complexity theory whether P=NP. In 2000, the problem is named as the Millennium prize problems by Clay Mathematics Institute. In 2011, on the 100th anniversary of Turing’s birth, an open solicitation of new computational model that is superior to TM in terms of computing capacity was made world-widely. It is in this context that PM was proposed in 2016. For terminologies and notations not included in this paper, as well as the proof that TM is the special case of PM, readers may refer to Ref.[21] for detailed description.

In this paper, we presented a PM based computing model for maximum clique problem.

The rest of paper is organized as follows: Section II presented the formal definition of maximum clique problem, our model for solving a 6-vertex instance. Followed by, results and discussions were given in Section III. Conclusions and future work were presented in Section IV.

II.   Methodology

1   Maximum clique problem

The maximum clique problem is a classic combinatorial optimization problem in graph theory, and is one of the first problems shown to be NP-complete^{[22, 23]}. The concept of clique may trace its history to the research of social science. In 1949, Luce et al.^[24] transformed social network into an undirected graph. Each vertex of the graph represented an individual in the network, and each edge represented the acquaintance between individuals. They gave the definition of clique as the set of vertices of complete subgraph, the group of people who known each other. In 1957, Harary et al.^[25] proposed an exact algorithm enumerating all cliques of an arbitrary graph. To this day, the maximum clique problem has found extensive applications in different domains, computer vision, market analysis and coding theory, etc.

Let $G = (V,E)$ be a undirected graph, where $V = \{ 1,2, \ldots ,n\}$ is the vertex set of $G$, $E \subseteq V \times V$ is the edge set of $G$. The complement graph of $G = (V,E)$ is the graph $\overline G = (V,\overline E )$, where $V = \{ 1,2, \ldots ,n\}$，$\overline E = \{ (i,j)\left| {i,j} \right. \in V,i \ne j,(i,j) \notin E\}$. Let ${V'}$ be the proper subset of $V$, ${V'} \subset V$, the subgraph induced by ${V'}$, denoted as $G({V'})$, is the graph $G = ({V'},{E'})$, where ${E'} = \{ (i,j)\left| {i,j} \right. \in {V'},i \ne j,(i,j) \in E\}$. A graph $G = (V,$$E)$ is complete iff all distinct vertices are pairwise adjacent, i.e., $\forall i,j \in V,i \ne j,\left( {i,j} \right) \in E$. A clique $C$ is a subset of vertex set $V$, $C \subseteq V$, such that the subgraph induced by $C$, $G(C)$, is a complete graph. A clique ${C_{mal}}$ is maximal if it is not a subset of any other cliques, which means the clique ${C_{mal}}$ can not be extended by including one more adjacent vertex. The clique ${C_{\max }}$with maximum cardinality in the maximal clique is the maximum clique of the graph $G$. The clique number of $G$, denoted by $\omega (G)$, is the cardinality of ${C_{\max }}$, $\omega (G) =$$\left| {{C_{\max }}} \right|$. Fig.2 below presented an instance of maximum clique problem of a graph with 6 vertices and 11 edges. The maximum clique to be searched is ${C_{\max }} =$$\{ 3,4,5,6\}$, the clique number is $\omega (G) = 4$.

Figure  2.  An instance of maximum clique problem

DownLoad: Full-Size Img PowerPoint

The maximum clique problem is closely related to other problems in combinatorial optimization. The maximum clique, the maximum independent set and the minimum vertex cover problems are computationally equivalent to one another. Mathematically, the maximum clique problem is usually formulated as the following 0-1 programming subject to edge constraints of complement graph.

Decades of research into maximum clique problem has demonstrated that finding the maximum clique of the given graph is rather difficult. A variety of algorithms have been proposed so far. These algorithms can be briefly categorized into two classes: exact^[20-29] and heuristic algorithms^[30-35]. The drawback of exact algorithms is that the time complexity of the algorithms increases exponentially with the size of the problem. The drawback of heuristic algorithms is that the algorithms are not necessarily to find the optimal solution to the given problem.

Algorithms for maximum clique problem have been the subject of research in BIC, and results are fruitful. In 1997, Ouyang et al.^[36] reported solving maximum clique problem by means of molecular biology techniques. For a graph with $N$ vertices, each possible clique was represented by a $N$-digit binary number. A bit set to 1 represented a vertex in the clique, and 0 represented a vertex out of the clique. Each binary bit was associated with a unique position and value DNA sequences, denoted by ${P_i}$,${V_i}$, respectively. Restriction endonuclease recognition sequences were embedded into value sequence. They firstly generated ${2^N}$ DNA molecules of different types using parallel overlap assembly, which is the solution space of the given problem. Then, for each edge in the complement graph, since the pair of vertices that are adjacent in the complement graph should not be both members of a clique, enzymatic digest those molecules in the data pool representing both vertices are in the clique with restriction enzymes. When all edges in the complement graph are examined one by one, the remaining DNA molecules with shortest length corresponded to the maximum clique of the given graph. In 2000, Head et al.^[37] proposed an algorithm for solving maximal independent problem using plasmids. In 2008, Li et al.^[38] applied pruning strategy to DNA computing and gave an algorithm for maximum clique problem based on sticker model. In 2014, Zhou et al.^[39] proposed a computing model based on the self-assembly of tiles for solving maximum clique problem.

2   Computing model

In this section, we took Fig.2 as an example and presented our model for maximum clique problem. We started with the construction of data base.

1   The construction of data library

Let $G = (V,E)$ be an undirected graph, where $V = \{ 1,2, \ldots ,n\}$, $E \subseteq V \times V$. For a arbitrary vertex $i \in V$, denote the neighborhood set of vertex $i$ (the set of vertices that are adjacent to vertex $i$ in graph $G$) by ${N_i}$$(i = 1,2, \ldots ,n)$, where ${N_i} = \{ j\left| {i \ne j,(i,j) \in E\} } \right.$. The subgraph induced by ${N_i}$ is denoted by $G({N_i})$. For example, the neighborhood set of vertex $1$ in Fig.2 is ${N_1} = \{ 2,4,5\}$, the induced subgraph was presented in Fig.3.

Figure  3.  The subgraph induced by $G({N_1})$

DownLoad: Full-Size Img PowerPoint

According to the definition of maximal clique, the maximal clique ${C_{mal}}$ including vertex $i$ must be the proper subset of $\{ i\} \cup {N_i}$. For each set $\{ i\} \cup {N_i}$, we constructed a data sublibrary ${X_i}$$(i = 1,2, \ldots ,n)$. The data library $X = {X_1} \cup {X_2} \cup \ldots \cup {X_n}$ was thus constructed. Each data sublibrary ${X_i}$ contained vast copies of data. Each type of data in the data sublibrary ${X_i}$ represented a vertex in the set $\{ i\} \cup {N_i}$. Each type of data consisted of two parts: a data body and data fibers $x_i^j$ (recall the structure of neuron introduced in the Introduction). All data in data library have the unique type of the data body. Data differ from one another in the type of data fiber. For example, for vertex 1 in the given graph, the neighborhood set of vertex 1 is $\{ 2,4,5\}$. The set $\{ 1\} \cup {N_1}$ has four vertices $\{ 1,2,4,5\}$. We used $4$different types of data to represent each vertex in the set. Each type of data has $3$ different types of data fiber. Fig.4 presented the four types of data in data sublibrary ${X_1}$. The black solid circles in Fig.4 are the data bodies, curves attached to the data body are data fibers. From left to right, Fig.4.(a),(b),(c), and (d) are data representing vertices $1,2,4,5$ in $\{ 1\} \cup {N_1}$,respectively. Data fibers $x_i^{vj}(j = 1,2, \ldots ,6)$ positioned centrally is the encoding for vertex $i$. These data fibers were specially designed for detecting which vertex was in the maximum clique in detector $\eta$. Other data fibers are target fibers that are complement to specific types of probe. There are a total of 12 different types of data fiber, 4 different types of data in data sublibrary ${X_1}$.

Figure  4.  Four types of data in the data sublibrary ${X_1}$

DownLoad: Full-Size Img PowerPoint

For convenience, we listed and separated data fibers by comma in the superscript, and denoted each data in data sublibrary ${X_i}$ by $x_i^{j,k,l}$. The data $x_i^{j,k,l}$ had three types of data fiber: $x_i^j$,$x_i^k$, and $x_i^l$. The data sublibrary ${X_1}$ was constructed and listed as follows:

Likewise, based on the set $\{ i\} \cup {N_i}$$(i = 2, \ldots ,n)$, we successively constructed data sub-libraries ${X_i}$$(i = 2,3, \ldots ,$$n)$ as follows:

There are a total of $56 + 6 = 72$ different types of data fiber, $1$ type of data body, and $28$ different types of data in the data library $X$. Therefore, the construction of data library $X$ for the maximum clique problem completed. The constructed data library $X$ was presented as follows:

More generally, let the cardinality of ${N_i}$ be $l$, $\left| {{N_i}} \right| = l$. There are a total of $l + 1$ different types of data ${x_i}$, $3(l + 1)$ different types of data fiber in the data sublibrary ${X_i}$$(i = 1,2, \ldots ,n)$.

2   The construction of probe library

Next, we presented the construction of probe library $Y$ based on the constructed data library$X$. Probes were designed according to the induced graph. Specifically, probes in probe sublibrary ${Y_i}$ were used to search and generate all maximal clique including vertex $i$.

As previously described, the maximal cliques including vertex $1$ must be the proper subset of $\{ 1\} \cup {N_1}$. Now, the question is: which vertices are also in the maximal cliques in addition to vertex $1$? In order to find these vertices, we performed iteration or recursion over the induced graph $G({N_1})$. Denote the induced graph by $G({({N_1})_k})$, where $k \in {N_i}$. Repeat the recursion until the induced graph has not edges any more. In this way, all the maximal cliques including vertex $1$ were ultimately found. Fig.5 presented the searching of the maximal cliques including vertex $1$. The maximal cliques found were: $\{ 1,5,2\}$ and $\{ 1,5,4\}$.

Figure  5.  The searching of maximal cliques including vertex $１$

DownLoad: Full-Size Img PowerPoint

For the maximal clique $\{ 1,5,2\}$, $2$ types of probe were designed. For the first type of probe, we took the complement of data fiber $x_1^1$ of data $x_1^{0,V1,1}$ and the complement of data fiber $x_1^6$ of data $x_1^{6,V5,7}$ in data sublibrary ${X_1}$ as probe, denoted by $\overline {x_1^1x_1^6}$ (the bar on the top represents complement, subscript $1$ corresponds to data sublibrary ${X_1}$). In case of the presence of data pair $(x_1^{0,V1,1},x_1^{6,V5,7})$, probe $\overline {x_1^1x_1^6}$ searches target data fibers $x_1^1$ and $x_1^6$, bounds to their complements simultaneously, and connects target data fibers $x_1^1$ and $x_1^6$ together, leading to the connection of data pair $(x_1^{0,V1,1},x_1^{6,V5,7})$. We call this operation basic probe operation. The product containing 2 types of data and 1 type of probe as result of basic probe operation is called 2-aggregation. In particular, a data may be considered as 1-aggregation. Fig.6 presented schematic diagram of the basic probe operation and 2-aggregation as result of the basic probe operation. Denote the basic probe operation by $\overline {x_1^1x_1^6} (x_1^{0,V1,1},x_1^{6,V5,7}) = x_1^{0,V1,1} \cdot \overline {x_1^1x_1^6} \cdot x_1^{6,V5,7}$. For the second type of probe, we took the complement of data fiber $x_1^7$ of data $x_1^{6,V5,7}$ and the complement of data fiber $x_1^2$ of data $x_1^{2,V2,3}$ in data sublibrary ${X_1}$ as probe, denoted by $\overline {x_1^7x_1^2}$. In case of the presence of data pair $(x_1^{6,V5,7},x_1^{2,V2,3})$, probe $\overline {x_1^7x_1^2}$ searches target data fibers $x_1^7$ and $x_1^2$, bounds to their complements simultaneously, and connects target data fibers $x_1^7$ and $x_1^2$, leading to the connection of data pair $(x_1^{0,V1,1},x_1^{6,V5,7})$.

Figure  6.  Schematic diagram of the basic probe operation and 2-aggregation as result of the basic probe operation

DownLoad: Full-Size Img PowerPoint

Similarly, for the maximal clique $\{ 1,5,4\}$, $2$ types of probe, $\overline {x_1^1x_1^6}$ and $\overline {x_1^7x_1^4}$ were correspondingly designed. Since probe $\overline {x_1^1x_1^6}$ was already designed for the maximal clique $\{ 1,5,2\}$, and there do not exist other maximal cliques including vertex $1$ any more, the probe sublibrary ${Y_1}$ was constructed. There are a total of $3$ types of probe. In case of the presence of data $x_1^{0,V1,1},x_1^{2,V2,3},x_1^{4,V4,5}$,$x_1^{6,V5,7}$, probe $\overline {x_1^1x_1^6}$ , $\overline {x_1^7x_1^2}$, $\overline {x_1^7x_1^4}$ search target data fibers and basic probe operations are performed simultaneously. The two types of 3-aggregation to be generated as result of these probe operations were presented in Fig.7. The maximal cliques including vertex $1$ are thus to be generated. Data fibers $x_1^{V1}$, $x_1^{V5}$, $x_1^{V2}$, $x_1^{V4}$ that are not involved in probe operations encode which vertices are in the maximal cliques.

Figure  7.  Schematic diagram of two types of 3-aggregation, which represents the maximal clique $\{ 1,5,2\}$ (top) and $\{1,5,4\}$ (bottom), respectively

DownLoad: Full-Size Img PowerPoint

Therefore, in order to search and generate all maximal cliques that includes vertex $1$, $3$ types of probe were designed. Probe sublibrary ${Y_1}$ containing vast copies of probes was constructed, and we listed them as follows:

Similarly, for the maximal cliques including vertex $2$, the searching was presented in Fig.8. The maximal cliques found were $\{ 2,5,1\}$and $\{ 2,5,3\}$. Since the maximal clique $\{ 2,5,1\}$ had been found in the searching of the maximal clique including vertex $1$($\{ 1,5,2\}$), for the maximal clique, we did not design probe. For the maximal clique $\{ 2,5,3\}$, $2$ types of probe $\overline {x_2^9x_2^{14}}$ and $\overline {x_2^{15}x_2^{12}}$ were designed.

Figure  8.  The searching of the maximal cliques including vertex $2$

DownLoad: Full-Size Img PowerPoint

In case of the presence of data and probes, the 3-aggregation to be generated as result of probe operations was presented in Fig.9. The maximal cliques including vertex $2$ are thus to be generated.

Figure  9.  Schematic diagram of the 3-agrregation, which represents the maximal clique$\{ 2,5,3\}$

DownLoad: Full-Size Img PowerPoint

Therefore, in order to search and generate all maximal cliques that includes vertex $2$, $2$ types of probe were designed. Probe sublibrary ${Y_2}$ containing vast copies of probes was constructed, and we listed them as follows:

Similarly, for the maximal cliques including vertex $3$, the searching was presented in Fig.10. The maximal cliques found were $\{ 3,2,5\}$ and $\{ 3,4,5,6\}$. Since the maximal clique $\{ 3,2,5\}$ had been found in the searching of the maximal clique including vertex $2$($\{ 2,5,3\}$), for the maximal clique, we did not design probe. For the maximal clique $\{ 3,4,5,6\}$, $3$ types of probe $\overline {x_3^{17}x_3^{20}}$, $\overline {x_3^{21}x_3^{22}}$ , and $\overline {x_3^{23}x_3^{24}}$ were designed.

Figure  10.  The searching of the maximal cliques including vertex $3$

DownLoad: Full-Size Img PowerPoint

In case of the presence of data and probes, the 4-aggregation to be generated by probe operations was presented in Fig.11. The maximal cliques including vertex $3$ are thus to be generated.

Figure  11.  Schematic diagram of the 4-aggregation, which represents the maximal clique$\{ 3,4,5,6\}$

DownLoad: Full-Size Img PowerPoint

Therefore, in order to search and generate all maximal cliques that includes vertex $3$, $3$ types of probe were designed. Probe sublibrary ${Y_3}$ containing vast copies of probes was constructed, and we listed them as follows:

Since there do not exist other maximal cliques any more in the given graph, probe sub-libraries ${Y_i}$$(i = 4,5,6)$were constructed as follows:

There are a total of $8$ different types of probe in the probe library. Therefore, the construction of probe library $Y$ for the maximum clique problem completed. The constructed probe library $Y$ was presented as follows:

More generally, for arbitrary vertex $i$, what is the principle of designing probe so that all maximal clique including vertex $i$ can be generated? Let the induced graph $G({({({N_i})_j})_k})$ contains only a vertex $l$. Then the maximal clique including vertex $i$ to be searched is $\{ i,j,k,l\}$. There exist probe $\overline {x_i^bx_i^c}$ for data pair $(x_i^{a,Vi,b},$$x_i^{c,Vj,d})$, probe $\overline {x_i^dx_i^e}$ for data pair $(x_i^{c,Vj,d}, x_i^{e,Vk,f})$, and probe $\overline {x_i^fx_i^g}$ for data pair $(x_i^{e,Vk,f},x_i^{g,Vl,h})$, where $\{ a,b,$$\ldots , h \in Z\}$. In other cases, there does not exist probe.

3   Probe operation

Upon the constructed data library $X$ and probe library $Y$, the data controller ${\sigma _1}$ took appropriate amount of data $x_1^{0,V1,1}$, $x_1^{2,V2,3}$，$x_1^{4,V4,5}$, $x_1^{6,V5,7}$, $x_2^{8,V2,9}$, $x_2^{10,V1,11}$, $x_2^{12,V3,13}$, $x_2^{14,V5,15}$, $x_3^{16,V3,17}$, $x_3^{18,V2,19}$, $x_3^{20,V4,21}$, $x_3^{22,V5,23}$, $x_3^{24,V6,25}$, $x_4^{26,V4,27}$, $x_4^{28,V1,29}$, $x_4^{30,V3,31}$, $x_4^{32,V5,33}$, $x_4^{34,V6,35}$, $x_5^{36,V5,37}$, $x_5^{38,V1,39}$, $x_5^{40,V2,41}$, $x_5^{42,V3,43}$, $x_5^{44,V4,45}$, $x_5^{46,V6,47}$, $x_6^{48,V6,49}$, $x_6^{50,V3,51}$, $x_6^{52,V4,53}$, $x_6^{54,V5,55}$ from the data library $X$, and added them into the computing platform $\lambda$. Meanwhile, probe controller ${\sigma _2}$ took appropriate amount of probes $\overline {x_1^1x_1^6}$, $\overline {x_1^7x_1^2}$, $\overline {x_1^7x_1^4}$, $\overline {x_2^9x_2^{14}}$, $\overline {x_2^{15}x_2^{12}}$, $\overline {x_3^{17}x_3^{20}}$, $\overline {x_3^{21}x_3^{22}}$, $\overline {x_3^{23}x_3^{24}}$ from the probe library $Y$, and added them into $\lambda$. In the computing platform $\lambda$, the probe operation was performed. Probes searched their complement data fibers, basic probe operations were performed simultaneously. Data were connected by probes in parallel. We called this one step of probe operation. All maximal cliques $\{ 1,5,2\}$, $\{ 1,5,4\}$, $\{ 2,5,3\}$, $\{ 3,4,5,6\}$ were generated in parallel (see Figs.7,9,11). The 4-aggregation (see Fig.11) corresponded to the wanted clique number $\omega (G) = 4$. The detector $\eta$ detected the types of data fiber $x_i^{Vj}(j = 1,2, \ldots ,6)$of 4-aggregation, which reported that the wanted maximum clique was $\{ 3,4,5,6\}$. Therefore, the maximum clique in the given graph was ultimately obtained. The 4-aggregation corresponding to true solutions to the maximum clique problem were put into the true solution storage $Q$. Non-solutions were put into the residue collector $C$.

III.   Results and Discussions

Given undirected graph $G$ with $n$ vertices and $m$ edges, how many types of data, data fibers, data body, and probes are required in the proposed model for the maximum clique problem?

For convenience, let the cardinality of ${N_i}$ be $l$, $\left| {{N_i}} \right| = l$. As we discussed previously, there are a total of $l + 1$ different types of data ${x_i}$, $3(l + 1)$ different types of data fiber in the data sublibrary ${X_i}$$(i = 1,2, \ldots ,n)$. In worst case, the given graph is complete. In this case, the model requires $n$ different types of data to represent $n$ vertices in $\{ i\} \cup {N_i}$,$(i = 1,2, \ldots ,n)$. The number of types of data is ${n^2}$. Therefore, the type of data is bounded by ${O}({n^2})$.

As for data fibers, since each data has 3 types of data fiber, 2 types of data fiber are the targets for probe, the other 1 is the encoding for vertex in the given graph, the number of types of data fibers is $2{n^2} + n$. Therefore, the type of data fiber is bounded by ${O}({n^2})$.

The data bodies of all data are the same with another. Data differ only in the types of data fiber. Therefore, the number of types of data bodies is 1.

As for the type of probe, probes are designed to search and generate all maximal cliques, as we discussed previously. According the designing principle of probes, for a maximal clique containing $k$ vertices, $k - 1$ types of probe are required to generate $k$-aggregation as result of the probe operation. Whereas, there are $k(k - 1)/2$ edges in the graph induced by $k$ vertices. Apparently, in this case, the number of types of probe is no more than the number of edges in the induced graph. It follows that, the number of types of probe in the probe library $Y$ is no more than the number of edges in the graph. Therefore, the type of probe is bound by ${O}({n^2})$ as well.

In short, the space complexity is ${O}({n^2})$.

Upon the constructed data library $X$ and probe library $Y$, in platform $\lambda$, the proposed model requires one step of probe computation to generate all maximal cliques.

The time complexity of the model is ${O}(1)$.

As the size of problem increases, the types of data and probes polynomially increase. More probes will involve in searching target data pairs and generating maximal cliques in parallel. This means the parallelism of the proposed model increases dramatically with problem size. We think it marks a giant step in computing theory.

In 1945, Von Neumann employed semiconductors as components to realize Turing machine, giving birth to the modern general-purpose computer. The question naturally arises: how the proposed model is realized?

A possible realization technology was proposed in Ref.[17]. In the method, data fibers in the proposed model were realized by using single stranded DNA molecules, data bodies were realized by using nano-particles. Therefore, data were realized by attaching DNA segments to nano-particles. Probes were realized by using the complementary strands of two target single stranded DNA molecules. Currently, advances in biological technology have already made the attachment quite easy.

It should be pointed out that the following key issues must be carefully addressed in the realization of PM. The top priority is the solution detection technology. How is the cardinality of $n$-aggregation resulting from probe operation detected? How is the topology of $n$-aggregation that is isomorphic to the given graph detected? These are the most important issues that inevitably occur in the realization of PM. Once the problem is solved, PM immediately becomes into reality. Such works are currently under development. However, with the advances in biotechnology and detection technology, issues mentioned above are expected to be solved. We believe that PM is sure to become into reality.

IV.   Conclusions

In this paper, a computing model based on PM for maximum clique problem was proposed. Given undirected graph $G$ with $n$ vertices and $m$ edges, the space and time complexity of the proposed model were ${O}({n^2})$, ${O}(1)$, respectively.

PM is a mathematic model with massive parallelism. Our work demonstrate that, for NP-complete search problem, the searching capability of PM is superior to TM. Theoretically, one step of probe operation can search ${2^n}$ possibilities. More importantly, the searching capability of PM increases dramatically with the size of problem.

PM was inspired from neural network. The main difference lies in the connective operator: probe, in contrast to synapse. The appealing characteristic of PM is the massive parallelism. In essence, the parallelism of PM contributes to the connective operator: probe. That is the reason that the model is termed PM. Although PM has far from being realized these days, we believe the model is promising. With massive parallelism inherited in PM, we expect more complicated problem can be tackled in this brand-new model. That will be our future work. Now, the question is: Whether there exists an alternative technique of realizing the connective operator that is more superior to probe?