首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in ModkP for each k  2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FPSPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FPSPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e.g., coset intersection) are in SPP, and thus in ModkP for each k  2.  相似文献   

2.
3.
4.
针对无向图同构的判定问题,一种层次化的基于谱分析的同构判定算法.比较两图的顶点数、边数以及度数序列对图进行预同构判定;然后对具有唯一Fiedler向量的图通过层次化的谱分析算法进行再次同构判定.与最具代表性的同构判定算法Nauty相比,随着判定图的规模增大,该算法对于规则网格图和固定度数图具有更高的同构判定效率.  相似文献   

5.
图同构问题的决策神经网络模型   总被引:1,自引:0,他引:1  
图的同构问题是研究两个图之间相互关系范畴.这对图表面上似乎不同,但本质上完全相同.由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用,因而,吸引了不少的学者从事这方面的研究.该文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型.该文在过去建立求解图的同构问题人工神经网络模型的基础上,拟应用人脑决策局域化的思想,提出了一种新的用于图的同构问题的人工神经网络模型.该模型中增加了一个自然的约束条件,加快了运算速度.  相似文献   

6.
按照同构图的定义判断两个图是否同构,最坏情况下其时间复杂度是O(N!),当结点数N比较大时,计算速度非常慢,针对该问题,提出一种通过统计结点间距离和按照距离分层,计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法,该算法可以给出两个图的结点间可能的对应关系.如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应,其时间复杂度仅为O(N4),否则,根据结点间可能的对应关系,避免遍历所有结点序号的交换,计算量可以成倍地下降.  相似文献   

7.
We continue the study of robust reductions initiated by Gavaldà and Balcázar. In particular, a 1991 paper of Gavaldà and Balcázar [7] claimed an optimal separation between the power of robust and nondeterministic strong reductions. Unfortunately, their proof is invalid. We re-establish their theorem. Generalizing robust reductions, we note that robustly strong reductions are built from two restrictions, robust underproductivity and robust overproductivity, both of which have been separately studied before in other contexts. By systematically analyzing the power of these reductions, we explore the extent to which each restriction weakens the power of reductions. We show that one of these reductions yields a new, strong form of the Karp—Lipton theorem. Received November 1997, and in final form March 1999.  相似文献   

8.
We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock and Pavan (ICALP (1), Lecture Notes in Computer Science, vol. 4051, pp. 465–476, Springer, 2006) and give a trade-off between the amount of advice needed for a reduction and its honesty on NEXP. We construct an oracle relative to which this trade-off is optimal. We show, in a more systematic study of non-uniform reductions, among other things that non-uniformity can be removed at the cost of more queries. In line with Post’s program for complexity theory (Buhrman and Torenvliet in Bulletin of the EATCS 85, pp. 41–51, 2005) we connect such ‘uniformization’ properties to the separation of complexity classes.  相似文献   

9.
10.
11.
Performing typical network tasks such as node scanning and path tracing can be difficult in large and dense graphs. To alleviate this problem we use eye‐tracking as an interactive input to detect tasks that users intend to perform and then produce unobtrusive visual changes that support these tasks. First, we introduce a novel fovea based filtering that dims out edges with endpoints far removed from a user's view focus. Second, we highlight edges that are being traced at any given moment or have been the focus of recent attention. Third, we track recently viewed nodes and increase the saliency of their neighborhoods. All visual responses are unobtrusive and easily ignored to avoid unintentional distraction and to account for the imprecise and low‐resolution nature of eye‐tracking. We also introduce a novel gaze‐correction approach that relies on knowledge about the network layout to reduce eye‐tracking error. Finally, we present results from a controlled user study showing that our methods led to a statistically significant accuracy improvement in one of two network tasks and that our gaze‐correction algorithm enables more accurate eye‐tracking interaction.  相似文献   

12.
Reductions between disjoint NP-Pairs   总被引:2,自引:0,他引:2  
Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A B, then all queries belong to C D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.  相似文献   

13.
14.
判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵。不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等。另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题。文章提出了一个简单有效的判断图同构的方法。首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构。最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应。  相似文献   

15.
Isomorphism and legal knowledge based systems   总被引:1,自引:1,他引:0  
This paper discusses some engineering considerations that should be taken into account when building a knowledge based system, and recommends isomorphism, the well defined correspondence of the knowledge base to the source texts, as a basic principle of system construction in the legal domain. Isomorphism, as it has been used in the field of legal knowledge based systems, is characterised and the benefits which stem from its use are described. Some objections to and limitations of the approach are discussed. The paper concludes with a case study giving a detailed example of the use of the isomorphic approach in a particular application.  相似文献   

16.
We analyze two bottom-up reduction algorithms over binary trees that represent replaceable data within a certain system, assuming the binary search tree (BST) probabilistic model. These reductions are based on idempotent and nilpotent operators, respectively. In both cases, the average size of the reduced tree, as well as the cost to obtain it, is asymptotically linear with respect to the size of the original tree. Additionally, the limiting distributions of the size of the trees obtained by means of these reductions satisfy a central limit law of Gaussian type.  相似文献   

17.
Many number theoretic problems such as integer factorization and the discrete logarithm problem have defied all attempts to classify their complexities. Thirteen such problems are considered, none of which is known either to have a deterministic polynomial time solution, or to be complete for any natural complexity class. Failing this, the next best goal is to determine which among these are the “easiest” and which are the “hardest” problems. Toward this end, this paper gives an overview of reductions among the problems. Two reductions are new: a deterministic polynomial time reduction from squarefreeness to Euler's function φ(n), and a probabilistic polynomial time reduction from order modulo a prime power to discrete logarithm modulo a prime power.  相似文献   

18.
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.  相似文献   

19.
In this note first we develop the notion of general fuzzy automata (GFA) to a new one which is called “BL-general fuzzy automata” and for simplicity, we write BL-GFA, instead of BL-general fuzzy automata. Then we focus on derivation, active state set, membership assignment, output mappings, and concept of belonging to an output label according to the entrance input strings \( X \, (X \in \Upsigma^{ * } ) \) for BL-general fuzzy automata. Therefore, we define the concepts of run map and behavior of BL-GFA. After that we present the morphism with threshold \( \tfrac{{\tau_{1} }}{{\tau_{2} }} \) between two BL-general fuzzy automata. Moreover we give some examples, to clarify these notions. Finally, we prove some theorems. In particular, we show that the isomorphic BL-general fuzzy automata have the same behavior.  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号