In this paper we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence in NP.It is shown that among all NP-systems with model checking problem i...In this paper we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence in NP.It is shown that among all NP-systems with model checking problem in NP,the existentially quantified propositional logic（PF） is maximal with respect to poly-time model-equivalent reduction.However,PF seems not a maximal NP-system in general because there exits an NP-system with model checking problem DP-complete.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.60970040Ministry of Education,Key Research Projects of Philosophy and Social Science under Grant No.05JJD72040122the Sun Yat-Sen University Young Scholar Project
文摘In this paper we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence in NP.It is shown that among all NP-systems with model checking problem in NP,the existentially quantified propositional logic（PF） is maximal with respect to poly-time model-equivalent reduction.However,PF seems not a maximal NP-system in general because there exits an NP-system with model checking problem DP-complete.
