DPBD——设计一类强NP-Complete问题近似算法的有效方法

本文针对一类强NP-Complete问题近似算法的设计问题,提出一种通用的设计策略DPBD,它通过一局部近似算法而获得一全局近似算法,并保证精度在一定范围内.最后,本文将DPBD应用于一著名的NP难度问题:平面Covering问题,对方法的有效性给予了证实.

On the completeness of eigen and root vector systems for fourth-order operator matrices and their applications

In this paper, we consider the eigenvalue problem of a class of fourth-order operator matrices appearing in mechan- ics, including the geometric multiplicity, algebraic index, and algebraic multiplicity of the eigenvalue, the symplectic orthogonality, and completeness of eigen and root vector systems. The obtained results are applied to the plate bending problem.

TOEPLITZ AND POSITIVE SEMIDEFINITE COMPLETION PROBLEM FOR CYCLE GRAPH

We present a sufficient and necessary condition for a so-called Cnk pattern to have positive semidefnite (PSD) completion. Since the graph of the Cnk pattern is composed by some simple cycles, our results extend those given in [1] for a simple cycle.We also derive some results for a partial Toeplitz PSD matrix specifying the Cnk pattern to have PSD completion and Toeplitz PSD completion.

A Finite-Dimensional Completely Integrable System Associated with Boussinesq Hierarchy

In this paper, a new completely integrable system related to the complex spectral problem -φ xx＋（i/4）wpx＋（i/4）（wp）x＋（1/4）vφ=iλφxand the constrained flows of the Boussinesq equations axe generated. According to the viewpoint of Hamiltonian mechanics, the Euler-Lagrange equations and the Legendre transformations, a reasonable Jacobi-Ostrogradsky coordinate system is obtained. Moreover, by means of the constrained conditions between the potentiaJ u, v and the eigenfunction φ, the involutive representations of the solutions for the Boussinesq equation hieraxchy axe given.

Nonlinear Electrical Impedance Tomography Method Using a Complete Electrode Model for the Characterization of Heterogeneous Domains

This paper presents an electrical impedance tomography(EIT)method using a partial-differential-equationconstrained optimization approach.The forward problem in the inversion framework is described by a complete electrodemodel(CEM),which seeks the electric potential within the domain and at surface electrodes considering the contact impedance between them.The finite element solution of the electric potential has been validated using a commercial code.The inverse medium problem for reconstructing the unknown electrical conductivity profile is formulated as an optimization problem constrained by the CEM.The method seeks the optimal solution of the domain’s electrical conductivity to minimize a Lagrangian functional consisting of a least-squares objective functional and a regularization term.Enforcing the stationarity of the Lagrangian leads to state,adjoint,and control problems,which constitute the Karush-Kuhn-Tucker(KKT)first-order optimality conditions.Subsequently,the electrical conductivity profile of the domain is iteratively updated by solving the KKT conditions in the reduced space of the control variable.Numerical results show that the relative error of the measured and calculated electric potentials after the inversion is less than 1%,demonstrating the successful reconstruction of heterogeneous electrical conductivity profiles using the proposed EIT method.This method thus represents an application framework for nondestructive evaluation of structures and geotechnical site characterization.

The Totally Non-positive Matrix Completion Problem

In this paper, the totally non-positive matrix is introduced. The totally non-positive completion asks which partial totally non-positive matrices have a completion to a totally non-positive matrix. This problem has. in general, a negative answer. Therefore, our question is for what kind of labeled graphs G each partial totally non-positive matrix whose associated graph is G has a totally non-positive completion? If G is not a monotonically labeled graph or monotonically labeled cycle, we give necessary and sufficient conditions that guarantee the existence of the desired completion.

Nonlocal controllability for semilinear problems in Banach spaces

If A： D（A） X→X is a densely defined and closed linear operator, which generates a linear semigroup S （t） in Banach space X. The nonlocal control/ability for the following nonlocal semilinear problems： u＇ （t） = Au （t） ＋ Bx（ t） ＋ f（ t, u（t） ）, 0≤t ≤ T with nonlocal initial condition u（0） = u0 ＋ g（u） is discussed in Banach space X. The results show that if semigroup S（t） is strongly continuous, the functionsf and g are compact and the control B is bounded, then it is nonlocally controllable. The nonlocal controllability for the above nonlocal problem is also studied when B and W are unbounded and the semigroup S（t） is compact or strongly continuous. For illustration, a partial differential equation is worked out.

Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem

As a typical representative of the NP-complete problem, the traveling salesman problem(TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization(DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt(C2-opt) algorithm to enhance the local search ability.Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization(PDLSO) algorithm is proposed.The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time.

ON SPECTRAL PROBLEM FOR VISCOUS SHEAR FLOWS

An important aspect of the Orr Sommerfeld problem, which governs the linear stability of parallel shear flows, is concerned with the study of the temporal and spatial spectra for large but finite values of the Reynolds number R . By using only outer (WKB) approximations which are valid in the "complete" sense, we are able to derive approximations to the eigenvalue relation for channel flows, pipe flow, and boundary layer flows which are all remarkably simple and which have a relative error of order ( αR) -1/2 . In this paper, we discuss briefly the basic ideas involved in the derivation of these approximations for boundary layer flows. We then present some results to illustrate the effectiveness of these new approximations. For example, we are even able to compute eigenvalues which lie arbitrarily close to the continuous spectra where all previous numerical treatments have failed.

Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP

In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for it with a polynomial time of biquadrate, which greatly reduces the computational complexity. Since this problem is also NP-complete, as a corollary, P = NP is proved to be true. It indicates the crack of the well-known open problem named “P versus NP”.

EXISTENCE THEOREMS OF SOLUTIONS FOR TWO－POINT BOUNDARY VALUE PROBLEM OF SECOND ORDER ORDINARY DIFFERENTIAL EQUATIONS IN BANACH SPACES

By using partial order method. some existing theorems of solutions for two-point bouniary value problem of second order ordinary differenlial equations in Banach spaces are given.

Solving the independent set problem by sticker based DNA computers

In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide” and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.

Applying Surface-Based DNA Computing for Solving the Dominating Set Problem

The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.

Solving a Traveling Salesman Problem with a Flower Structure

This works aims to give an answer to the problem P = NP? The result is positive with the criteria that solve the Traveling Salesman Problem in polynomial cost of the input size and a proof is given. This problem gets a solution because a polyhedron, with a cut flower looking, is introduced instead of graph (e.g. tree).

An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2 n/4 ) 1-ε processors, 0≤ ε ≤1, and O(2 n/2 ) memory to find a solution for the n -element knapsack problem in time O(2 n/4 (2 n/4 ) ε) . The cost of the proposed parallel algorithm is O(2 n/2 ) , which is an optimal method for solving the knapsack problem without memory conflicts and an improved result over the past researches.

The Simplest Possible Fully Correct Solution of the Clay Millennium Problem about P vs. NP. A Simple Proof That P ≠ NP = EXPTIME

In the current paper, I present probably the simplest possible abstract formal proof that P ≠ NP, and NP = EXPTIME, in the context of the standard mathematical set theory of computational complexity and deterministic Turing machines. My previous publications about the solution of the P vs. NP with the same result NP = EXPTIME, to be fully correct and understandable need the Lemma 4.1 and its proof of the current paper. The arguments of the current paper in order to prove NP = EXPTME are even simpler than in my previous publications. The strategy to solve the P vs. NP problem in the current paper (and in my previous publications) is by starting with an EXPTIME-complete language (problem) and proving that it has a re-formulation as an NP-class language, thus NP = EXPTIME. The main reason that the scientific community has missed so far such a simple proof, is because of two factors 1) It has been tried extensively but in vain to simplify the solutions of NP-complete problems from exponential time algorithms to polynomial time algorithms (which would be a good strategy only if P = NP) 2) It is believed that the complexity class NP is strictly a subclass to the complexity class EXPTIME (in spite the fact that any known solution to any of the NP-complete problems is not less than exponential). The simplicity of the current solution would have been missed if 2) was to be believed true. So far the majority of the relevant scientific community has considered this famous problem not yet solved. The present results definitely solve the 3rd Clay Millennium Problem about P versus NP in a simple, abstract and transparent way that the general scientific community, but also the experts of the area, can follow, understand and therefore become able to accept.

Completeness of General Solutions to Axisymmetric Problems of Transversely Isotropic Body

In this paper a kind of problems,which are a little wider than the axisymmetric problems of a transversely isotropic elastic body,are considered in a rectangular coordinates system.Two new general solutions of the axisymmetric problems of a transversely isotropic body are concisely obtained in a cylindrical coordinates system.Their completeness is also proved.It is worth while pointing out thai whether the meridional half-section is simply connected or multiply connected,both the new general solutions are single-valued.Using these results eight special general solutions are derived,including some known famous solutions.

利用分支学习优化子图同构的搜索

子图同构问题是经典的、具有广泛实际应用的NP完全问题。针对精确算法的分支策略依赖顶点度,计算代价高的问题,提出结合无解记录和顶点度约束规则,通过混合分支学习策略减少求解时间的方法(SIBL)。无解记录是指算法每次重启前无目标解的分支路径,为了去除无效搜索,首先移除目标图中顶点度小于当前模式图顶点的候选顶点,然后移除出现在无解记录中的顶点,最后依据顶点分值进行降序排序,优先选择分值大的顶点。新策略提供了利用上界下降量计算单个顶点和顶点匹配对的两种分值计算方式,并交替使用两种分值选择分支顶点以快速寻找目标解,避免贪心选择的局部最优问题。通过测试14220个来自生物、图像等领域的算例发现,SIBL相较于当前领先的Glasgow、McSplit+RL_SI分别多解决了10.08%、19.88%的中等难度算例,验证了分支学习能有效改进子图同构算法的求解效率。

An optical fiber network oracle for NP-complete problems

The modern information society is enabled by photonic fiber networks characterized by huge coverage and great complexity and ranging in size from transcontinental submarine telecommunication cables to fiber to the home and local segments.This world-wide network has yet to match the complexity of the human brain,which contains a hundred billion neurons,each with thousands of synaptic connections on average.However,it already exceeds the complexity of brains from primitive organisms,i.e.,the honey bee,which has a brain containing approximately one million neurons.In this study,we present a discussion of the computing potential of optical networks as information carriers.Using a simple fiber network,we provide a proof-of-principle demonstration that this network can be treated as an optical oracle for the Hamiltonian path problem,the famous mathematical complexity problem of finding whether a set of towns can be travelled via a path in which each town is visited only once.Pronouncement of a Hamiltonian path is achieved by monitoring the delay of an optical pulse that interrogates the network,and this delay will be equal to the sum of the travel times needed to visit all of the nodes(towns).We argue that the optical oracle could solve this NP-complete problem hundreds of times faster than brute-force computing.Additionally,we discuss secure communication applications for the optical oracle and propose possible implementation in silicon photonics and plasmonic networks.