loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
34th International Symposium on Multiple-Valued Logic (ISMVL'04)
The Interface between P and NP in Signed CNF Formulas
University of Toronto, Toronto, Canada
May 19-May 22
ISBN: 0-7695-2130-4
ASCII Text
x 
 
C. Ansótegui, R. Béjar, A. Cabiscol, F. Manyà, "The Interface between P and NP in Signed CNF Formulas," Multiple-Valued Logic, IEEE International Symposium on, pp. 251-256, 34th International Symposium on Multiple-Valued Logic (ISMVL'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/ISMVL.2004.1319950,
author = {C. Ansótegui and R. Béjar and A. Cabiscol and F. Manyà},
title = {The Interface between P and NP in Signed CNF Formulas},
journal ={Multiple-Valued Logic, IEEE International Symposium on},
volume = {0},
year = {2004},
issn = {0195-623X},
pages = {251-256},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISMVL.2004.1319950},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Multiple-Valued Logic, IEEE International Symposium on
TI - The Interface between P and NP in Signed CNF Formulas
SN - 0195-623X
SP251
EP256
A1 - C. Ansótegui,
A1 - R. Béjar,
A1 - A. Cabiscol,
A1 - F. Manyà,
PY - 2004
KW - null
VL - 0
JA - Multiple-Valued Logic, IEEE International Symposium on
ER -
 
C. Ansótegui, Universitat de Lleida
R. Béjar, Universitat de Lleida
A. Cabiscol, Universitat de Lleida
F. Manyà, Universitat de Lleida
We first define a new class of signed CNF formulas and prove that its satisfiability problem is NP-complete. We then study in detail the interface between P and NP in two many-valued satisfiability problems: Mono+pPartiallySigned-2SAT and Regular+pSigned-2SAT. We show that such problems smoothly interpolate between P and NP by mixing together a polynomial and a NP-complete problem, and identify phase transition behavior in each of these problems.
Citation:
C. Ansótegui, R. Béjar, A. Cabiscol, F. Manyà, "The Interface between P and NP in Signed CNF Formulas," ismvl, pp.251-256, 34th International Symposium on Multiple-Valued Logic (ISMVL'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.