Title :
Polynomial Size Asymmetric Linear Model for SAT
Author_Institution :
An Alcatel-Lucent Co., Genesys Telecommun. Labs., Inc., Daly City, CA, USA
Abstract :
Article describes a polynomial time many-one reduction of SAT to a polynomial size asymmetric linear system, where asymmetry means that shape and location of the system´s polytope depend on order of clauses in CNF and on order of literals in the clauses.
Keywords :
computability; computational complexity; SAT; polynomial size asymmetric linear model; polynomial time many-one reduction; Cities and towns; Computer science; Laboratories; Linear systems; NP-complete problem; Polynomials; Search problems; Shape; Size measurement; Traveling salesman problems; Linear model; NP-complete; Reduction; SAT;
Conference_Titel :
World Congress on Engineering and Computer Science 2008, WCECS '08. Advances in Electrical and Electronics Engineering - IAENG Special Edition of the
Conference_Location :
San Francisco, CA
Print_ISBN :
978-1-4244-3545-6
DOI :
10.1109/WCECS.2008.16
