The Research On The Models Of Non-classical Computation And Their Computational Complexity

Computing power, that is the computability problem, is used to determine whethera computer is capable of computing. Computational efficiency, that is thecomputational complexity problem, is used to determine whether a computer cancomplete the computation of certain scale within a required period of time and space.Computing power and computing efficiency are mutually helpful and complementary.They constitute an important research area in Computer Science and Math. Thetheoretical model provides an important theoretical basis for program correctnessverification and system reliability design; Theory of Computation provides people away to understand the relationship between intelligence and calculation problems. Theimprovement in computing efficiency has always been an important subject in the fieldof computer algorithms design and analysis. It requires a uniform standard todetermine how to measure the computing efficiency of an algorithm and this standardis provided by the computing theory, which also generates a set of analytical theoriesrelated to this standard and provides a tool for accurately describing the computingefficiency.The non-classical computing theory was brought up as opposed to the classicalcomputing theory. The main difference is the change in computational model, that is touse the methods of random and fuzzy to process the classic Turing Machine in anon-deterministic way, to draw a conclusion related to computability andcomputational complexity, to provide a way for people to realize quantum computingand bio-computing, and to provide a theoretical proof for people to discover themystery of intelligence.Having discussing the conclusions of classical computing model and thecomputational complexity, this paper focuses on discussing the theoretical models andconclusions about randomized algorithms and fuzzy algorithms. When it comes to thefuzzy computing NP-complete, that is, λ-cut language acceptance problems, we use thereduction of the polynomial time as a proof; when it comes to its non-approximate, thatis, fuzzy language accepted, we use the reduction of introduction to the gap as a proof.The main characteristic of non-classic computing model is that it’s non-deterministic,of which the implementation depends on the parallel enumeration of all possiblesolutions. The newly developed "cloud computing", that is, large scale distributedparallel computing, can provide a physical basis for it, but computing model is a logic entity and needs to be expressed in terms of Math. That’s why we need to abstract thecalculation mode of "Cloud Computing". The research of computational complexity isrequired to provide a theoretical basis for accurate computational efficiency of the"cloud computing". SAT problem is an NP-complete problem and its complement is aco-NP problem, which seems to be more difficult than the SAT on the surface. The"Cloud Computing" for this problem can demonstrate the computational efficiency ofthe "cloud computing". This paper provides the algorithm applying to the cloudcomputing infrastructure, which can figure out the solution for SAT problem and itscomplementary problem within the polynomial time, and proves the computationalefficiency of the "cloud computing" in reality.