【摘 要】
：
A regular (3, 4)-CNF formula F is a 3-CNF formula, where each variable occurs exactly four times in F.A regular (3, 4, u)-CNF formula F is a regular (3, 4)-CNF formula, where each variable occurs u ti
【机 构】
：
College of Computer Science and Technology,Guizhou University,Guiyang (550025),P.R.China;School of E
【出 处】
：
2015全国理论计算机科学学术年会
论文部分内容阅读
A regular (3, 4)-CNF formula F is a 3-CNF formula, where each variable occurs exactly four times in F.A regular (3, 4, u)-CNF formula F is a regular (3, 4)-CNF formula, where each variable occurs u times positively in F, u is a integer no more than four.The regular (3,4)-SAT problem is the satisfiability problem restricted to regular (3, 4)-CNF formulas.It is known that regular (3, 4)-SAT is NP-Complete.In this paper, we give a lower bound on MAX-SAT for regualr (3,4)-CNF formula, sat(F) ≥ 17/20m for a regular (3, 4, 3)-CNF formula F and sat(F) ≥3/4m for a regular (3, 4, 2)-CNF formula F, where sat(F) is the maximal number of clauses that can be satisfied by a truth assignment, m is the number of clauses of F.
其他文献
Document databases are becoming popular, but how to present complex document query to obtain useful information from the document remains an important topic to study.In this paper, we describe the des
The individual household electricity consumption is major part of the city in the electricity market.The accurate prediction of household power load is very important for power sector to reasonable de
Herd behavior is a phenomenon that often appears in the stock market.It is caused by the irrational imitation of investors and is expressed as major investors make similar investing decisions in a sho
In this paper, we consider the problem of scheduling jobs with release dates and rejection on a bounded single parallel batching machine.Our objective is to minimize the sum of total completion time o
Conditional probability neural network (CPNN) has special advantage in pattern classification problems.However, how to find the optimal parameters of the CPNN to achieve better performance is an extra
The air pollution in Lanzhou city has caused wide public concern over the recent years.Among the factors leading to air pollution in lanzhou city, high PM10 concentration is an important one.Thus, pre
In CFD simulations, the smaller the cell size is, the more accurate the result is.However, a smaller cell size in all simulation regions means much more cells which in turn increased the consumption o
In virtualized and dynamical cloud computing environment, all resources such as infrastructure, hardware,platform, software and data can be virtualized and partitioned into some kinds of resouces pool
This paper presents an integrated method for ligaturing simulation of blood vessel in Virtual Simulation Training System of Liver Surgery.The integrated method mainly includes four aspects: simulation
This paper explores the Deep Belief Networks (DBNs) in the application of high-speed train vibration signals processing.Firstly, a new method based on DBNs is proposed.The vibration signals are prepro