Complexity Resources in Physical Computation



Monday 24 — Wednesday 26 August, 2009

Oxford University Computing Laboratory, Oxford, UK


This workshop aims to address the question: what physical resources are consumed during computation?

The standard, Turing-machine case is well studied, and the relevant complexity resources—notably run-time and memory space—are accordingly routinely considered. But what of the non-standard case? And what of trade-offs between component models in hybrid computational models?

Some relevant questions are

  • What resources are relevant to computation via quantum, analogue, optical, ... computer?
  • What can be said of complexity, entanglement, etc. in biological systems and in nature?
  • Can we meaningfully view energy, precision of measurement, transfer of information, ... as resources?
  • What is the trade-off between classical and quantum resources in a measurement-based quantum computer?
  • Is there a trade-off between computational and spatio-temporally distributed resources?
  • A more fundamental trade-off question: is there an underlying 'overall' resource, of which individual resources are facets?
  • What complexity results follow from consideration of hypothetical resources such as non-local boxes?
  • What general framework of complexity is there that accommodates all computational models?
  • Can computational limitations be expressed as a physical law?

The workshop aims to bring together people interested in such questions, and shed light on these issues.

The workshop is funded by EPSRC grant, Complexity and Decidability in Unconventional Computational Models.