Artículos con la etiqueta ‘computación y complejidad’

“Information-Friction” and its implications on minimum energy required for communication

Por • 10 ene, 2014 • Category: Ambiente

Just as there are frictional losses associated with moving masses on a surface, what if there were frictional losses associated with moving information on a substrate? Indeed, many methods of communication suffer from such frictional losses. We propose to model these losses as proportional to “bit-meters,” i.e., the product of mass of information (i.e., the number of bits) and the distance of information transport. We use this “information-friction” model to understand fundamental energy requirements on encoding and decoding in communication circuitry. First, for communication across a binary input AWGN channel, we arrive at limits on bit-meters (and thus energy consumption) for decoding implementations that have a predetermined input-independent lengths of messages.



Problem Complexity Research from Energy Perspective

Por • 21 sep, 2013 • Category: Crítica

Computational complexity is a particularly important objective. The idea of Landauer principle was extended through mapping three classic problems (sorting,ordered searching and max of N unordered numbers) into Maxwell demon thought experiment in this paper. The problems’complexity is defined on the entropy basis and the minimum energy required to solve them are rigorous deduced from the perspective of energy (entropy) and the second law of thermodynamics. Then the theoretical energy consumed by real program and basic operators of classical computer are both analyzed, the time complexity lower bounds of three problems’all possible algorithms are derived in this way. The lower bound is also deduced for the two n*n matrix multiplication problem. In the end, the reason why reversible computation is impossible and the possibility of super-linear energy consumption capacity which may be the power behind quantum computation are discussed, a conjecture is proposed which may prove NP!=P. The study will bring fresh and profound understanding of computation complexity.