[FOM] What can physical systems compute?

[Kreinovich, Vladik]

Great references, many thanks. May I also add that some physical theories and models, if true, will lead to the possibility of solving NP-hard problems in polynomial time, there is a wonderful survey by Aaronson.

In particular, in hyperbolic space-time, where the volume of a sphere grows exponentially with radius, one can fit exponentially many processors in a sphere of a linear radius, and thus, solve SAT and other problems in polynomial time; see, e.g.,
  Dara Morgenstein and Vladik Kreinovich, "Which
  algorithms are feasible and which are not depends on
  the geometry of space-time", Geombinatorics, 1995, Vol. 4, No.
  3, pp. 80-97.
  http://www.cs.utep.edu/vladik/1994/tr94-20a.pdf


Vladik Kreinovich and Maurice Margenstern, "In Some Curved Spaces,

  One Can Solve NP-Hard Problems in Polynomial Time", Notes of

  Mathematical Seminars of St. Petersburg Department of Steklov

  Institute of Mathematics, 2008, Vol. 358, pp. 224-250; reprinted in

  Journal of Mathematical Sciences, 2009, Vol. 158, No. 5, pp. 727-740.
http://www.cs.utep.edu/vladik/2007/tr07-30a.pdf

and references therein. Another easy-to-understand possibility is if time machine is possible. In this case, we can take as long as we want to compute and then send the result back in time, so we get it in time 0 (which is clearly polynomial). Even a threat of time machine can enable us to solve NP-hard problems in polynomial time: crudely speaking, we can use a random process to general n Boolean values, check whether these values form are a satisfying vector, and if not, set up a time machine to bring an inconsistency, then consistency will lead to a satisfying vector.


M. Koshelev and V. Kreinovich,

  "Towards Computers of Generation Omega -

  Non-Equilibrium Thermodynamics, Granularity, and Acausal Processes: A

  Brief Survey",

  Proceedings of the International Conference on

  Intelligent Systems and Semiotics (ISAS'97), National Institute of

  Standards and Technology Publ., Gaithersburg, MD, 1997, pp. 383-388.
http://www.cs.utep.edu/vladik/1997/tr97-12.pdf


Olga M. Kosheleva and Vladik Kreinovich. "What can physics give to

  constructive mathematics," Mathematical Logic and

  Mathematical Linguistics,

  Kalinin, 1981, pp. 117-128 (in Russian).




From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of Tucker J.V.
Sent: Friday, April 05, 2013 3:54 AM
To: fom at cs.nyu.edu
Subject: [FOM] What can physical systems compute?

Colleagues,

1. In a recent response to Dan Schwarts' question about invariance and complexity (March 20) I posted some observations about equivalence theorems for different computational models. I pointed out that the invariance we find in classical computability theory (= computability on natural numbers or strings) is special. For example, in the general case of universal algebras, or in the specific case of the reals, there are significant distinctions between models that we wish to preserve and use (rather than neglect). Invariance questions can be a great source of mathematical guidance in computability theory.


2. Some FOMers have asked me further questions, especially about my final point, which was:

"5. If you look at computational models equipped with simple physical systems as oracles you get a variety of classes that break the Church-Turing barrier, e.g. Turing machines even under the restriction of polynomial time can give you P/poly or P/log*."

This posting gives some background and references.


3. Felix Costa, Edwin Beggs and I have been exploring the question,

What can physical systems compute?,

by using physical systems as oracles to algorithms. Specifically, we have taken physical models of experiments that measure quantities and used them as oracles to polynomial-time Turing machines.

Of immediate interest is the way oracles are queried. A rational is presented as initial data to the equipment and a physical theory determines what happens next.  The experiment requires us to look at three cases: the initial data is given exactly, or with arbitrary accuracy, or with a fixed finite error. There is delay for the answer to the query.

Our methodology has been

(i)  to study extensively different particular experiments acting as oracles (we have considered 9 with varying levels of detail).

(ii) to seek axiomatisations of the oracle protocols.


4. The research programme started with a specific experiment to measure the vertex of a wedge. We developed the methodology and exactly characterised the computational classes in:

E J Beggs, J F Costa, B Loff and J V Tucker, Computational complexity with experiments as oracles, Proceedings Royal Society Series A, 464 (2008) 2777-2801.

E J Beggs, J F Costa, B Loff and J V Tucker, Computational complexity with experiments as oracles II: Upper bounds, Proceedings Royal Society Series A, 465 (2009) 1453-1465.

For queries that were exact and arbitrary accurate we first found the non-uniform complexity class P/poly.


5. Later, when we made a different physical model of the wedge we were able to characterise the computational classes as P/log* in:


E J Beggs, J F Costa and J V Tucker, The impact of models of a physical oracle on computational power, Mathematical Structures in Computer Science, Mathematical Structures in Computer Science, 22 (2012) 853-879.  doi:10.1017/S0960129511000557


6. Actually, many of the other experiments we studied led to P/log* and recently we have axiomatised the class of experiments in the paper:

E J Beggs, J F Costa and J V Tucker, Axiomatising physical experiments as oracles to algorithms, Philosophical Transactions Royal Society, A 370 (2012) 3359-3384.  doi:10.1098/rsta.2011.0427


7. Other non-uniform complexity classes arise (especially probabilistic classes) and we are in search of new axiomatisations to map the computational powers and relate them to physical attributes. The argument as to which of the 4 or 5 classes are important will ultimately be a physical argument.





John




-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130405/f541187c/attachment-0001.html>