[1] Cook S A. The complexity of theorem proving procedures. InProc. ACM STOC, May 1971, pp.151-158.[2] Aspvall B, Plass M F, Tarjan R E. A linear-time algorithmfor testing the truth of certain quantified boolean formulas.Inf. Process. Lett., 1979, 8(3): 121-123.[3] Valiant L G. The complexity of computing the permanent.Theoret. Comput. Sci., 1979, 8(2): 189-201.[4] Valiant L G. The complexity of enumeration and reliabilityproblems. SIAM J. Comput., 1979, 8(3): 410-421.[5] Arora S, Lund C, Motwani R, Sudan M, Szegedy M. Proofverification and the hardness of approximation problems. J.ACM, 1998, 45(3): 501-555.[6] Hastad J. Some optimal inapproximability results. J. ACM,2001, 48(4): 798-859.[7] Henschen L, Wos L. Unit refutations and Horn sets. J. ACM,1974, 21(4): 590-605.[8] Yamasaki S, Doshita S. The satisfiability problem for the classconsisting of Horn sentences and some non-Horn sentences inpropositional logic. Infor. Control, 1983, 59(1-3): 1-12.[9] Schaefer T J. The complexity of satisfiability problems. InProc. ACM STOC, May 1978, pp.216-226.[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): 245-254.[11] Tovey C A. A simplified NP-complete satisfiability problem.Discrete Appl. Math., 1984, 8(1): 85-89.[12] Kratochvìl J, Savick′y P, Tuza Z. One more occurrence of variablesmakes satisfiability jump from trivial to NP-complete.SIAM J. Comput., 1993, 22(1): 203-210.[13] Gebauer H, Szab′o T, Tardos G. The local lemma is tight forSAT. In Proc. the 22nd ACM-SIAM Symposium on DiscreteAlgorithms (SODA), Jan. 2011, pp.664-674.[14] Lichtenstein D. Planar formulae and their uses. SIAM J.Comput., 1982, 11(2): 329-343.[15] Monien B, Sudborough I H. Bandwidth constrained NPcompleteproblems. In Proc. ACM STOC, May 1981, pp.207-217.[16] Georgiou K, Papakonstantinou P A. Complexity and algorithmsfor well-structured k-SAT instances. In Proc. the 11thInternational Conference on Theory and Applications of SatisfiabilityTesting (SAT), May 2008, pp.105-118.[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): 844-846.[19] Borosh I, Flahive M, Treybig B. Small solution of linear Diophantineequations. Discrete Math., 1986, 58(3): 215-220.[20] Bradley G H. Algorithms for Hermite and Smith normal matricesand linear diophantine equations. Math. Comput.,1971, 25(116): 897-907. |