共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
A characterization of minimal complete sets of words of a free monoid which are codes, is given. 相似文献
4.
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. 相似文献
5.
6.
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. 相似文献
7.
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. 相似文献
8.
Jie Wang 《Theory of Computing Systems》1995,28(2):109-116
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. 相似文献
9.
Armin Hemmerling 《Information and Computation》2011,209(2):173-182
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. 相似文献
10.
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. 相似文献
11.
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. 相似文献
12.
Seinosuke Toda 《Theory of Computing Systems》1991,24(1):69-82
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
2
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. 相似文献
13.
Bin Fu
Hong-zhou Li
《Theoretical computer science》1993,120(2):279-291The 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-Pm-hard set H such that H - AεPbtt(sparse) and A — HεPm(sparse) then P = NP. So no NP-Pm-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 Pbtt(sparse). 相似文献
14.
15.
Behrooz Parhami 《Information Processing Letters》2008,107(6):246-251
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. 相似文献
16.
John L. Knapp 《Data & Knowledge Engineering》1998,26(3):271-290
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. 相似文献
17.
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. 相似文献
18.
19.
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. 相似文献
20.
Sanjeev Saxena 《Information Processing Letters》2010,110(4):168-170
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. 相似文献