On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

On MODkP Counting Degrees

For a prime k, the embeddability of finite lattices are discussed for various kind of the MOD_kP degrees of recursive sets. In particular, all finite lattices are embeddable into the MOD_kP Turing degrees, whereas the non distributive lattice M₃ is embeddable into the MOD₂P many-one degrees but N₅ is not.     

A jump inversion theorem for the enumeration jump

Abstract. We prove a jump inversion theorem for the enumeration jump and a minimal pair type theorem for the enumeration reducibilty. As an application some results of Selman, Case and Ash are obtained. Received: 15 May 1998     

Enumeration of All Possibly Optimal Vertices with Possible Optimality Degrees in Linear Programming Problems with a Possibilistic Objective Function

In this paper, we treat linear programming problems with fuzzy objective function coefficients. To such a problem, the possibly optimal solution set is defined as a fuzzy set. It is shown that any possibly optimal solution can be represented by a convex combination of possibly optimal vertices. A method to enumerate all possibly optimal vertices with their membership degrees is developed. It is shown that, given a possibly optimal extreme point with a higher membership degree, the membership degree of an adjacent extreme point is calculated by solving a linear programming problem and that all possibly optimal vertices are enumerated sequentially by tracing adjacent possibly optimal extreme points from a possibly optimal extreme point with the highest membership degree.     

Local Density of Kleene Degrees

Concerning Post's problem for Kleene degrees and its relativization, Hrbacek showed in [1] and [2] that if V = L, then Kleene degrees of coanalytic sets are dense, and then for all K ?^ωω, there are N₁ sets which are Kleene semirecursive in K and not Kleene recursive in each other and K. But the density of Kleene semirecursive in K Kleene degrees is not obtained from these theorems. In this note, we extend these theorems by showing that if V = L, then for all K ? ^ωω, Kleene semirecursive in K Kleene degrees are dense above K.     

一类RNA二级结构的计数

多核苷酸的二级结构可视为一类顶点标号平面图，通常通过枚举每类RNA二级结构图的各种子图来计算其递推公式。本文作者给出了限制端环长度的RNA二级结构的递推公式，并运用隐式估计法计算它的渐近值。     

Enumeration of quarter-turn-symmetric alternating-sign matrices of odd order

Kuperberg showed that the partition function of the square-ice model related to quarter-turn-symmetric alternating-sign matrices of even order is the product of two similar factors. We propose a square-ice model whose states are in bijection with the quarter-turn-symmetric alternating-sign matrices of odd order and show that the partition function of this model can be written similarly. In particular, this allows proving Robbins’s conjectures related to the enumeration of quarter-turn-symmetric alternating-sign matrices. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 149, No. 3, pp. 395–408, December, 2006.     

Gray Code Enumeration of Plane Straight-Line Graphs

We develop Gray code enumeration schemes for geometric straight-line graphs in the plane. The considered graph classes include plane graphs, connected plane graphs, and plane spanning trees. Previous results were restricted to the case where the underlying vertex set is in convex position. Research supported by the FWF Joint Research Project Industrial Geometry S9205-N12 and Projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2005SGR00692.     

Enumeration of matchings in families of self-similar graphs

The number of matchings of a graph G is an important graph parameter in various contexts, notably in statistical physics (dimer-monomer model). Following recent research on graph parameters of this type in connection with self-similar, fractal-like graphs, we study the asymptotic behavior of the number of matchings in families of self-similar graphs that are constructed by a very general replacement procedure. Under certain conditions on the geometry of the graphs, we are able to prove that the number of matchings generally follows a doubly exponential growth. The proof depends on an independence theorem for the number of matchings that has been used earlier to treat the special case of Sierpiński graphs. We also further extend the technique to the matching-generating polynomial (equivalent to the partition function for the dimer-monomer model) and provide a variety of examples.     

克莱茵瓶上奇异地图的色数

A map is singular if each edge is on the same face on a surface (i.e., it has only one face on a surface). In this paper we present the chromatic enumeration for rooted singular maps on the Klein bottle.     

Degrees of difficulty of generalized r.e. separating classes

Important examples of classes of functions are the classes of sets (elements of ^ω 2) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions f ∈ ^ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let denote the Medvedev degrees of those such that no m + 1 sets among A ₀,...,A _k-1 have a nonempty intersection. It is shown that each is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions is the greatest element of . If 2 ≤ l < k, then 0 _M is the only degree in which is below a member of . Each is densely ordered and has the splitting property and the same holds for the lattice it generates. The elements of are exactly the joins of elements of for . Supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

Enumeration of point-determining graphs

Point-determining graphs are graphs in which no two vertices have the same neighborhoods, co-point-determining graphs are those whose complements are point-determining, and bi-point-determining graphs are those both point-determining and co-point-determining. Bicolored point-determining graphs are point-determining graphs whose vertices are properly colored with white and black. We use the combinatorial theory of species to enumerate these graphs as well as the connected cases.     

Enumeration of Unlabelled Mating Graphs

The problem of enumeration of unlabelled mating graphs is solved by constructing a bijection between the class of unlabelled mating graphs and the class of unlabelled graphs without endpoints.     

函数图及函数有向图计数式的组合证明

本文给出了函数有向图计数式的一个简短证明     

区间数相似度研究

对区间数相似性问题进行了探讨.定义了区间数相似度的概念,给出了度量区间数相似度的一个简洁公式,详细研究了它的一些优良性质,如:自反性、对称性和传递性等,并且研究了区间数相似度公式与区间数排序的可能度公式之间的关系,从而为区间数的实际应用奠定了理论基础.     

Infimum Properties Differ in the Weak Truth-table Degrees and the Turing Degrees

Abstract We prove that there are non-recursive r.e. sets A and C with A < _T C such that for every set . Both authors are supported by “863” and the National Science Foundation of China