Some Results Between Descriptive Complexity And Computational Complexity

In finite model theory, descriptive complexity theory as the link which con-nects computational complexity and logics of finite structures, through providing new proof methods and additional evidences makes the complexity classes looks "natural" but not tied to the specific abstract machines used to define them. As to some main complexity class, descriptive complexity uses logics to define them in a semantical way. For example, PH as a union of complexity class in the poly-nomial hierarchy, is precisely the class of languages expressible by statements of second-order logic.As its development progressed, a group of computer science theorists have proved that many diverse logics can capture different complexity classes. We call that these logics are equal to their corresponding complexity classes. Consequently, we can study some properties of computational complexity with the help of mathe-matical logic.While not all problems can be captured by a corresponding logic, these exam-ples which cannot be captured by logic are all important and oriented. In computa-tional complexity theorem, the very famous problem is P vs NP, and the results of inexpressibility of logic are possible to separate the complexity class. Thus, the in-expressibility of logics has been considered as a core topic. In this thesis, we expand the cope of problems involving inexpressibility of logics:In descriptive complexity, we know that existential second order (ESO) logic with a first order part that is universal Horn, as well as logics such as LFP+C IFP+C and C∞ωω can capture the class P when the structures are ordered.In Chapter2, we show that Linear Programming cannot be expressed in these logics at the structure level, at the same time, we extend the similar result to quadratic programming.In Chapter3, We also present the limits of expressibility of certain properties in logics L∞ωω, LFP, and PFP, by using Pebble Games, one of methodologies of mathematical logic. Another key focus of this thesis is given, in computer science, the NP-complete class plays one of the most useful roles in classifying the complexity of compu-tational problems. This is not only because any problem in NP can be reduced to an NP-complete problem, but also for that if any NP-complete problem can be solved by polynomial-time algorithm, then all NP problems will be solvable in polynomial-time. Although it is widely thought that NP-complete problems do not have polynomial-time algorithms, so far there is no proof for the conjecture. In this case, identifying the class of NP-Complete is very important.In Chapter4, we consider the computational problems from the descriptive complexity point of view, and show how to prove an NP problem is complete by logical reduction.In addition,we also show another role of logical reduction when it is operated between P problems, we found that the logical sentences of LFP+C, IFP+C and C∞ωω are insufficient to express P problem, this part has been shown in Chapter2.