On polynomial time isomorphisms of some new complete sets

In this note we show that the recently discovered NP complete sets arising in number theory, the PTAPE complete sets arising in game theory, and EXTAPE complete sets arising from algebraic word problems are polynomial time isomorphic to the previously known complete sets in the corresponding classes.     

Relativized isomorphisms of NP-complete sets

In this paper, we present several results about collapsing and non-collapsing degrees ofNP-complete sets. The first, a relativized collapsing result, is interesting because it is the strongest known constructive approximation to a relativization of Berman and Hartmanis' 1977 conjecture that all _m ^P -complete sets forNP arep-isomorphic. In addition, the collapsing result explores new territory in oracle construction, particularly in combining overlapping and apparently incompatible coding and diagonalizing techniques. We also present non-collapsing results, which are notable for their technical simplicity, and which rely on no unproven assumptions such as one-way functions. The basic technique developed in these non-collapsing constructions is surprisingly robust, and can be combined with many different oracle constructions.     

Minimal complete sets of words

A characterization of minimal complete sets of words of a free monoid which are codes, is given.     

A note on complete sets and transitive closure

It is shown that there is a length-preserving relation that is NP-complete such that the transitive closure of the relation is PSPACE-complete.This research was supported in part by the National Science Foundation under Grant MCS80-11979.     

大型成套装备安全保障系统的研究

主要针对大型成套装备类行业的应用需求,研究物联网、云计算、云制造、云服务等关键技术,并在技术研究的基础上提出保障装备功能安全的设计方案,构建基于功能安全的在线控制装置及云服务平台。并介绍了这种新型安全保障系统在臭氧发生装备中的实际应用。     

On sets turing reducible to p-selective sets

We consider sets Turing reducible to p-selective sets under various resource bounds and a restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP/poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP cannot be reduced to the p-selective sets under 2 ^lin time reductions with at mostn ^k queries for anyfixed k ε N.     

A complete axiom system for rational sets with multiplicity

By extending the axiom system for equalities between rational (or recognizable) sets by Salomaa, we introduce an axiom system for equalities between rational K-subsets (sets recognized by finite state automata with multiplicity in semiring, K). The system is consistent and if K is a field it is complete; that is, all and only equalities between rational K-subsets are derivable in the system.     

Productive functions and isomorphisms

Joseph and Young [5] conjectured that there are non-p-isomorphic NP-complete sets if ak-creative set in NP exists which has no p-invertible p-productive function. We prove that this conjecture is true for the exponential-time (deterministic and nondeterministic) complexity classes E and NE. In particular, we prove that non-p-isomorphic E-complete sets exist if and only if there is a p-creative set in E which has no p-invertible p-productive function. Similar result holds for NE as well.This work was supported in part by NSF Grants CCR-8814339 and CCR-9108899.     

Observations on complete sets between linear time and polynomial time

There is a single set that is complete for a variety of nondeterministic time complexity classes with respect to related versions of m-reducibility. This observation immediately leads to transfer results for determinism versus nondeterminism solutions. Also, an upward transfer of collapses of certain oracle hierarchies, built analogously to the polynomial-time or the linear-time hierarchies, can be shown by means of uniformly constructed sets that are complete for related levels of all these hierarchies. A similar result holds for difference hierarchies over nondeterministic complexity classes. Finally, we give an oracle set relative to which the nondeterministic classes coincide with the deterministic ones, for several sets of time bounds, and we prove that the strictness of the tape-number hierarchy for deterministic linear-time Turing machines does not relativize.     

A complete characterization of reachable sets for constrained linear time-varying systems

We consider linear time-varying systems with linear constraints on both control and state variables. The reachable set is a convex polyhedron that we completely characterize in terms of its boundary hyperplanes.     

On operations of soft sets

Soft set theory, proposed by Molodtsov, has been regarded as an effective mathematical tool to deal with uncertainties. In this paper, first we prove that certain De Morgan’s law hold in soft set theory with respect to different operations on soft sets. Then, we discuss the basic properties of operations on soft sets such as intersection, extended intersection, restricted union and restricted difference. Moreover, we illustrate their interconnections between each other. Also we define the notion of restricted symmetric difference of soft sets and investigate its properties. The main purpose of this paper is to extend the theoretical aspect of operations on soft sets.     

On polynomial-time truth-table reducibility of intractable sets to P-selective sets

The existence of setsnot being _tt ^P -reducible to low sets is investigated for several complexity classes such as UP, NP, the polynomial-time hierarchy, PSPACE, and EXPTIME. The p-selective sets are mainly considered as a class of low sets. Such investigations were done in many earlier works, but almost all of these have dealt withpositive reductions in order to imply the strongest consequence such as P=NP under the assumption that all sets in NP are polynomial-time reducible to low sets. Currently, there seems to be some difficulty in obtaining the same strong results undernonpositive reducibilities. The purpose of this paper is to develop a useful technique to show for many complexity classes that if each set in the class is polynomial-time reducible to a p-selective set via anonpositive reduction, then the class is already contained in P. The following results are shown in this paper.(1) If each set in UP is _tt ^P -reducible to a p-selective set, then P=UP.(2) If each set in NP is _tt ^P -reducible to a p-selective set, then P=FewP and R=NP.(3) If each set in ₂ ^P is _tt ^P -reducible to a p-selective set, then P=NP.(4) If each set in PSPACE is _tt ^P -reducible to a p-selective set, then P=PSPACE.(5) There is a set in EXPTIME that is not _tt ^P -reducible to any p-selective set.It remains open whether P=NP follows from a weaker assumption that each set in NP is _tt ^P -reducible to a p-selective set.     

On symmetric differences of NP-hard sets with weakly P-selective sets

The symmetric differences of NP-hard sets with weakly-P-selective sets are investigated. We show that if there exist a weakly-P-selective set A and an NP-^P_m-hard set H such that H - AεP_btt(sparse) and A — HεP_m(sparse) then P = NP. So no NP-^P_m-hard set has sparse symmetric difference with any weakly-P-selective set unless P = NP. The proof of our main result is an interesting application of the tree prunning techniques (Fortune 1979; Mahaney 1982). In addition, we show that there exists a P-selective set which has exponentially dense symmetric difference with every set in P_btt(sparse).     

On isomorphisms and similarities between generalized Petersen networks and periodically regular chordal rings

Generalized Petersen (GP) networks and periodically regular chordal (PRC) rings have been proposed independently to ameliorate the high latency and extreme fragility of simple ring networks. In this paper, we note that certain GP networks are isomorphic to suitably constructed PRC rings, while other varieties correspond to PRC rings that closely approximate their topological and performance attributes. In the absence of equivalence and similarity proofs in the opposite direction, our results indicate that PRC rings may be preferable to GP networks in the sense of covering a broader family of networks and offering greater flexibility in cost-performance tradeoffs.     

ER isomorphisms and uniqueness conditions

Given a collection of entity types (database tables) there is usually more than one way to model their associations. Consequently, two data models may appear different while essentially they are the same. To simplify the task of comparing data models, necessary and sufficient conditions are defined for a collection of entity types to have a unique Entity Relationship Diagram (ERD). The sufficient conditions for uniqueness are translated into modeling constraints that can be easily used to build an Entity-Relationship model. It is shown that the constraints do not prevent the representation of information requirements except for rare types of involuted relationships that seldom appear in the real world. Additionally, sufficient conditions are established for two ERDs to be isomorphic. All of this is done under the assumption that relationships are degree 2 or less. The results are extended to models containing relationships of higher degree.     

On generalized fuzzy rough sets

In this paper, a class of generalized fuzzy rough sets based on two universes are studied. Some new set-valued mappings and fuzzy set-valued mappings are introduced to discuss properties of the known model, and a new model for fuzzy rough sets is proposed which provides a new selection of interval structure for uncertainty reasoning using rough set theory. Some properties of the new model are revealed. The new model seems to be more natural in the sense that fuzzy sets are approximated by fuzzy sets on the same universe.     

On complete one-way functions

Complete constructions play an important role in theoretical computer science. However, in cryptography complete constructions have so far been either absent or purely theoretical. In 2003, L.A. Levin presented the idea of a combinatorial complete one-way function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post correspondence problem. We also present the properties of a combinatorial problem that allow a complete one-way function to be based on this problem. The paper also gives an alternative proof of Levin’s result.     

On finding fundamental cut sets

In this paper a linear time algorithm is proposed for preprocessing the edges of a graph. After preprocessing (in linear time), the fundamental cut set of any tree edge can be determined in time proportional to the size of that cut set.