检索结果-内蒙古大学图书馆

Reducing computational complexity for DBZF Precoding in xDSL Downlinks 4

学校读者我要写书评

暂无评论

Reducing Computational Complexity for DBZF Precoding in xDSL...

4th International Conference on Information Technology and Nanotechnology, ITNT 2018

作者： Semushin, I.V. Tsyganova, J.V. Ulyanovsk State University Lev Tolstoy street 42 Ulyanovsk432017 Russia

However broad the Decomposition-based Zero-forcing (DBZF) precoder acceptance may be, reducing the computational complexity of its implementation is an absolute necessity for the VDSL networking professionals. The paper digs deeper into this problem from the perspective of matrix inversion which is inherent in the very nature of the DBZF. Eight strategies considered here differ in mode of action: four of them include matrix inversion, and four others drop implementing the procedure. While the baseline strategy itemized under No. 1 acts with the Gaussian LU-decomposition, strategy No. 2 deals with the Jordanian LU - decomposition thereby enabling mild reduction of the operation count. Strategy No. 3 works for more significant reduction as it operates with the elimination form of the inverse matrix. The most cost-cutting are strategies excluding the question of matrix inversion and replacing it by far more straightforward linear system solution, as it is in Strategy No. 4. Both cases No. 3 and No. 4 are examined in their two subcases marked (1) and (2) differing in Gaussian (1) or Jordanian (2) subversions of the same LU-decomposition. An alternative strategy No. 5 uses the least squares-based square-root-type sequential system solution, and it is the most accurate computational procedure when compared with other strategies. Strategy No. 6 is different in that it implements the QR-decomposition of the channel transition matrix H, and it is the most numerically robust one against the ill-conditioned matrix H. © 2018 Institute of Physics Publishing. All rights reserved.

关键词： computational complexity

computational complexity of the Rydberg blockade in two dimensions

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Pichler, Hannes Wang, Sheng-Tao Zhou, Leo Choi, Soonwon Lukin, Mikhail D. ITAMP Harvard-Smithsonian Center for Astrophysics CambridgeMA02138 United States Department of Physics Harvard University CambridgeMA02138 United States Department of Physics University of California Berkeley BerkeleyCA94720 United States

We discuss the computational complexity of finding the ground state of the two-dimensional array of quantum bits that interact via strong van derWaals interactions. Specifically, we focus on systems where the interaction strength between two spins depends only on their relative distance x and decays as 1=x6that have been realized with individually trapped homogeneously excited neutral atoms interacting via the so-called Rydberg blockade mechanism. We show that the solution to NP-complete problems can be encoded in ground state of such a many-body system by a proper geometrical arrangement of the atoms. We present a reduction from the NP-complete maximum independent set problem on planar graphs with maximum degree three. Our results demonstrate that computationally hard optimization problems can be naturally addressed with coherent quantum optimizers accessible in near term experiments. Copyright © 2018, The Authors. All rights reserved.

关键词： computational complexity

computational complexity of Observing Evolution in Artificial-Life Forms

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Misra, Janardan

Observations are an essential component of the simulation based studies on artificial-evolutionary systems (AES) by which entities are identified and their behavior is observed to uncover higher-level "emergent" phenomena. Because of the heterogeneity of AES models and implicit nature of observations, precise characterization of the observation process, independent of the underlying micro-level reaction semantics of the model, is a difficult problem. Building upon the multiset based algebraic framework to characterize state-space trajectory of AES model simulations, we estimate bounds on computational resource requirements of the process of automatically discovering life-like evolutionary behavior in AES models during simulations. For illustration, we consider the case of Langton’s Cellular Automata model and characterize the worst case computational complexity bounds for identifying entity and population level reproduction. Copyright © 2018, The Authors. All rights reserved.

关键词： computational complexity

computational complexity of Enumerative 3-Manifold Invariants

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Samperton, Eric Griffin UNIVERSITY OF CALIFORNIA

Fix a finite group G. We analyze the computational complexity of the problem of counting homomorphisms π1(X) → G, where X is a topological space treated as computational input. We are especially interested in requiring G to be a fixed, finite, nonabelian, simple group. We then consider two cases: when the input X = M is a closed, triangulated 3-manifold, and when X = S3 r K is the complement of a knot (presented as a diagram) in S3. We prove complexity theoretic hardness results in both settings. When M is closed, we show that counting homomorphisms π1(M) → G (up to automorphisms of G) is #P-complete via parsimonious Levin reduction—the strictest type of polynomial-time reduction. This remains true even if we require M to be an integer homology 3-sphere. We prove an analogous result in the case that X = S3 r K is the complement of a knot. Both proofs proceed by studying the action of the pointed mapping class group MCG∗(Σ) on the set of homomorphisms {π1(Σ) → G} for an appropriate surface Σ. In the case where X = M is closed, we take Σ to be a closed surface with large genus. When X = S3 r K is a knot complement, we take Σ to be a disk with many punctures. Our constructions exhibit classical computational universality for a combinatorial topological quantum field theory associated to G. Our "topological classical computing" theorems are analogs of the famous results of Freedman, Larsen and Wang establishing the quantum universality of topological quantum computing with the Jones polynomial at a root of unity. Instead of using quantum circuits, we develop a circuit model for classical reversible computing that is equivariant with respect to a symmetry of the computational alphabet. Copyright © 2018, The Authors. All rights reserved.

关键词： computational complexity

Protecting election from bribery: New approach and computational complexity characterization 17

学校读者我要写书评

暂无评论

Protecting election from bribery: New approach and computati...

17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018

作者： Chen, Lin Xu, Lei Xu, Shouhuai Gao, Zhimin Shah, Nolan Lu, Yang Shi, Weidong University of Houston HoustonTX United States University of Texas at San Antonio San AntonioTX United States

ISBN: (纸本)9781510868083

The bribery problem in elections has received a considerable amount of attention. In this paper, we initiate the study of a related, but new problem, the protection problem, namely protecting elections from bribery. In this problem, there is a defender who is given a defense budget and can use the budget to award some of the voters such that they cannot be bribed anymore. This naturally leads to the following bi-level decision problem: Is it possible for the defender with a given defense budget to protect an election from being manipulated by the attacker with a given attack budget for bribing voters? We characterize the computational complexity of the protection problem. We show that it is in general significantly harder than the bribery problem. However, the protection problem can be solved, under certain circumstances, in polynomial time. © 2018 International Foundation for Autonomous Agents and Multiagent Systems (***). All rights reserved.

关键词： computational complexity

computational complexity of Games and Puzzles

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Costa, Diogo Manuel dos Santos

In this thesis, we survey techniques and results from the study of complexity Theory and Games. We then apply these techniques to obtain new results for previously unstudied games. Our contributions in the games Hexiom, Cut the Rope, and Back to Bed may be helpful in further studies by exploiting structure common to several games. We also highlight some interesting paths for further study, related to uncertainty, that have yet to receive thorough study given their prevalence in today’s games. Copyright © 2018, The Authors. All rights reserved.

关键词： computational complexity

Restricted power - computational complexity results for strategic defense games 9

学校读者我要写书评

暂无评论

Restricted power - Computational complexity results for stra...

9th International Conference on Fun with Algorithms, FUN 2018

作者： De Haan, Ronald Wolf, Petra Institute for Logic Language and Computation University of Amsterdam Netherlands Wilhelm-Schickard-Institut University of Tübingen Germany

ISBN: (纸本)9783959770675

We study the game Greedy Spiders, a two-player strategic defense game, on planar graphs and show PSPACE-completeness for the problem of deciding whether one player has a winning strategy for a given instance of the game. We also generalize our results in metatheorems, which consider a large set of strategic defense games. We achieve more detailed complexity results by restricting the possible strategies of one of the players, which leads us to Σp2- and Πp2-hardness results. © Ronald de Haan and Petra Wolf;licensed under Creative Commons License CC-BY 9th International Conference on Fun with Algorithms (FUN 2018).

关键词： computational complexity

computational complexity lower bounds of certain discrete Radon transform approximations

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Khanipov, Timur M.

For the computational model where only additions are allowed, the Ω(n2 log n) lower bound on operations count with respect to image size n × n is obtained for two types of the discrete Radon transform implementations: the fast Hough transform and a generic strip pattern class which includes the classical Hough transform, implying the fast Hough transform algorithm asymptotic optimality. The proofs are based on a specific result from the boolean circuits complexity theory and are generalized for the case of boolean ∨ binary operation. Copyright © 2018, The Authors. All rights reserved.

关键词： computational complexity

computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Formenti, Enrico Perrot, Kévin Rémila, Éric 2000 route des Lucioles BP 121 Sophia Antipolis CedexF-06903 France 46 allé d’Italie Lyon Cedex 769364 France 2120 Blanco Encalada Santiago Chile Site stéphanois 6 rue Basse des Rives Saint-Etienne Cedex 242 023 France

In this paper we prove that the general avalanche problem AP is in NC for the Kadanoff sandpile model in one dimension, answering an open problem of [2]. Thus adding one more item to the (slowly) growing list of dimension sensitive problems since in higher dimensions the problem is P-complete (for monotone sandpiles). Copyright © 2018, The Authors. All rights reserved.

关键词： computational complexity