Reductions to Graph Isomorphism

We show that several reducibility notions coincide when applied to the Graph Isomorphism (GI) problem. In particular we show that if a set is many-one logspace reducible to GI, then it is in fact many-one \(\textsf{AC}^{0}\) reducible to GI. For the case of Turing reducibilities we show that for any k≥0 an \(\textsf{NC}^{k+1}\) reduction to GI can be transformed into an \(\textsf{AC}^{k}\) reduction to the same problem.     

图同构中的一类顶点细分方法

提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.     

关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。     

不确定属性图的子图同构及其判定算法

在分析了复杂网络(社会网络)结构的基础上,针对不确定属性图的特征,首先定义了不确定属性图的期望子图同构;由于其只用一个阈值作为限制条件,虽然方法简单,但计算量大,故接着给出了不确定属性图的α-β子图同构的定义,并对其语义进行了解释说明;第三,设计并实现了子图同构算法;最后,通过实验证明α-β子图同构优于期望子图同构,同时分析了不同阈值情况下α-β子图同构的变化规律.α-β子图同构算法的研究为不确定属性图的子图查询和社区挖掘工作奠定了基础.     

无向图的层次化谱分析同构判定算法

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

图同构问题的决策神经网络模型

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

基于结点间距离统计的无向无权图同构判别

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

Graph isomorphism is low for PP

We show that the graph isomorphism problem, is low for PP and for C=P, i.e., it does not provide a PP or C=P computation with any additional power when used as an oracle. Furthermore, we show that graph isomorphism belongs to the class LWPP (see Fenner, Fortnow, Kurtz [12]). A similar result holds for the (apparently more difficult) problem Group Factorization. The problem of determining whether a given graph has a nontrivial automorphism, Graph Automorphism, is shown to be in SPP, and is therefore low for PP, C=P, and Mod _k P,k2.     

The size of SPP

Derandomization techniques are used to show that at least one of the following holds regarding the size of the counting complexity class SPP:

1. μ_p(SPP)=0.

2. PH SPP.

In other words, SPP is small by being a negligible subset of exponential time or large by containing the entire polynomial-time hierarchy. This addresses an open problem about the complexity of the graph isomorphism problem: it is not weakly complete for exponential time unless PH is contained in SPP. It is also shown that the polynomial-time hierarchy is contained in SPP^NP if NP does not have p-measure 0.     

Curry—Howard同构理论：研究综述

一、引言理论计算机科学的发展吸取了大量数学和逻辑上的重要成果。逻辑是理论计算机科学十分重要的基础之一,而其中又以直觉主义逻辑对计算机科学的影响最为显著,它的思想比古典逻辑更加切合计算的观点。另一个值得一提的成果就是Alonzo Church在1936年提出的λ-演算系统,λ-演算所依据的是一种完全不同于逻辑的思想,它是计算机科学中函数式程序设计语言的理论基础。这是两种无论从语祛上还是从语义上去观察都区别甚大的形式系统,然而它们之间却存在着某种奇妙的对应关系,这就是本文所要介绍的Curry-Howard同构理论(Curry-Howard Isomorphism)。     

智能网中业务提供点的实现技术

介绍了智能网的概念及相应的结构,给出了一个业务提供点的设计和开发方案,并详细了其中一些关键技术,列出核心代码。     

领域驱动设计在SPP系统中的应用

研究了企业级应用系统开发的现状,明确了采用基于Web的多层架构体系(如J2EE)来进行企业级应用开发,分析了数据库驱动设计方法在Web应用开发中存在的缺点,引入领域驱动设计方法,介绍了领域驱动设计方法的开发模式,并运用到船舶性能预报(SPP)系统的设计中来,完成了SPP系统的分层架构和领域建模,解决了基于数据库驱动设计方法的Web应用开发存在的诸多问题,使系统获得了很好的扩展性和可维护性.     

Isomorphism and legal knowledge based systems

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.