| Ed Blakey |
| edward.blakey@queens.ox.ac.uk |
|
|
A New Gap Theorem: the Gap Theorem’s Robustness against Dominance (2009) Blakey, E. (In preparation)
This conference paper was presented at The Science and Philosophy of Unconventional Computing 2009. The slides used in the presentation are available here. The work forms part of the EPSRC-funded project, Complexity and Decidability in Unconventional Computational Models.
Abstract (provisional). Thanks to Trachtenbrot and (independently) Borodin, computational complexity theorists have the Gap Theorem, which guarantees the existence of arbitrarily large gaps in the hierarchy of complexity classes. That is, there can be made arbitrarily large increases in resource availability that, for all their vastness, yield no additional computational power: every computation that can be performed given the extra resource could have been performed in its absence.
In response to needs arising during complexity analyses of non-standard—quantum, analogue, chemical, optical, etc.—computers, the notion of dominance was introduced (we recap in the present paper the relevant definitions). With dominance comes a corresponding hierarchy of complexity classes, and it is natural to ask whether a gap theorem, analogous to that of Trachtenbrot and Borodin, holds in this context.
In this paper, we show that a gap theorem does indeed hold for certain complexity classes defined in terms of dominance. We also consider related statements concerning other dominance classes, and formulate corresponding conjectures.
Keywords: gap theorem, dominance, computational complexity, computability, non-standard computing, unconventional computing.
Beyond Blum: What is a Resource? (2008) Blakey, E. In the International Journal of Unconventional Computing (to appear; in preparation)
This peer-reviewed journal paper is to appear in the International Journal of Unconventional Computing. It forms part of the EPSRC-funded project, Complexity and Decidability in Unconventional Computational Models.
Abstract (provisional). When analysing a Turing machine’s complexity, we can appeal to decades of experience to determine which resources (typically time steps/tape cells) to measure. More fundamentally, we have Blum’s criteria for admission as a valid resource.
When analysing a non-Turing computer’s complexity, the situation is less clear. What resources are relevant for, say, an analogue computer? Can we meaningfully compare a Turing machine’s time complexity with an optical computer’s precision complexity? Crucially, what should we admit as a resource in the context of non-standard computation?
Our aim is to specify a suitable, non-Turing-computer analogue of Blum’s axioms. We start with the existing axioms, but show that, alone, they are insufficient. Accordingly, we further restrict the notion of resource: we define normality of resource, advocating consideration only of normal resources during non-standard computers’ complexity analyses. This eliminates some ‘deceptive’ complexity behaviour encountered with Blum’s axioms alone.
Keywords: Computational complexity; non-Turing/non-standard computer; resource; Blum’s axioms; normalization; dominance.
Dominance: Consistently Comparing Computational Complexity (2008) Blakey, E. Oxford University Computing Laboratory’s Research Report series, RR-08-09
This report appears in Oxford University Computing Laboratory’s Research Report series as RR-08-09. It forms part of the EPSRC-funded project, Complexity and Decidability in Unconventional Computational Models.
Abstract. Though complexity theory strives primarily to categorize problems according to their complexity, it is typically the complexity only of methods of solving problems that we can directly measure. Specifically, we have an upper bound for a problem’s complexity: namely, the complexity of the most efficient known solution method for the problem. In order to improve such bounds, it is desired to consider sets of solution methods that are as complete as possible; but, whilst comparisons of computing systems’ respective efficiencies can—via O-notation—readily be made when the systems conform to the same computational model and when the comparison is with respect to the same resource, it is not clear how to compare model-heterogeneous sets of solution methods—this imposes a constraint on the size of sets of methods that can be considered, and a corresponding constraint on the quality of bounds on the complexity of problems.
Here, we propose the notion of dominance as a way of augmenting the power of O-notation to compare systems’ complexity. In particular, our augmentation allows meaningful comparison of the respective complexities, with respect to different resources, of computing systems that conform to different computational models, thus allowing consideration of larger, model-heterogeneous sets of solution methods and, hence, improved bounds on problems’ complexity.
Computational Complexity in Non-Turing Models of Computation; The What, the Why and the How (2008) Blakey, E. In the proceedings of Quantum Physics and Logic/Development of Computational Models 2008 (to appear)
This peer-reviewed conference paper was presented at Quantum Physics and Logic/Development of Computational Models 2008, in the proceedings of which it is to appear. A video of the presentation is available here, and the slides used therein here.
Abstract. We preliminarily recap what is meant by complexity and non-Turing computation, by way of explanation of our title, ‘Computational Complexity in Non-Turing Models of Computation’.
Based on investigation of a motivating example, we argue that traditional complexity theory does not adequately capture the true complexity of certain non-Turing computers, and, hence, that an extension of the theory is needed in order to accommodate such machines.
We propose a framework of complexity that is not computation-model-dependent—that, rather, is extensible so as to accommodate diverse computational models—, and that allows meaningful comparison of computers’ respective complexities, whether or not the comparison be with respect to different resources, and whether or not the computers be instances of different models of computation.
Whilst, we suggest, complexity theory is—without some modification—of limited applicability to certain non-standard models, we hope that the ideas described here go some way to showing how such modification can be made, and that members of the non-Turing-computation community—not least participants of Quantum Physics and Logic/Development of Computational Models 2008—find these ideas both useful and interesting.
Keywords: Computational complexity, non-standard/non-Turing computational models, precision.
Factorizing RSA Keys, an Improved Analogue Solution (2008) Blakey, E. In the Journal of New Generation Computing, vol. 27, no. 2, Y. Suzuki, M. Hagiya, H. Umeo, A. Adamatzky (guest editors), Ohmsha/Springer Earlier version in Natural Computing, Proceedings in Information and Communications Technology, vol. 1, Y. Suzuki, M. Hagiya, H. Umeo, A. Adamatzky (editors), Springer, ISBN 978-4-431-88980-9
This peer-reviewed journal paper appears in the Journal of New Generation Computing. It was presented at the Second International Workshop on Natural Computing, in the peer-reviewed proceedings of which an earlier version of the paper appears. The slides used in the presentation are available here.
Abstract. Factorization is notoriously difficult. Though the problem is not known to be NP-hard, neither efficient, algorithmic solution nor technologically practicable, quantum-computer solution has been found. This apparent complexity, which renders infeasible the factorization of sufficiently large values, makes secure the RSA cryptographic system.
Given the lack of a practicable factorization system from algorithmic or quantum-computing models, we ask whether efficient solution exists elsewhere; this motivates the analogue system presented here. The system’s complexity is prohibitive of its factorizing arbitrary, natural numbers, though the problem is mitigated when factorizing n = pq for primes p and q of similar size, and, hence, when factorizing RSA keys.
Ultimately, though, we argue that the system’s polynomial time and space complexities are testament not to its power, but to the inadequacy of traditional, Turing-machine-based complexity theory; we propose precision complexity (defined in our previous paper [1]) as a more relevant measure, and advocate, more generally, non-standard complexity analyses for non-standard computers.
Keywords: Factorization, Analogue Computer, Computational Complexity, Precision Complexity, RSA Cryptography.
1. Blakey, E., “On the Computational Complexity of Physical Computing Systems”, in Proceedings of Unconventional Computing 2007 (Adamatzky, A; Bull, L.; De Lacy Costello, B.; Stepney, S. and Teuscher, C. editors), Luniver Press, pp. 95—115, 2007.
A Model-Independent Theory of Computational Complexity; Price: from Patience to Precision (and Beyond) (2007) Blakey, E. Unpublished academic dissertation
This dissertation was written during the author’s studies for the degree of Doctor of Philosophy in Computer Science (Oxford, 2006 — present), in particular for consideration during the transfer from PRS to DPhil status. It describes the author’s DPhil thesis project, including work already completed and future work.
Abstract. The field of computational complexity strives to categorize problems according to the cost of their solution. Whereas reasoning directly about the computational complexity of a problem seems inherently difficult, it is relatively easy to ascertain the complexity of specific methods (algorithms, analogue computers, Turing machines, etc.) that solve the problem.
Consequently, our sole understanding of a problem’s complexity is, in the majority of cases, gleaned via our having determined the complexity of solution methods for the problem; specifically, we have that the problem’s complexity is bounded from above by the complexity of the most efficient known solution method.
In order to improve such bounds, it is desired to consider as large a set as is possible of solution methods for a problem. Each set so considered in practice, however, is likely to be of solution methods taken from a single model of computation (often that of the Turing machine). This is a necessary evil of our inability meaningfully to compare the complexity of instances of different computation models.
Required, then, is a more general framework in which to study complexity; in particular, we wish to be able to use the framework to consider on a consistent and comparable footing the complexity—with respect to several notions of resource—of instances of diverse models of computation. The proposed DPhil project motivates, defines and investigates such a framework.
On the Computational Complexity of Physical Computing Systems (2007) Blakey, E. In Unconventional Computing 2007, A. Adamatzky, L. Bull, B. De Lacy Costello, S. Stepney, C. Teuscher (editors), Luniver Press, ISBN 978-1-905986-05-7
This peer-reviewed conference paper was presented at Unconventional Computing 2007, in the proceedings of which it appears. The slides used in the presentation are available here.
Abstract. By far the most studied model of computation is the Turing machine model. It is the suggestion of Church's Thesis that, as far as computability is concerned, consideration of this model alone is sufficient; but what of complexity?
The traditional notion of computational resource, in terms of which computational complexity may be defined (since, in essence, complexity is nothing more than required resource viewed as a function of input size), caters almost exclusively for algorithmic models of computation such as the Turing machine model. Accordingly, the most commonly encountered computational resource is run-time of a Turing machine or algorithm or equivalent.
We here extend the definition of resource, notably so as to include the physical notion of precision with which we can make measurements; this allows characterization in a more insightful way of the complexity of computations performed by analogue, DNA, quantum and other physical computers.
The primary intent of this (ongoing) work is not that it be of practical use by, for example, offering physical solution methods that improve upon the speed, efficiency or similar offered by existing—especially digital—computers. Rather, the work is a theoretical study: the wider, more physical framework of computation is presented as a context in which to generalize the closely related notions of resource and complexity. The ultimate aim, from this theoretical viewpoint, is to shed light on whether complexity is inherent in problems as opposed to solution methods, whether the latter be physical or algorithmic.
An Analogue Solution to the Problem of Factorization (2007) Blakey, E. Oxford University Computing Laboratory’s Research Report series, RR-07-04 Associated patent: System and method for finding integer solutions, United States patent 7453574
This report appears in Oxford University Computing Laboratory’s Research Report series as RR-07-04. The method of factorization described is the subject of a US patent, applied for by IBM and with the author as sole inventor.
Abstract. The task of factorizing a given integer is notoriously difficult, to the extent of rendering computationally infeasible the extraction of factors of numbers beyond a certain size. This infeasibility is what makes the RSA cryptographic system, for example, secure.
We describe an analogue method1 of factorizing. Just as with traditional algorithms, there is a practical limit to the size of numbers that the method can factorize; in contrast with traditional algorithms, however, the method suffers no increase in calculation time as the input number approaches this limit.
The process described exploits a direct physical implementation of a geometric formulation of the problem of factorizing; this allows factors of numbers within the allowed range to be ascertained (or else primality guaranteed) virtually instantaneously.
1 The method is the subject of a pending US patent, applied for by IBM and with sole inventor Ed Blakey.
A Cellular-Automatic Implementation of Communication Channels, with particular consideration of Several Intersecting Channels (2002) Blakey, E. Unpublished academic dissertation
This dissertation was submitted as part of the author’s studies for the degree of Master of Science in Mathematics and the Foundations of Computer Science (Oxford, 2001 — 2002, Distinction).
Abstract. Channels of communication (e.g. wires along which are sent electrical pulses which encode a bit-stream) are in reality, and in particular in three spatial dimensions, free to pass over or under each other so as to cross over without intersecting; a rudimentary consideration of their two-dimensional analogue shows however that, assuming wires of strictly positive thickness, to cross two channels requires that they intersect. It is therefore natural to ask whether a system of two such intersecting channels can in a suitable, two-dimensional mathematical model be implemented in such a way that each channel can successfully carry its respective data from source to sink, without the two input-streams interfering (specifically at the intersection); this is the problem on which this dissertation focuses.
The approach is to model channels in a way reminiscent of both cellular automata and systolic arrays; notably, both space and time are rendered discretely. It is shown that in this model, the problem described above can be solved (a claim whose proof is constructive)—this is arguably the most insightful conclusion of the dissertation. It is then natural to consider the optimality (in various senses) of a solution; accordingly such discussion is presented here. Consideration is also given to the success with which the ‘spirit’ of the intuitively-stated motivating problem is captured by the mathematical model.
Concluded in this dissertation is that there exist solutions to those problems potentially arising in situations in which channels intersect, and also that to cross channels instead of routing them around each other is in some senses beneficial.
The Group Theory Behind Rubik’s Cube (c.2000) Blakey, E. Unpublished academic essay
This extended essay was submitted as part of the author’s studies for the degree of Bachelor of Arts in Mathematical Sciences (Oxford, 1998 — 2001, First Class Honours).
Purpose of the Essay. This essay is a study of Rubik’s cube in the context of group theory. It deals with a standard 3×3×3 cube, exploring the group of available moves and its action on sets of the cube’s constituent parts, discussing conjugation and parity, and ultimately showing the group of moves to be isomorphic to a better-understood group. The essay is not a ‘hint book’ for the cube—I don’t offer algorithms to solve it—but rather a discussion of the group theory involved.
Page last updated on 16.iv.2009.