DocumentCode
514983
Title
Notice of Retraction
Computing R-contraction for Propositional Logic is Hard
Author
He Li ; Lusong Li
Author_Institution
State Key Lab. of Software Dev. Environ., Beihang Univ., Beijing, China
Volume
2
fYear
2010
fDate
6-7 March 2010
Firstpage
260
Lastpage
263
Abstract
Notice of Retraction
After careful and considered review of the content of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE´s Publication Principles.
We hereby retract the content of this paper. Reasonable effort should be made to remove all past references to this paper.
The presenting author of this paper has the option to appeal this decision by contacting TPII@ieee.org.
R-calculus is a formal revision calculus system which can formally deduce R-contraction. R-contraction is the axiom system´s maximal subset that is consistent with the refutations by facts. In this paper, we prove that computing R-contraction for propositional logic is hard by two steps. Firstly, we prove that computing R-contraction is at least as hard as its decision problem. Secondly, we prove that the decision problem of computing R-contraction is NP-complete by presenting that the satisfiability problem, a known NP-complete problem, can polynomially reduce to it. So for this problem, we should direct our efforts at developing efficient heuristic algorithms or some other technology such as human-computer interaction.
After careful and considered review of the content of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE´s Publication Principles.
We hereby retract the content of this paper. Reasonable effort should be made to remove all past references to this paper.
The presenting author of this paper has the option to appeal this decision by contacting TPII@ieee.org.
R-calculus is a formal revision calculus system which can formally deduce R-contraction. R-contraction is the axiom system´s maximal subset that is consistent with the refutations by facts. In this paper, we prove that computing R-contraction for propositional logic is hard by two steps. Firstly, we prove that computing R-contraction is at least as hard as its decision problem. Secondly, we prove that the decision problem of computing R-contraction is NP-complete by presenting that the satisfiability problem, a known NP-complete problem, can polynomially reduce to it. So for this problem, we should direct our efforts at developing efficient heuristic algorithms or some other technology such as human-computer interaction.
Keywords
computability; computational complexity; process algebra; NP-complete; R-calculus; R-contraction; decision problem; formal revision calculus system; heuristic algorithm; maximal subset; propositional logic; satisfiability problem; Approximation algorithms; Calculus; Computer science; Computer science education; Heuristic algorithms; Logic; NP-complete problem; Polynomials; Programming; Software testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Education Technology and Computer Science (ETCS), 2010 Second International Workshop on
Conference_Location
Wuhan
Print_ISBN
978-1-4244-6388-6
Type
conf
DOI
10.1109/ETCS.2010.19
Filename
5460040
Link To Document