A large class of NP optimization problems called MNP are studied. It is shown that Rmax(2) is in this class and some problems which are not likely in Rmax(2) are in this class. A new kind of reductions, SL-reductions,...A large class of NP optimization problems called MNP are studied. It is shown that Rmax(2) is in this class and some problems which are not likely in Rmax(2) are in this class. A new kind of reductions, SL-reductions, is defined to preserve approximability and nonapprokimability, so it is a more general version of L-reductions and A-reductions. Then some complete problems of this class under SL-reductions are shown and it is proved that the max-clique problem is one of them. So all complete problems in this class are as difficult to approximate as the max-clique problem.展开更多
Hintikka thinks that second-order logic is not pure logic,and because of Godel's incompleteness theorems,he suggests that we should liberate ourselves from the mistaken idea that first-order logic is the foundatio...Hintikka thinks that second-order logic is not pure logic,and because of Godel's incompleteness theorems,he suggests that we should liberate ourselves from the mistaken idea that first-order logic is the foundational logic of mathematics.With this background he introduces his independence friendly logic(IFL).In this paper,I argue that approaches taking Hintikka’s IFL as a foundational logic of mathematics face serious challenges.First,the quantifiers in Hintikka’s IFL are not distinguishable from Linstrom's general quantifiers,which means that the quantifiers in IFL involve higher order entities.Second,if we take Wright’s interpretation of quantifiers or if we take Hale’s criterion for the identity of concepts,Quine’s thesis that second-order logic is set theory will be rejected.Third,Hintikka's definition of truth itself cannot be expressed in the extension of language of IFL.Since second-order logic can do what IFL does,the significance of IFL for the foundations of mathematics is weakened.展开更多
We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases.The tools we use come in the form of collapse results which...We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases.The tools we use come in the form of collapse results which are well established in the context of first-order logic.We show that the natural-active collapse with a condition and the activegeneric collapse carry over to the second-order logic for structures with o-minimality property and any signature in the complex value relations.The expressiveness results for more powerful logics including monadic second-order logic,monadic second-order logic with fix-point operators,and fragments of second-order logic are investigated in the paper.We discuss the data complexity for second-order logics over constraint databases.The main results are that the complexity upper bounds for three theories,MSO+(LIN),MSO+(POLY),and Inflationary DATALOGact^cv(SC,M)without powerset operator are∪iΣi^NC1,NCH=∪iΣi^NC,and AC^0/poly,respectively.We also consider the problem of query closure property in the context of embedded finite models and constraint databases with complex objects and the issue of how to determine safe constraint queries.展开更多
基金The National Natural Science Foundation of China grant !No.69373006 The National Hi-Tech Programme of China grant !No. 863-3
文摘A large class of NP optimization problems called MNP are studied. It is shown that Rmax(2) is in this class and some problems which are not likely in Rmax(2) are in this class. A new kind of reductions, SL-reductions, is defined to preserve approximability and nonapprokimability, so it is a more general version of L-reductions and A-reductions. Then some complete problems of this class under SL-reductions are shown and it is proved that the max-clique problem is one of them. So all complete problems in this class are as difficult to approximate as the max-clique problem.
基金Renmin University of China’s 2018 Fund for Building World-Class Universities(Disciplines).
文摘Hintikka thinks that second-order logic is not pure logic,and because of Godel's incompleteness theorems,he suggests that we should liberate ourselves from the mistaken idea that first-order logic is the foundational logic of mathematics.With this background he introduces his independence friendly logic(IFL).In this paper,I argue that approaches taking Hintikka’s IFL as a foundational logic of mathematics face serious challenges.First,the quantifiers in Hintikka’s IFL are not distinguishable from Linstrom's general quantifiers,which means that the quantifiers in IFL involve higher order entities.Second,if we take Wright’s interpretation of quantifiers or if we take Hale’s criterion for the identity of concepts,Quine’s thesis that second-order logic is set theory will be rejected.Third,Hintikka's definition of truth itself cannot be expressed in the extension of language of IFL.Since second-order logic can do what IFL does,the significance of IFL for the foundations of mathematics is weakened.
文摘We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases.The tools we use come in the form of collapse results which are well established in the context of first-order logic.We show that the natural-active collapse with a condition and the activegeneric collapse carry over to the second-order logic for structures with o-minimality property and any signature in the complex value relations.The expressiveness results for more powerful logics including monadic second-order logic,monadic second-order logic with fix-point operators,and fragments of second-order logic are investigated in the paper.We discuss the data complexity for second-order logics over constraint databases.The main results are that the complexity upper bounds for three theories,MSO+(LIN),MSO+(POLY),and Inflationary DATALOGact^cv(SC,M)without powerset operator are∪iΣi^NC1,NCH=∪iΣi^NC,and AC^0/poly,respectively.We also consider the problem of query closure property in the context of embedded finite models and constraint databases with complex objects and the issue of how to determine safe constraint queries.
