• DocumentCode
    3297994
  • Title

    Polynomial Size Asymmetric Linear Model for SAT

  • Author

    Gubin, Sergey

  • Author_Institution
    An Alcatel-Lucent Co., Genesys Telecommun. Labs., Inc., Daly City, CA, USA
  • fYear
    2008
  • fDate
    22-24 Oct. 2008
  • Firstpage
    62
  • Lastpage
    66
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • 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
  • Type

    conf

  • DOI
    10.1109/WCECS.2008.16
  • Filename
    5233193
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3297994