
›› 2012, Vol. 27 ›› Issue (4): 668677.doi: 10.1007/s1139001212539
• Special Section on Theoretical Computer Science • Previous Articles Next Articles
HongYu Liang (梁宏宇) and Jing He (何晶)
[1] Cook S A. The complexity of theorem proving procedures. InProc. ACM STOC, May 1971, pp.151158. [2] Aspvall B, Plass M F, Tarjan R E. A lineartime algorithmfor testing the truth of certain quantified boolean formulas.Inf. Process. Lett., 1979, 8(3): 121123. [3] Valiant L G. The complexity of computing the permanent.Theoret. Comput. Sci., 1979, 8(2): 189201. [4] Valiant L G. The complexity of enumeration and reliabilityproblems. SIAM J. Comput., 1979, 8(3): 410421. [5] Arora S, Lund C, Motwani R, Sudan M, Szegedy M. Proofverification and the hardness of approximation problems. J.ACM, 1998, 45(3): 501555. [6] Hastad J. Some optimal inapproximability results. J. ACM,2001, 48(4): 798859. [7] Henschen L, Wos L. Unit refutations and Horn sets. J. ACM,1974, 21(4): 590605. [8] Yamasaki S, Doshita S. The satisfiability problem for the classconsisting of Horn sentences and some nonHorn sentences inpropositional logic. Infor. Control, 1983, 59(13): 112. [9] Schaefer T J. The complexity of satisfiability problems. InProc. ACM STOC, May 1978, pp.216226. [10] Allender E, Bauland M, Immerman N, Schnoor H, Vollmer H.The complexity of satisfiability problems: Refining Schaefer’stheorem. J. Comput. System Sci., 2009, 75(4): 245254. [11] Tovey C A. A simplified NPcomplete satisfiability problem.Discrete Appl. Math., 1984, 8(1): 8589. [12] Kratochvìl J, Savick′y P, Tuza Z. One more occurrence of variablesmakes satisfiability jump from trivial to NPcomplete.SIAM J. Comput., 1993, 22(1): 203210. [13] Gebauer H, Szab′o T, Tardos G. The local lemma is tight forSAT. In Proc. the 22nd ACMSIAM Symposium on DiscreteAlgorithms (SODA), Jan. 2011, pp.664674. [14] Lichtenstein D. Planar formulae and their uses. SIAM J.Comput., 1982, 11(2): 329343. [15] Monien B, Sudborough I H. Bandwidth constrained NPcompleteproblems. In Proc. ACM STOC, May 1981, pp.207217. [16] Georgiou K, Papakonstantinou P A. Complexity and algorithmsfor wellstructured kSAT instances. In Proc. the 11thInternational Conference on Theory and Applications of SatisfiabilityTesting (SAT), May 2008, pp.105118. [17] Rosen K H. Elementary Number Theory and its Applications(5th Edition), Addison Wesley, 2004. [18] Borosh I, Flahive M, Rubin D, Treybig B. A sharp boundfor solutions of linear diophantine equations. P. Am. Math.Soc., 1989, 105(4): 844846. [19] Borosh I, Flahive M, Treybig B. Small solution of linear Diophantineequations. Discrete Math., 1986, 58(3): 215220. [20] Bradley G H. Algorithms for Hermite and Smith normal matricesand linear diophantine equations. Math. Comput.,1971, 25(116): 897907. 
No related articles found! 

