Reductions on NP and P-selective sets

P-selective sets are used to distinguish polynomial time-bounded reducibilities on NP. In particular, we consider different kinds of “positive” reductions; these preserve membership in NP and are not a priori closed under complements. We show that the class of all sets which are both P-selective and have positive reductions to their complements is P. This is used to show that if DEXT ≠ NEXT, then there exists a set in NP?P that is not positive reducible to its complement. Various similar results are obtained. We also show that P is the class of all sets which are both p-selective and positive truth-table self-reducible. From this result, it follows that various naturally defined apparently intractible problems are not p-selective unless P = NP.     

On the reducibility of sets inside NP to sets with low information content

This paper studies for various natural problems in NP whether they can be reduced to sets with low information content, such as branches, P-selective sets, and membership comparable sets. The problems that are studied include the satisfiability problem, the graph automorphism problem, the undirected graph accessibility problem, the determinant function, and all logspace self-reducible languages. Some of these are complete for complexity classes within NP, but for others an exact complexity theoretic characterization is not known. Reducibility of these problems is studied in a general framework introduced in this paper: prover-verifier protocols with low-complexity provers. It is shown that all these natural problems indeed have such protocols. This fact is used to show, for certain reduction types, that these problems are not reducible to sets with low information content unless their complexity is much less than what it is currently believed to be. The general framework is also used to obtain a new characterization of the complexity class is the class of all logspace self-reducible sets in L^L-sel.     

NP-Creative sets: A new class of creative sets in NP

We obtain a new definition of creativeness for NP, called NP-creativeness. We show that all NP-creative sets are NP-complete and provide strong evidence that all known NP-complete sets are NP-creative. We also show that all NP-creative sets are complete under exponentially honest reductions and contain an infinite NP subset in their complement (in other words, they are not NP-simple). A preliminary version of this paper was presented at the Eleventh Conference on Foundation of Software Technology and Theoretical Computer Science, India.     

On sparse sets in NP–P

The main result of this note shows that there exists a sparse set in NP that is not in P if and only if EXPTIME≠NEXPTIME. Several other results are derived about the complexity of very sparse sets in NP–P and an interpretation of the meaning of these results is given in terms of the complexity of solving ‘individual instances’ of problems in NP–P.     

On lattice ordered soft sets

Certain type of linguistic terms such as satisfactory, good, very good and excellent have an order among them. In this paper we introduce a new concept of soft sets with some order among the parameters. Some properties of lattice ordered soft sets are given. Lattice ordered soft sets are very useful in particular type of decision making problems where some order exists among the elements of parameters set.     

Adaptive versus nonadaptive queries to NP and p-selective sets

We prove that P = NP follows if for some , the class of functions that are computable in polynomial time by nonadaptively accessing an oracle in NP is effectively included in PF^NP[k⌈log n⌉— 1], the class of functions that are computable in polynomial k⌈log n⌉— 1 queries to an oracle in NP.?We draw several observations and relationships between the following two properties of a complexity class : whether there exists a truthtable hard p-selective language for , and whether polynomially-many nonadaptive queries to can be answered by making O(log n)-many adaptive queries to (in symbols, whether ). Among these, we show that if there exists an NP-hard p-selective set under truth-table reductions, then . However, if , then these two properties are equivalent. Received: November 1, 1996.     

Some observations on NP real numbers and P-selective sets

We show that each standard left cut of a real number is a p-selective set. Classification results about NP real numbers and recursively enumerable real numbers follow from similar results about p-selective and semirecursive sets. In particular, it is proved that no left cut can be NP-hard unless the polynomial hierarchy collapses to ?₂^P. This result is surprising because it shows that the McLaughlin-Martin construction of a ?_tt-complete r.e. semirecursive set fails at the polynomial time complexity level.     

概念格与粗糙集的数据分析方法研究

概念格和粗糙集是数据挖掘中对数据进行分析与处理的两个有力工具,它们在数据分析方面有相似之处.通过运用概念格刻画粗糙集的一些概念与性质给二者建立了联系.指出了概念格每个结点都是粗糙集中一个等价类,并借鉴粗糙集的思想,提出了在概念格中进行概念近似的方法.同时使用概念格中的概念重新描述了粗糙集的上下近似,最后通过事例将粗糙集中改进的区分矩阵运用于概念格中的属性约简,从而减少了区别矩阵的存储空间,并同时减少了区别矩阵的计算量,真正从一定意义上结合了二者的优点.     

Revising the link between L-Chu correspondences and completely lattice L-ordered sets

Continuing our categorical study of L-fuzzy extensions of formal concept analysis, we provide a representation theorem for the category of L-Chu correspondences between L-formal contexts and prove that it is equivalent to the category of completely lattice L-ordered sets.     

Computing generating sets of lattice ideals and Markov bases of lattices

In this article, we present an algorithm for computing generating sets of lattice ideals or equivalently for computing Markov bases of lattices. Generating sets of lattice ideals and Markov bases of lattices are essentially equivalent concepts. In contrast to other existing methods, the algorithm in this article computes with projections of lattices. This algorithm clearly outperforms other algorithms in our computational experience. Two areas of application for generating sets of lattice ideals and Markov bases lattices are algebraic statistics and integer programming.     

基于概念格的组规则产生集的算法研究

数据挖掘中传统的关联规则生成算法产生的关联规则集合相当庞大,其中很多规则可由其它规则导出。使用闭项集可以减少规则的数目,而概念格节点间的泛化和例化关系非常适用于规则的提取。目前几种基于概念格的规则提取算法局限于得到准确支持度、信任度的无冗余规则。提出了一种在概念格上挖掘出能推导出所有满足最小支持度、信任度规则的规则产生集算法,文中称之为组规则产生集算法,减少了规则的规模。在此基础上进一步给出了组规则产生集的存储数据结构并用其导出一般规则产生集的算法。     

Vague soft sets and their properties

Soft set theory, proposed by Molodtsov, has been regarded as an effective mathematical tool to deal with uncertainty. However, it is difficult to be used to represent the vagueness of problem parameters. In this paper, we introduce the notion of vague soft set which is an extension to the soft set. The basic properties of vague soft sets are presented and discussed.     

Vague软集的一些代数性质

基于Vague集和软集现有理论以及Vague集思想与软集思想之间的联系,初步提出了Vague软集的狭义交、狭义并、相对补运算的概念,并在此基础上分别研究了这些运算的若干代数性质。     

Nest sets and relativized closure properties

A nest set is the language generated by a context-free grammar whose rules are $\text{A → aB}\text{a}\text{?}\text{C}$ or A → ? (where a, ā are paired terminal symbols, and A, B, C are nonterminal symbols). They can be seen as the one-dimensional expressions of the recognizable sets of binary trees. We study their closure properties under relativized operations with respect to the Dyck set, which is the maximum set in the class. The operations considered are relativized versions of AFL operations, quotient, direct product, shuffle product, and some others. As an application we prove various closure properties of generalized parenthesis languages.     

Generating combinatorial sets with given properties

Special classes of combinatorial sets called k-sets are analyzed. An algorithm for the generation of k-sets is proposed. It is based on a unified algorithm for generating base combinatorial sets. The possibilities of using it to generate various base sets are considered. The complexity of the algorithms is assessed. The results of computational experiments are analyzed.     

概念格上规则产生集的算法研究与应用

用传统的规则生成算法产生的关联规则集合相当庞大,其中很多规则可由其它规则导出。使用闭项集可以减少规则的数目,而概念格节点间的泛化和例化关系非常适用于规则的提取。目前几种基于概念格的规则提取算法局限于得到准确支持度、信任度的无冗余规则。提出了一种在概念格上挖掘出能推导出所有满足最小支持度、信任度规则的规则产生集算法,文中称之为组规则产生集算法,减少了规则的规模,提高了挖掘效率,进一步给出了组规则产生集的存储数据结构和根据应用需要用其导出单一后项规则的算法。     

Searching sets of properties with neural networks

In this paper we develop an algorithm in the framework of neural networks. Specifically we consider the problem of detecting a subset of elements of a set Ω which possess a given property.