The problem of perfectly secure communication has enjoyed considerable theoretical treatment over the last decades. Results in this area include the identification of multipath transmission as a necessary ingredient, ...The problem of perfectly secure communication has enjoyed considerable theoretical treatment over the last decades. Results in this area include the identification of multipath transmission as a necessary ingredient, as well as quantum key distribution （QKD）, which can perfectly protect direct lines, Combining the advantages of the quantum and multipath transmission paradigm, as well as rigorously analyzing the security of such combined techniques, is possible by virtue of game-theory. Based on a game-theoretic measure of channel vulnerability, the authors prove the problem of setting up infrastructures for QKD-based multipath transmission to be NP-complete. The authors consider the problem in two flavors, both being computationally hard. Remarkably, the authors＇ results indicate that the P-vs-NP-question is only of minor effect for confidentiality, because either nowadays public-key cryptosystems remain secure （in case that P, NP） or infrastructures facilitating perfectly confidential communication can be constructed efficiently （in case that P = NP）.展开更多
We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for ...We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson's. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.展开更多
In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both cla...In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both classical computer and the quantum computer. According to the general principle of quantum interference, the very essence of quantum interference is the interference of the sub-waves of the quantum system itself A quantum system considered here can be any quantum system： a single microscopic particle, a composite quantum system such as an atom or a molecule, or a loose collection of a few quantum objects such as two independent photons. In the duality computer, the wave of the duality computer is split into several sub-waves and they pass through different routes, where different computing gate operations are performed. These sub-waves are then re-combined to interfere to give the computational results. The quantum computer, however, has only used the particle nature of quantum object. In a duality computer, it may be possible to find a marked item from an unsorted database using only a single query, and all NP-complete problems may have polynomial algorithms. Two proof-of-the-principle designs of the duality computer are presented： the giant molecule scheme and the nonlinear quantum optics scheme. We also propose thought experiment to check the related fundamental issues, the measurement efficiency of a partial wave function.展开更多
Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed sy...Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.展开更多
The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the mach...The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems.展开更多
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 ...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”.展开更多
In multi-component systems,the components are dependent,rather than degenerating independently,leading to changes inmaintenance schedules.In this situation,this study proposes a grouping dynamicmaintenance strategy.Co...In multi-component systems,the components are dependent,rather than degenerating independently,leading to changes inmaintenance schedules.In this situation,this study proposes a grouping dynamicmaintenance strategy.Considering the structure of multi-component systems,the maintenance strategy is determined according to the importance of the components.The strategy can minimize the expected depreciation cost of the system and divide the system into optimal groups that meet economic requirements.First,multi-component models are grouped.Then,a failure probability model of multi-component systems is established.The maintenance parameters in each maintenance cycle are updated according to the failure probability of the components.Second,the component importance indicator is introduced into the grouping model,and the optimization model,which aimed at a maximum economic profit,is established.A genetic algorithm is used to solve the non-deterministic polynomial(NP)-complete problem in the optimization model,and the optimal grouping is obtained through the initial grouping determined by random allocation.An 11-component series and parallel system is used to illustrate the effectiveness of the proposed strategy,and the influence of the system structure and the parameters on the maintenance strategy is discussed.展开更多
Given a complete graph with vertex set X and subsets X_1, X_2,..., X_n, the problem of finding a subgraph G with minimum number of edges such that for every i = 1, 2,..., n G contains a spanning tree on X_i, arises in...Given a complete graph with vertex set X and subsets X_1, X_2,..., X_n, the problem of finding a subgraph G with minimum number of edges such that for every i = 1, 2,..., n G contains a spanning tree on X_i, arises in the design of vaccum systems. In general, this problem is NP-complete and it is proved that for n = 2 and 3 this problem is polynomial-time solvable. In this paper, we prove that for n = 4, the problem is also polynomial-time solvable and give a method to construct the corresponding graph.展开更多
Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G. In the authors＇ previous work, it has been...Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G. In the authors＇ previous work, it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P= NP. In this paper the authors show that for any fixed integer r ≥ 5, if the edges of a graph G are colored by r colors, called an r-edge-colored graph, the problem remains NP-complete. Similar result holds for the monochromatic path （cycle） partition problem. Therefore, to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.展开更多
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 “...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.展开更多
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 proble...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.展开更多
文摘The problem of perfectly secure communication has enjoyed considerable theoretical treatment over the last decades. Results in this area include the identification of multipath transmission as a necessary ingredient, as well as quantum key distribution （QKD）, which can perfectly protect direct lines, Combining the advantages of the quantum and multipath transmission paradigm, as well as rigorously analyzing the security of such combined techniques, is possible by virtue of game-theory. Based on a game-theoretic measure of channel vulnerability, the authors prove the problem of setting up infrastructures for QKD-based multipath transmission to be NP-complete. The authors consider the problem in two flavors, both being computationally hard. Remarkably, the authors＇ results indicate that the P-vs-NP-question is only of minor effect for confidentiality, because either nowadays public-key cryptosystems remain secure （in case that P, NP） or infrastructures facilitating perfectly confidential communication can be constructed efficiently （in case that P = NP）.
文摘We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson's. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.
基金The project supported by the National Fundamental Research Program under Grant No. 001CB309308, National Natural Science Foundation of China under Grant Nos. 10325521 and 60433050, and the SRFDP Program of the Ministry of Education of China
文摘In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both classical computer and the quantum computer. According to the general principle of quantum interference, the very essence of quantum interference is the interference of the sub-waves of the quantum system itself A quantum system considered here can be any quantum system： a single microscopic particle, a composite quantum system such as an atom or a molecule, or a loose collection of a few quantum objects such as two independent photons. In the duality computer, the wave of the duality computer is split into several sub-waves and they pass through different routes, where different computing gate operations are performed. These sub-waves are then re-combined to interfere to give the computational results. The quantum computer, however, has only used the particle nature of quantum object. In a duality computer, it may be possible to find a marked item from an unsorted database using only a single query, and all NP-complete problems may have polynomial algorithms. Two proof-of-the-principle designs of the duality computer are presented： the giant molecule scheme and the nonlinear quantum optics scheme. We also propose thought experiment to check the related fundamental issues, the measurement efficiency of a partial wave function.
文摘Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.
基金Supported by the National Natural Science Foundation of China(11871213,71431004).
文摘The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems.
文摘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”.
基金supported by the National Natural Science Foundation of China under Grant No.12172100.
文摘In multi-component systems,the components are dependent,rather than degenerating independently,leading to changes inmaintenance schedules.In this situation,this study proposes a grouping dynamicmaintenance strategy.Considering the structure of multi-component systems,the maintenance strategy is determined according to the importance of the components.The strategy can minimize the expected depreciation cost of the system and divide the system into optimal groups that meet economic requirements.First,multi-component models are grouped.Then,a failure probability model of multi-component systems is established.The maintenance parameters in each maintenance cycle are updated according to the failure probability of the components.Second,the component importance indicator is introduced into the grouping model,and the optimization model,which aimed at a maximum economic profit,is established.A genetic algorithm is used to solve the non-deterministic polynomial(NP)-complete problem in the optimization model,and the optimal grouping is obtained through the initial grouping determined by random allocation.An 11-component series and parallel system is used to illustrate the effectiveness of the proposed strategy,and the influence of the system structure and the parameters on the maintenance strategy is discussed.
文摘Given a complete graph with vertex set X and subsets X_1, X_2,..., X_n, the problem of finding a subgraph G with minimum number of edges such that for every i = 1, 2,..., n G contains a spanning tree on X_i, arises in the design of vaccum systems. In general, this problem is NP-complete and it is proved that for n = 2 and 3 this problem is polynomial-time solvable. In this paper, we prove that for n = 4, the problem is also polynomial-time solvable and give a method to construct the corresponding graph.
基金Supported by the National Natural Science Foundation of China,PCSIRT and the"973"Program
文摘Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G. In the authors＇ previous work, it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P= NP. In this paper the authors show that for any fixed integer r ≥ 5, if the edges of a graph G are colored by r colors, called an r-edge-colored graph, the problem remains NP-complete. Similar result holds for the monochromatic path （cycle） partition problem. Therefore, to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.
文摘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.
文摘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.
