Abstract:
Adversarial SAT (AdSAT) is a generalization of the satisfiability (SAT) problem in which two players try to make a boolean formula true (resp. false) by controlling their respective sets of variables. AdSAT belongs to a higher complexity class in the polynomial hierarchy than SAT and therefore the nature of the critical region and the transition are not easily paralleled to those of SAT and worth of independent study. AdSAT also provides an upper bound for the transition threshold of the quantum satisfiability problem (QSAT). We present a complete algorithm for AdSAT, show that 2-AdSAT is in $\mathbf{P}$, and then study two stochastic algorithms (simulated annealing and its improved variant) and compare their performances in detail for 3-AdSAT. Varying the density of clauses $\alpha$ we find a sharp SAT-UNSAT transition at a critical value whose upper bound is $\alpha_c \lesssim 1.5$, thus providing a much stricter upper bound for the QSAT transition than those previously found.

Abstract:
In this paper the reason why entropy reduction (negentropy) can be used to measure the complexity of any computation was first elaborated both in the aspect of mathematics and informational physics. In the same time the equivalence of computation and information was clearly stated. Then the complexities of three specific problems: logical compare, sorting and SAT, were analyzed and measured. The result showed SAT was a problem with exponential complexity which naturally leads to the conclusion that no efficient algorithm exists to solve it. That's to say: NP!=P.

Abstract:
Ohya and Volovich have been proposed a new quantum computation model with chaos amplification to solve the SAT problem, which went beyond usual quantum algorithm. In this paper we study the complexity of the SAT algorithm by counting the steps of computation algorithm rigorously, which was mentioned in the paper [1,2,3,5,7]For this purpose, we refine the quantum gates treating the SAT problem step by step.

Abstract:
We introduce the NP-complete problem 3SAT_N and extend Tovey's results to a classification theorem for this problem. This theorem leads us to generalize the concept of truth assignments for SAT to aggressive truth assignments for 3SAT_N. We introduce the concept of a set compatible with the P and NP problem, and prove that all aggressive truth assignments are pseudo-algorithms. We combine algorithm, pseudo-algorithm and diagonalization method to study the complexity of 3SAT_N and the P versus NP problem. The main result is P != NP.

Abstract:
We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.

Abstract:
The (2+p)-Satisfiability (SAT) problem interpolates between different classes of complexity theory and is believed to be of basic interest in understanding the onset of typical case complexity in random combinatorics. In this paper, a tricritical point in the phase diagram of the random $2+p$-SAT problem is analytically computed using the replica approach and found to lie in the range $2/5 \le p_0 \le 0.416$. These bounds on $p_0$ are in agreement with previous numerical simulations and rigorous results.

Abstract:
Traditional approach to the study of society-nature interactions based on reductionism and linear causality is no longer fully capable of explaining complex dynamics of integrated socio-economic and natural systems. For this reason demands for complexity theory is growing. Understanding interactions between society and nature, human and their environment must come from the examination of how the two systems operate together, and not from examination of those systems themselves in isolation. Since our geographical community is not familiar enough with complexity theory, first part of article is devoted to outlining shift from reductionism to holism and complexity theory. In the second part, features of complex systems as it is human (society)-environment system are discussed. .

Abstract:
The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT ∈P SPARSE∩NP; (2) SAT ∈SRTD tt; (3) SAT ∈P tt bAPP ; (4)FP tt SAT . It is proved that some pairs of these conjectures implyP=NP, for example, if and SAT ∈p tt bAPP , or if SAT ∈SRTD tt and SAT ∈P tt bAPP , thenP=NP. This improves previous results in literature. This work is supported by the key project fund of China’s Ninth Five-Year Plan and the Science Foundation of Peking University. LIU Tian received the B.S. degree from University of Science and Technology of China in 1989, the M.S. degree in theory of computer science from Beijing Computer Institute in 1992, and the Ph.D. degree in computer software and theory. Peking University in 1999. His main research interests include computational complexity theory.

Abstract:
In this paper we study biased random K-SAT problems in which each logical variable is negated with probability $p$. This generalization provides us a crossover from easy to hard problems and would help us in a better understanding of the typical complexity of random K-SAT problems. The exact solution of 1-SAT case is given. The critical point of K-SAT problems and results of replica method are derived in the replica symmetry framework. It is found that in this approximation $\alpha_c \propto p^{-(K-1)}$ for $p\to 0$. Solving numerically the survey propagation equations for K=3 we find that for $p