UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

A new reduction from 3SAT to n-partite graphs

Hulme, DJ; Hirsch, R; Buxton, BF; Lotto, RB; (2007) A new reduction from 3SAT to n-partite graphs. In: 2007 IEEE Symposium on Foundations of Computational Intelligence, Vols 1 and 2. (pp. 235 - 238). IEEE

Full text not available from this repository.


The Constraint Satisfaction Problem (CSP) is one of the most prominent problems in artificial intelligence, logic, theoretical computer science, engineering and many other areas in science and industry. One instance of a CSP, the satisfiability problem in propositional logic (SAT), has become increasingly popular and has illuminated important insights into our understanding of the fundamentals of computation. Though the concept of representing propositional formulae as n-partite graphs is certainly not novel, in this paper we introduce a new polynomial reduction from 3SAT to G(7)(n) graphs and demonstrate that this framework has advantages over the standard representation. More specifically, after presenting the reduction we show that many hard 3SAT instances represented in this framework can be solved using a basic path-consistency algorithm, and finally we discuss the potential advantages and implications of using such a representation.

Type: Proceedings paper
Title: A new reduction from 3SAT to n-partite graphs
Event: IEEE Symposium on Foundations of Computational Intelligence
Location: Honolulu, HI
Dates: 2007-04-01 - 2007-04-05
ISBN-13: 978-1-4244-0703-3
URI: http://discovery.ucl.ac.uk/id/eprint/165952
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item