检索结果-南通市图书馆

A public key cryptosystem based on data complexity under quantum environment

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2015年第11期58卷 48-58页

作者： WU WanQing ZHANG HuanGuo WANG HouZhen MAO ShaoWu JIA JianWei LIU JinHui Computer School Wuhan University

Since the Shor algorithm showed that a quantum algorithm can efficiently calculate discrete logarithms and factorize integers, it has been used to break the RSA, EIGamal, and ECC classical public key cryptosystems. This is therefore a significant issue in the context of ensuring communication security over insecure channels. In this paper, we prove that there are no polynomial-size quantum circuits that can compute all Boolean functions(of which there are 22ncases) in the standard quantum oracle model. Based on this,we propose the notion of data complexity under a quantum environment and suggest that it can be used as a condition for post-quantum computation. It is generally believed that np-complete problems cannot be solved in polynomial time even with quantum computers. Therefore, a public key cryptosystem and signature scheme based on the difficulty of np-complete problems and the notion of data complexity are presented here. Finally,we analyze the security of the proposed encryption and signature schemes.

关键词： public key cryptography information security np-complete problem complexity theory quantum computation

A Hopeful CNF-SAT─Algorithm Its High Efficiency, Industrial Application and Limitation

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 1998年第1期13卷 9-12页

作者：黄文奇李未 DepartmentofComputerScience HuazhongUniversityofScience＆TechnologyWuhan430074P.R.China DepartmentofC

From the SAT physical model, a physical hypothesis named PHHY is proposed. By PHHY, it is proved that there is a universally efficient algorithm for solving SAT problem. Then, by square packing problem, the authors show that there are interesting industrial np-complete problems which can be solved through SAT algorithms, but each way of solving like this will be much worse than that of a certain direct solving.

关键词： np-complete problem CNF-SAT satisfiability potential function approximate algorithm probability complexity.

维普期刊数据库

A novel computing model of the maximum clique problem based on circular DNA

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2010年第7期53卷 1409-1416页

作者： YANG Jing, ZHANG Cheng, XU Jin*, LIU XiangRong & QIANG XiaoLi Institute of Software, School of Electronics Engineering and Computer Science, Key Laboratory of High Confidence Software Technologies, Ministry of Education, Peking University, Beijing 100871, China Institute of Software School of Electronics Engineering and Computer Science Key Laboratory of High Confidence Software Technologies Ministry of Education Peking University Beijing China

A novel DNA-based model is developed to calculate np-complete problems, which is made of circular DNA molecules, streptavidin-coated magnetic beads and DNA circligase. To test the feasibility of the model, we apply it to compute a five-node maximum clique problem (MCP). During the computation, DNA molecule structures were transformed between linear DNA and circular DNA by streptavidin-coated magnetic beads and circligase, in order to search for the truth solutions. This greatly reduces the quantity of time and space consumed in calculation, and its time and space complexity both are O(n + m). Compared with the brute force method, using this algorithm searching process at most needs in n + 1 test tubes for an MCP with n vertices, while brute force method requires 2n test tubes. Furthermore, the constructed unenumerable initial solution space greatly improved the processing ability of the DNA computer. This novel model indicates that it may be a powerful DNA-based computer for solving some np-complete problems.

关键词： DNA-based computing model circular DNA molecules np-complete problem circligase streptavidin-coated magnetic beads

Energy-efficient routing for mobile agents in wireless sensor networks

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Frontiers of Electrical and Electronic Engineering in China 2007年第2期2卷 161-166页

作者： CAO Yongtao HE Chen JIANG Lingge Department of Electrical Engineering Shanghai Jiao Tong UniversityShanghai 200030China

In wireless sensor networks,data fusion(in-network processing)is a critical issue because sensor networks are energy-constrained and ***,a new scheme based on mobile agent has been proposed to solve the *** order and number of nodes on the route traversed by a mobile agent determine the energy consumption,and hence,they have a significant impact on the overall performance of the whole *** the limited transmission range of sensor nodes,we showed that this routing problem in a multi-hop cluster could be modeled as a node-weighted traveling tourist problem(TTP).We proved that the problem was nondeterministic polynomial time(np)-*** we presented a new approximation algorithm to solve the *** experiments demonstrate that the proposed heuristic is more energy-efficient than the two earlier ones.

关键词： wireless sensor networks mobile agent rout-ing np-complete problem

A Distributed Heuristic Algorithm on Delay-Constrained Least-Cost Unicast Routing

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

A Distributed Heuristic Algorithm on Delay-Constrained Least...

A Heuristic Approach to Fast NOVCA （Near Optimal Vertex Cover Algorithm）

2000 International Conference on Communication Technology(WCC2000·ICCT2000)

作者： Wang Zhengying Shi Bingxin Zou Ling Dept.Of Electronics & Information Eng. Hua Zhong University of Science and Technology

ISBN: (纸本)0780363949

Delay-constrained least-cost unicast routing problem is *** this paper,we present a distributed heuristic algorithm,called the distributed DCLC unicast routing heuristic based on selection function(DCLC-DSF).DCLC-DSF,which is a dynamic routing algorithm with re-routing and negotiation mechanism,only requires the local information to be kept at each node:the delay and cost of neighbor *** the worst case,for a network with e links and n nodes,its message complexity of DCLCDSF is O(λe),and the computation complexity of each node is O(n),whereλis the maximum node degree of the *** for a stable network,the message complexity is O(e).The simulation results also show that,on the average,DCLC-DSF requires much fewer ***,DCLC-DSF scales well to largescale *** picture the protocol of DCLC-DSF by a finite state *** also use simulation to compare DCLC-DSF to the optimal DCLC algorithm CBF and the least-delay path algorithm LDR The results show that DCLC-DSF path costs are within 5- 8%from those of the optimal *** work is ongoing.

关键词： QoS Routing np-complete problem Finite State Machine

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Computer Technology and Application 2014年第2期5卷 83-90页

作者： Sanj aya Gajurel Roger Bielefeld ITS Advanced Research Computing CWR U Cleveland 44106 USA

This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.

关键词： Vertex cover problem combinatorial problem np-complete problem approximation algorithm optimization algorithms.

A surface-based DNA algorithm for the minimal vertex cover problem

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Progress in Natural Science:Materials International 2003年第1期 80-82页

作者： PAN Linqiang , XU Jin and LIU Yachun (Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China Department of Mathematics and Physics, Institute of Engineering and Technology, Nanhua University, Hengyang 421001, China) Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074China Department of Mathematics and Physics Institute of Engineering and Technology Nanhua University Hengyang 421001 China

Abstract DNA computing was proposed for solving a class of intractable computational problems, of which the computing timewill grow exponentially with the problem size. Up to now, many achievements have been made to improve its performance and increase itsreliability. It has been shown many times that the surface-based DNA computing technique has very low error rate, but the technique hasnot been widely used in the DNA computing algorithms design. In this paper, a surface-based DNA computing algorithm for minimal ver-tex cover problem, a problem well-known for its exponential difficulty, is introduced. This work provides further evidence for the abilityof surface-based DNA computing in solving np-complete problems.

关键词： DNA computing np-complete problem minimal vertex cover problem.

Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science in China(Series F) 2001年第3期44卷 226-233页

作者：蒋昌俊 Department of Computer Science Tongji University Department of Computer Science Shandong Science Technology University Laboratory of Computer Science Institute of Software Chinese Academy of Sciences

As far as we know, the testing problem of legal firing sequence is np-complete for gener-al Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classes, such as persistent Petri nets, conflict-free Petri nets and state machine Petri nets. In this paper, the language properties of synchronous composition net are discussed. Based on these results, the testing algorithm polynomial-time complexity for legal firing sequence is proposed. Therefore, net classification of polynomial-time solvability for testing legal firing sequence is extended.

关键词： Petri net synchronous composition legal firing sequence testing algorithm np-complete problem polynomial-time complex.

维普期刊数据库

Solid phase based DNA solution of the coloring problem

在线全文

学校读者我要写书评

暂无评论

Progress in Natural Science:Materials International 2004年第5期 85-88页

作者： PAN Linqiang , LIU Guangwu, XU Jin and LIU Yachun (1. Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China 2. Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tarraco 1, 43005 Tarragona, Spain 3. Department of Mathematical and Physical Science, Nanhua University, Hengyang 421001, China) Department of Control Science and Engineering Huazhong University of Science and TechnologyWuhan 430074China Research Group on Mathematical Linguistics Rovira i Virgili UniversityPl. Imperial Trraco 143005 TarragonaSpain Department of Control Science and Engineering Huazhong University of Science and TechnologyWuhan 430074China Department of Mathematical and Physical Science Nanhua UniversityHengyang 421001China

DNA computing has the potential to tackle computationally difficult problems that have real-world implications. The parallel search capabilities of DNA make it a valuable tool for approaching intractable computational problems, for which conventional computers have limited potentials. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. In this paper, the coloring problem has been solved by means of molecular biology techniques. The coloring problem is a well-known np-complete problem. This work represents further evidence for the ability of DNA computing to solve np-complete problems.

关键词： DNA computing np-complete problem coloring problem.