Artículos con la etiqueta ‘Computational Complexity (cs.CC)’

«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.



Closing a Gap in the Complexity of Refinement Modal Logic

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

Refinement Modal Logic (RML), which was recently introduced by Bozzelli et al., is an extension of classical modal logic which allows one to reason about a changing model. In this paper we study computational complexity questions related to this logic, settling a number of open problems. Specifically, we study the complexity of satisfiability for the existential fragment of RML, a problem posed by Bozzelli, van Ditmarsch and Pinchinat. Our main result is a tight PSPACE upper bound for this problem, which we achieve by introducing a new tableau system. As a direct consequence, we obtain a tight characterization of the complexity of RML satisfiability for any fixed number of alternations of refinement quantifiers. Additionally, through a simple reduction we establish that the model checking problem for RML is PSPACE-complete, even for formulas with a single quantifier.



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.



Incomputability after Alan Turing

Por • 24 abr, 2013 • Category: Leyes

Incomputability as a mathematical notion arose from work of Alan Turing and Alonzo Church in the 1930s. Like Turing himself, it attracted less attention than it deserved beyond the confines of mathematics. Today our experiences in computer science, physics, biology, artificial intelligence, economics and the humanities point to the importance of the notion for understanding the world around us. This article takes a Turing centenary look at how the interface between the computable world and the incomputable formed a central theme in Turing’s work – from the early establishment of the standard model of the stored program computer, to the late work on emergence of form in nature, and the first approaches to understanding and simulating human intelligence.



Regular graphs and the spectra of two-variable logic with counting

Por • 14 abr, 2013 • Category: Crítica

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. This notion has been shown to be closely linked with complexity theory. In fact, asking whether the spectra of first-order logic sentences is closed under complement is equivalent to asking whether NE=coNE. In this paper we show that when restricted to using only two variables, the spectra of first-order logic sentences are closed under complement. In particular, we show that they are semilinear. At the heart of our proof are semilinear characterisations for the existence of regular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices.



The axiomatic power of Kolmogorov complexity

Por • 18 ene, 2013 • Category: Ciencia y tecnología

The famous Godel incompleteness theorem states that for every consistent sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical (and well studied) approach is to add to some theory T an axiom that claims the consistency of T. In this paper we discuss another approach motivated by Chaitin’s version of Godel’s theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us to prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter, unless NP=PSPACE.



Introducing the Computable Universe

Por • 18 jun, 2012 • Category: Leyes

Some contemporary views of the universe assume information and computation to be key in understanding and explaining the basic structure underpinning physical reality. We introduce the Computable Universe exploring some of the basic arguments giving foundation to these visions. We will focus on the algorithmic and quantum aspects, and how these may fit and support the computable universe hypothesis.



Introducing the Computable Universe

Por • 12 jun, 2012 • Category: Educacion

Some contemporary views of the universe assume information and computation to be key in understanding and explaining the basic structure underpinning physical reality. We introduce the Computable Universe exploring some of the basic arguments giving foundation to these visions. We will focus on the algorithmic and quantum aspects, and how these may fit and support the computable universe hypothesis.



Foreword: A Computable Universe, Understanding Computation and Exploring Nature As Computation

Por • 30 may, 2012 • Category: Ciencia y tecnología

I am most honoured to have the privilege to present the Foreword to this fascinating and wonderfully varied collection of contributions, concerning the nature of computation and of its deep connection with the operation of those basic laws, known or yet unknown, governing the universe in which we live. Fundamentally deep questions are indeed being grappled with here, and the fact that we find so many different viewpoints is something to be expected, since, in truth, we know little about the foundational nature and origins of these basic laws, despite the immense precision that we so often find revealed in them. Accordingly, it is not surprising that within the viewpoints expressed here is some unabashed speculation, occasionally bordering on just partially justified guesswork, while elsewhere we find a good deal of precise reasoning, some in the form of rigorous mathematical theorems. Both of these are as should be, for without some inspired guesswork we cannot have new ideas as to where look in order to make genuinely new progress, and without precise mathematical reasoning, no less than in precise observation, we cannot know when we are right — or, more usually, when we are wrong