Finding Hard Instances of Satisfiability in Lukasiewicz Logics

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 May 2015 Spain Publisher:IEEEJournal:2015 IEEE International Symposium on Multiple-Valued Logic

Authors: Miquel Bofill; Felip Manyà; Amanda Vidal; Mateu Villaret;

doi: 10.1109/ismvl.2015.10

handle: 10261/159316

Finding Hard Instances of Satisfiability in Lukasiewicz Logics

- Summary
- Subjects
- Metrics

Abstract

One aspect that has been poorly studied in multiple-valued logics, and in particular in Lukasiewicz logics, is the generation of instances of varying difficulty for evaluating, comparing and improving satisfiability solvers. In this paper we present a new class of clausal forms, called Lukasiewicz L-clausal forms, motivate their usefulness, study their complexity, and report on an empirical investigation that shows an easy-hard-easy pattern and a phase transition phenomenon when testing the satisfiability of L-clausal forms. © 2015 IEEE.

Research partially supported by the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the Ministerio de Economía y Competividad projects AT CONSOLIDER CSD2007-0022, INGENIO 2010, CO-PRIVACY TIN2011-27076-C03-03, EDETRI TIN2012-39348-C02-01 and HeLo TIN2012-33042. The second author was supported by Mobility Grant PRX14/00195 of the Ministerío de Educación, Cultura y Deporte.

Peer Reviewed

Country

Spain

Related Organizations

Spanish National Research Council
Spain

Keywords

Easy-hard-easy pattern, Lukasiewicz logics, Benchmarks, Becnhmarks, Complexity, Satisfiability, Phase transition

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	9
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%