http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf

Preface: Martin M. Musatov

An Argument for P=NP

Selmer Bringsjord & Joshua Taylor_

Department of Cognitive Science

Department of Computer Science

The Rensselaer AI & Reasoning (RAIR) Lab

Rensselaer Polytechnic Institute (RPI)

Troy NY 12180 USA

http://www.rpi.edu/_brings

{selmer,tayloj}@rpi.edu

version of 5.31.05

• blue = new material created in light of a particular commentator

• red = new material created in light of 2nd commentator (who claimed that we smuggle in

exponentially growing hardware)

• purple = latest additions due to our own further research and reflection

_We’re greatly indebted to Michael Zenzen for many valuable discussions about the P=?NP problem and physics

(simpliciter and digital), and to Jim Fahey for discussions about such physics and mixed-mode dual-diamond operators

in modal logic. The presentation of the core arguments herein to the Spring 2005 edition of Bringsjord’s graduate

seminar, Logic & Artificial Intelligence, and his guest lectures on P=?NP in the 2005 Formal Foundations of Cognitive

Science graduate seminar, sparked a number of helpful objections and suggestions, for which we are grateful. We’re

indebted as well to two anonymous commentators for trenchant comments. Though the two arguments herein (the

second of which seems to establish P=NP) are for weal or woe Bringsjord’s, Taylor’s astute objections catalyzed

crucial refinements.

The Clay Mathematics Institute offers a $1 million prize for a solution to the P=?NP problem.1

We look forward to receiving our award — but concede that the expected format of a solution is

an object-level proof, not a meta-level argument like what we provide. On the other hand, certainly

the winner needn’t provide a constructive proof that P=NP.2 Despite G¨odel’s recently discovered

position on the matter,3 the general consensus has certainly been that P6=NP, and many of those

brave, contrarian (and, alas, often confused) souls who have endeavored to show P=NP have

sought to take the beckoning route of exhibiting a polynomial-time algorithm for one or more of

the 1000 or so currently catalogued NP-complete problems. This is an exceedingly taxing (and,

at least hitherto, unproductive) direction to take, and we eschew it. We happily concede that

constructive success would have many practical implications, but we are more interested in the fact

of the matter than, say, whether many current cryptographic schemes can be compromised. Very

well; let’s proceed.

In logic and related fields we often speak about problems in purely abstract terms. For example,

we may declare a problem to be Turing-solvable, without giving any thought whatsoever to the

embodiment of a Turing machine able to carry out a solution.4 So we may for instance say that the

set C of composite numbers is Turing-decidable: that there exists some TM M such that, for every

n 2 N= {0, 1, 2, . . .}, with n given to M as input (suitably encoded on its tape), M produces (say)

Y iff n 2 C, and N otherwise. Such facts are routinely confirmed in the absence of even a stray,

evanescent thought about how M might or might not be embodied.

However, it’s well-known that TMs (and other purely abstract computers) can be built. In

fact, one such physical machine is processing the letters in the present sentence, as I (Selmer) type

them. We may not know for sure that every abstract TM Mi from the countably infinite set of

such devices can be physicalized to produce Mip

, but certainly we do know that for every physical

TM Mip

able to accomplish some computation, there exists a corresponding purely mathematical

TM that carries out the same computation (in the mathematical universe). This fact will prove

convenient below.

Another well-known fact, one we also find rather helpful, is that there are simple physical

processes not reflective of the mathematical structure of TMs and the like, which nonetheless solve

1See http://www.claymath.org/millennium. There are six other “millennium” problems; each of these is also

associated with a $1M prize.

2As many readers know, the history of the problem is littered with failed attempts to provide non-constructive

substantiation of the received view that P6=NP.

3His position is communicated in a stunningly prescient letter he wrote to von Neumann in 1950; this letter is

reproduced, in English, in (Sipser 1992). G¨odel, writing of course before the modern P=?NP framework, inquires

as to von Neumann’s thoughts about what is today known as the k-symbol provability problem. Let _ be a formula

of LI (a formula of first-order logic, or just FOL). We write `k _ provided there is a first-order proof of _ of _ k

symbols. G¨odel apparently believed that it might well be possible to answer questions of the form “`k _?” in linear

or quadratic time. When the set here is made explicit and configured so as to allow for encoding on a Turing machine

tape, it’s patent that it’s NP-complete. G¨odel was quite at home with the idea that as logic and mathematics

progress, machines would increasingly take over the “Yes-No” part of the enterprise. Any notion that G¨odel would

have embraced an argument by analogy from the undecidability of FOL to the perpetual intractability of the k-symbol

provability problem is utterly misguided: He writes: “It would obviously mean that in spite of the undecidability of

the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely

replaced by a machine.”

4An exactly parallel point obviously holds of all those incorporeal models known to be equivalent to TMs: register

machines, the _-calculus, abaci, etc. As more philosophically inclined readers will know, there isn’t consensus as to

what a physical instantiation of a mathematical machine is. However, given the orientation of the present paper,

we can rise above such turbulence. The fact is, a cornerstone of computer science is that idealized machines can

be physically realized: we teach computability theory because we presuppose this. For a sustained discussion of

the relationship between abstract machines, and theorems regarding them, and their embodied counterparts, see

(Bringsjord & Zenzen 1997).

1

some problems that are overwhelmingly difficult for TMs and their digital relatives. For example,

the Steiner Tree problem (STP) is known to be NP-complete (see e.g. pp. 208–209 of Garey &

Johnson 1979).5 Nonetheless, a simple physical process (termed an analog computation6) can

apparently solve it quickly. STP is the problem of connecting n points on a plane with a graph

of minimal overall length, using junction points if necessary.7 The physical process in question

can be described in English as a straightforward algorithm: Make two parallel glass plates, and

insert n pins between the plates to represent the points; dip the structure into a soap solution, and

remove it; record the answer. The soap film will connect the n pins in the minimum Steiner-tree

graph (Iwamura, Akazawa & Amemiya 1998).8 Building the structure and the solution (and the

container for the solution), activity usually termed pre-processing in analog computation, requires

steps linear in the size of n, dipping and withdrawing make two steps, and recording — the so-called

post-processing phase — is linear in n as well, so despite the fact that STP is NP-complete, the

physical process just described — let’s call it As — is apparently carried out well within O(nk), for

some constant k.

Figure 1: Solution to embodied Steiner Tree Problem with five points, found by soapfilm processing

by Courant & Robbins (1941). The same results are obtained by Dewdney (1984).

At this point some readers may report that, at least for them, ‘step’ here has no precise meaning.

They might say: “How is the process just described algorithmic? Why, for example, does it take

one step to add a pin? Doesn’t one have to measure the location (precisely!), drill a hole, fasten

the pin, etc? After all, the construction is a more-or-less continuous process in space and time.”

5STP is NP-hard when the metric is non-discretized, and NP-complete when the metric is discrete.

6Analog computers are nothing new, though they don’t get much air time these days. An elegant example is

Vannevar Bush’s famous differential analyzer, which solves ordinary differential equations. A nice discussion of the

analyzer (in connection not with Bush, but rather with Claude Shannon) can be found in (Earman 1986). A colorful

discussion of the speedup that can be achieved through analog computation is provided by Dewdney (1984), who

describes a series of analog computers, including something close to the soapfilm computer central to the present

paper, and who also in some sense pointed in at least the general direction of our argument, by writing:

Throughout the foregoing discussion of analog computers for small inputs I have dodged the important

issue of the feasibility of constructing such gadgets. Although each of the gadgets can be built and

persuaded to work, after a fashion, on small problems, it would be silly to suggest that one construct

them with serious computations in mind. Yet, considered in the context of an ideal world in which ideal

materials are available, each gadget works, by definition, exactly as described. (Dewdney 1984, p. 25;

emphasis ours)

One of the oldest discussions of analog computers is presented by Courant & Robbins (1941), who tinkered with

various wireframe-in-soapfilm analog computers, in connection with STP, and other problems.

7Just as we have the metaphor-clothed ‘Traveling Salesmen Problem’ (an NP-complete problem analyzed e.g. in

Lewis & Papadimitriou 1981), STP can be conceived as the problem of building a road system (possibly with

intersections outside the towns themselves) that connects n towns, where than system is of minimum length.

8As mentioned in note 6, additional descriptions of the analog soapfilm computation can be found, e.g., in (Courant

& Robbins 1941, Dewdney 1984, Fischler & Firschein 1987).

2

There are two reasons why this sort of objection fails. First, Turing machines (and their

equivalents) are subject to the same suspicions. After all, a Turing machine’s read/write head

must move from one square to the next, and each such move is a “step.” Furthermore, rest assured

that once a TM is embodied, it doesn’t immediately pass into the non-algorithmic realm. On

the contrary, embodied machines, though they run through “continuous processes in space and

time,” are behaving algorithmically. In addition, in Turing’s (1936) original paper on the halting

problem, he equates the behavior of the inanimate machine with the work of a ‘computist’ working

with ordinary paper and pencil at the level used to couch the aforementioned soapfilm computation.

The second reason the objection here is surmounted is given below, when the digital physics scheme

is invoked — a scheme according to which every high-level process corresponds to a low-level one

carried out by some Turing machine.

Returning to the soap process: Before starting to read this short paper, you were probably

positive that P6=NP. If you’ve now heard about it for the first time, does the soap process change

your mind? We didn’t think so. But please reason further with us.

First, some simple notation. Let’s refer to the physical version of the STP problem as B(STP)

(for emBodied STP), and the abstract version as STP. In addition, following usage above, we use

M with or without superscripts to refer to Turing machines, and Mp to refer to physicalized TMs

(with plain ‘M’ denoting abstract TMs). We refer to analog processes with variable A. Now here is

a na¨ıve proof, functioning as precursor to the more sophisticated successor given later, formalizable

in sorted9 first-order logic (FOL), that P=NP (where the predicate letter N is explained later):

The Preliminary, Na¨ıve Proof

1 9M (M solves STP in polynomial time) ! P=NP definition of NP-completeness

2 9A (A solves B(STP) in polynomial time ^N(A)) derivable, e.g., by existential introduction

from soapfilm process, i.e., As

3 9A (A solves B(STP) in polynomial time ^N(A)) !

9Mp(Mp solves B(STP) in polynomial time) digital physics; see below

4 9Mp(Mp solves B(STP) in polynomial time) !

9M(M solves STP in polynomial time) unassailable; see justification 3rd ¶ 5 P=NP 1–4 (full FOL derivation trivial)

We don’t hold that this argument is sound as it stands (that’s why the sophisticated successor

is coming, after all), but there is no question that the reasoning here can be certified as formally

valid (e.g., using an automated proof checker). The only question is whether the premises are true.

If they are, the problem is at long last solved in the affirmative. Are the premises true?

Line 2, note, isn’t a premise, but rather an intermediate conclusion; however, there are two

routes to this conclusion. As noted in the justification column, one possible inference to line

2 is from As, where this constant is replaced by the variable A, and existential introduction is

used.10 The second route takes account of what we regard to be self-evident: Surely As is just

the tip of the iceberg, with myriad analog processes out there in our physical universe waiting to

be discovered and harnessed (though presumably most will remain undetected for eternity). This

view can be derived from a sampling assumption, according to which a finding like As must be a

random sampling from some small proper subset of the set of all candidate processes available in the

cosmos. We don’t pursue this derivation herein. Interested readers should consult a parallel form

9E.g., 1 is short for 9x(A(x) ^M solves . . .).

10We assume for certification a natural deduction calculus, with rules for introducing and eliminating truthfunctional

connectives and quantifiers; a nice system of this sort for FOL is F, from Barwise & Etchemendy 1999.

For natural deduction in modal logic, consult (Konyndyk 1986).

3

of argument explored in theoretical physics (see e.g. Bostrom 2002), and should instantiate that

form in the present domain with additional samples (e.g., the various analog computers discussed

in Dewdney 1984).

We anticipate that some will be uncomfortable with the view that there exists a process A that

accommodates ever greater values for n. In light of this, we move now to the more sophisticated

of our two proofs: First, note that full specification of our proof in FOL does include universal

quantification over N, and a corresponding index for STP and B(STP), as for example in what

line 2, unpacked, becomes:

9A8n(. . .B(STP)n . . .) . . .

Now, it’s exceedingly hard to see how As cannot succeed on n + 1 if the minimal graph has been

found for n physicalized points. Whatever underlying principles of physics generate the graph in

the case of n surely can be employed to generate it for n + 1. Even if the physical laws governing

our universe are such that there is some point n+1 at which As fails, surely it’s logically physically

possible that this failure not occur.11 In short, it’s mathematically possible that there is a world w?

at which it’s physically possible that the underlying physics working so well on some initial interval

(e.g., 1–6) in our world w_, works for the entire countably infinite set.12

It’s easy enough to make the reasoning here more precise. Begin by abbreviating ‘A solves

B(STP)n,’ where A is some analog process, by S(A,B(STP)n. Next, relativize this locution to a

world, so that, for example, we know (by virtue of soapfilm tinkering in our world)

S(As,w_,B(STP)n), 1 _ n _ 6.

We now need to express the progression we have in mind more carefully. The idea, again, is that

as the size of the input grows, idiosyncrasies in the collection of physical laws governing the world

w in question may prevent the soapfilm process from yielding the answer — but we can always

be sure that if things work for n, in-principle adjustment will allow them to work for n + 1, and

so by induction the progression will work for all k 2 N. In our gedanken-experiment we simply

add to and modify the collection of physical laws so that the underlying physics that worked for

n − 1 works for n. We refer to this augmentation and adjustment by way of the _ function, which

yields a world preserving the underlying physics (least action, perhaps; see note 12) that worked

previously (in the world to the left of _), combined with what it takes to reach the next increment.

So, we have

11The double modal operator is key. While |=w 3p_ means in the standard formal semantics that _ is true at some

possible world w0 2 Wp ( W (where W is the set of all possible worlds logically/mathematically accessible from w,

and Wp the proper subset of W preserving the physical laws of w), and |=w 3_ holds iff _ is true at some world in

W, |=w 33p_ means that 3p_ holds at some world w0 2 W.

12Michael Zenzen has pointed out to us that the so-called Principle of Least Action is a prime candidate for

something that is at the core of what is carried over from world to world in order to reach to w? (for discussion of

these principles, see the remarkable Castigliano 1966). This principle would be what Jim Fahey has referred to as a

‘proto’-law of nature. It’s a profound waste of time to build gadgets that, in w_, compute ever larger initial intervals,

if the aim of such activity is to seek evidence that counts either for or against our argument: The conditions in

such seat-of-the-pants experiments are not controlled (even Courant (1941), when running his soapfilm experiments,

realized the need to idealize), and all our proof needs is truth at quite-removed w?, not our actual world.

4

S(As,w_,B(STP)n), 1 _ n _ 6

S(As, (w_ _ w2),B(STP)7)

S(As, ((w_ _ w2) _ w3),B(STP)8)

...

S(As, (· · · ((w_ _ w2) _ w3) _ · · · _ wm),B(STP)m+5)

...

Now we set w? to

X!

1

· · · ((w1 _ w2) _ w3) · · ·

and infer by the !-rule that

8nS(As,w?,B(STP)n).

The foregoing allows us to formulate a more formidable second proof that employs modal logic

(Chellas 1980, Hughes & Cresswell 1968, Konyndyk 1986). If we let 3p refer to physical possibility

in a manner that parallels the straight 3 of logical possibility from modal logic,13 then the modal

version of line 3 is

33p9A8n(A solves B(STP)n in polynomial time ^ N(A)) !

33p9Mp8n(Mp solves B(STP)n in polynomial time)

and this technique can be easily propagated through the original proof to produce the more circumspect

one. In this modal proof, line 4 becomes the key principle that if it’s logically physically

possible that a physical TM solve B(STP)n in polynomial time, then there exists (in the mathematical

universe) a TM that solves STPn in polynomial time. This principle would appear to be

invulnerable. Summing up, we have:

The Modalized Proof

10 9M8n(M solves STPn in polynomial time) ! P=NP definition of NP-completeness

20 33p9A8n (A solves B(STP)n in polynomial time ^N(A)) derivable by induction, the !-rule,

existential intro on As

30 33p9A8n (A solves B(STP)n in polynomial time ^N(A)) !

33p9Mp8n(Mp solves B(STP)n in polynomial time) possible digital physics; see below

40 33p9Mp8n(Mp solves B(STP)n in polynomial time !

9M8n(M solves STPn in polynomial time)) unassailable; see justification 3rd ¶

50 P=NP 10–40 (full FOL derivation trivial)

Please note that the modal version of our argument provides complete immunity from an objection

that the physical universe is finite, and that therefore no analog process can scale up through

all natural numbers as inputs for the minimal graph to be generated. The dominant view among

theoretical physicists appears to be that the theory of inflation (Vilenkin 1983, Guth 2000) holds

(which renders it likely that the universe is infinite). But we need not take a stand on the issue. All

we need is what follows immediately from the fact that the theory of inflation, whether or not true,

is certainly coherent: namely, that it’s logically physically possible that the universe is infinite.

13We assume a normal S5 version of the 3 operator.

5

By “digital physics” in the justification of premise 3/30, we have in mind the position that the

physical universe is fundamentally a vast physical computer — or, if you like, a computer composed

of computers, which are in turn composed of computers, and so on. This view has been recently

affirmed by Wolfram (2002), but Fredkin (1990) advanced the view long ago (and continues to

energetically defend it now), and Feynman (1982) seems to have embraced the view as well. Even

Einstein can be read as having affirmed the digital physics position. Whether or not the actual

world is fundamentally governed by digital physics, there can be no denying that there is a possible

world that is — and this weak fact is all that our proof presupposes. Though premise 3/30 refers to

physicalized Turing machines, most digital models in physics are based on cellular automata, but

this is of no matter: it’s well-known that every cellular automaton can be recast as a TM.14

Our argument shows that if P6=NP, digital physics is incoherent. Since it must be true that

all physical phenomena can in principle be modeled in information-processing terms of some kind,

P6=NP thus immediately implies, courtesy of our arguments, that hypercomputational processes

exist in some physical universes.15 If you believe, as many do, that hypercomputational processes

are always merely mathematical, and never physically real, you can’t be rational and at the same

time refuse to accept our case for P=NP.

Perhaps you do indeed refuse to accept the coherence of the digital physics view, and have no

qualms about in-principle physical hypercomputation. It was with skeptics like you in mind that

the predicate N( ) (for “normal”) was included in our proofs. While many are perhaps right to

point out, contra Wolfram and company, that some physical phenomena (e.g., those associated

with quantum mechanics) are so bizarre and complicated that they resist formalization in TM-level

computational models, the fact of the matter is that the analog process we exploit is a painfully

simple macroscopic phenomenon—as we say, a “normal” physical process. There are two important

features implied by normality in the present case.

First, the soapfilm process (and for that matter any of the many known analog processes that

yield speedup, e.g., the “string” computer: Dewdney 1984, Dewdney 1985) shouldn’t be treated

any different than ordinary physical processes interpreted to fall on the scalable digital side. We

can use an abacus functioning as a Register machine, or a model railroad system functioning as a

Turing machine, to see that we have on hand a process that, at least in principle, solves a problem.

When the abacus is correctly deployed to add 2 + 2 and hence leave 4 beads in the designated

location, we know that, assuming the physics to be preserved as we scale up, n + n presents no

trouble.

The second important feature purchased by normality is that it precludes any cheating with

respect to hardware. By definition, a guess for an NP problem is checkable in polynomial time.

Likewise, by definition, if exponential hardware is allowed, the check can be carried out in polynomial

time. In a non-normal situation, the underlying physical stuff can be imagined to grow even

at a geometric rate, and so a computer can in polynomial time “solve” problems that grow at a

14The transformation preserves polynomial-time processing, as cognoscenti know. For others, a sketch: Use an

n-dimension TM in which n is high enough to sufficiently represent the CA which is the universe. Let each cell of

the TM’s tapes represent a cell of the CA. The alphabet of the TM will contain some representation of all states for

the CA’s cells. The computation performed by the CA is finite, so the TM’s states are as well. It is known that the

transformation from multidimensional Turing machines to standard Turing machines is a polynomial transformation.

If the computation performed in each cell of the CA is in class P, the equivalent TM will be in class P.

15Physical phenomena that can be rigorously modeled only via information processing above the Turing Limit

(Siegelmann 1999, Bringsjord & Zenzen 2003) would be phenomena calling for hypercomputational machines. Just as

the class of mathematical devices equivalent to TMs is infinite, so also there are an infinite number of hypercomputational

machines. Examples include analog chaotic neural nets (Siegelmann & Sontag 1994) and infinite time

Turing machines (Hamkins & Lewis 2000). Other examples include analog “knob” TMs (Bringsjord 2001) and

accelerated TMs (Copeland 1998).

6

geometric rate.16 The soapfilm process leverages physical material in the standard way. We don’t

have a supply of soapy water assumed to grown exponentially as the number of pins increases. In

fact, the great irony facing anyone who claims that we are sneaking in exponentially increasing

hardware is that the empirical and arithmetical facts (e.g., see Dewdney 1984) indicate that analog

computation derives its power from the ability to handle larger and larger input while its core

process (happening after what we’ve called pre-processing) hums along at linear time on hardware

whose size grows in linear fashion.

The bottom line regarding normality is that the burden of proof is surely on those who would

maintain that the formal machinery of digital physics is in principle insufficient to model something

as straightforward as submerging nails in, and retrieving them from, a bucket of soapy water.

Postscript

A reader asks:

“Some rather smart people continue to feverishly search for object-language level confirmation

of the received view that P6=NP. Do you seriously maintain that this work is otiose? What if

you woke up tomorrow to find that someone had established, at the object-language level, what

people generally expect: namely, P6=NP?”

If we received this information tomorrow, and the proof checked out, we would be faced with

an antinomy, since our argument certainly appears to be sound — and the conclusion of a sound

argument comes no less highly recommended than the conclusion of a proof. Admittedly, this would

be an antinomy Bringsjord has imagined since the argument given above occurred to him, for the

simple reason that, intuitively, he is himself inclined to believe that P6=NP — while on the other

hand, again, there stands the argument in question, and there really is no denying its power. It’s

also possible that humans, not just us, but all humans, will forever fail to wake to such a proof,

for the reason that the question is independent of classical mathematics, as identified with some

axiomatic set theory cast in first-order logic. In this case, the future wouldn’t bring the result our

interlocutor asks us to imagine, but rather only, for eternity, meta-arguments on the issue. If so,

here is ours, given at the dawn of the coming dialectic.

References

Barwise, J. & Etchemendy, J. (1999), Language, Proof, and Logic, Seven Bridges, New York, NY.

Bostrom, N. (2002), Anthropic Bias: Observation Selection Effects, Routledge, New York, NY.

Bringsjord, S. (2001), ‘In computation, parallel is nothing, physical everything’, Minds and Machines 11, 95–

99.

Bringsjord, S. & Zenzen, M. (1997), ‘Cognition is not computation: The argument from irreversibility?’,

Synthese 113, 285–320.

Bringsjord, S. & Zenzen, M. (2003), Superminds: People Harness Hypercomputation, and More, Kluwer

Academic Publishers, Dordrecht, The Netherlands.

Castigliano, C. A. P. (1966), The Theory of Equilibrium of Elastic Systems and its Applications, Dover, New

York, NY.

16The cardinality of sets produced by successive application of the power set operator P grows geometrically, but

we can imagine 2n processors that share memory in which the input I = {i1, i2, . . . , in} is placed, each of which

is connected to a printer. Starting at i1 and working up in parallel, each processor does or doesn’t issue a print

command, depending upon whether the ik matches its unique identifier. In linear time P(I) is printed.

7

Chellas, B. F. (1980), Modal Logic: An Introduction, Cambridge University Press, Cambridge, UK.

Copeland, B. J. (1998), Even Turing machines can compute uncomputable functions, in J. Casti, ed.,

‘Unconventional Models of Computation’, Springer-Verlag, London, UK, pp. 150–164.

Courant, R. & Robbins, H. (1941), What is Mathematics?, Oxford University Press, Oxford, UK.

Dewdney, A. K. (1984), ‘Computer Recreations: On the Spaghetti Computer and and other Analog Gadgets

for Problem Solving’, Scientific American 250, 19–26.

Dewdney, A. K. (1985), ‘Computer Recreations’, Scientific American 253, 23–24.

Earman, J. (1986), A Primer on Determinism, D. Reidel, Dordrecht, The Netherlands.

Feynman, R. P. (1982), ‘Simulating physics with computers’, International Journal of Theoretical Physics

21, 467–488.

Fischler, M. & Firschein, O. (1987), Intelligence: The Eye, the Brain, and the Computer, Addison-Wesley,

Reading, MA.

Fredkin, E. (1990), ‘Digital mechanics: An informational process based on reversible universal CA’, Physica

D 45, 254–270.

Garey, M. & Johnson, D. (1979), Computers and Intractability, W.H. Freeman, New York, NY.

Guth, A. (2000), ‘Inflation and eternal inflation’, Physics Reports 333, 555–574.

Hamkins, J. D. & Lewis, A. (2000), ‘Infinite time Turing machines’, Journal of Symbolic Logic 65(2), 567–

604.

Hughes, G. & Cresswell, M. (1968), An Introduction to Modal Logic, Methuen, London, UK.

Iwamura, H., Akazawa, M. & Amemiya, Y. (1998), ‘Single-electron majority logic circuits’, IEICE Trans.

Electronics E81-C(1), 42–48.

Konyndyk, K. (1986), Introductory Modal Logic, University of Notre Dame Press, Notre Dame, IN.

Lewis, H. & Papadimitriou, C. (1981), Elements of the Theory of Computation, Prentice Hall, Englewood

Cliffs, NJ.

Siegelmann, H. & Sontag, E. (1994), ‘Analog computation via neural nets’, Theoretical Computer Science

131, 331–360.

Siegelmann, H. T. (1999), Neural Networks and Analog Computation: Beyond the Turing Limit, Birkh¨auser,

Boston, MA.

Sipser, M. (1992), The history and status of the P versus NP question, in ‘Proceedings of the 24th Annual

ACM Symposium on the Theory of Computing’, pp. 603–618.

Turing, A. M. (1936), ‘On computable numbers with applications to the entscheidung-problem’, Proceedings

of the London Mathematical Society 42, 230–265.

Vilenkin, A. (1983), ‘The birth of inflationary universes’, Physical Review D 61, 083507.

Wolfram, S. (2002), A New Kind of Science, Wolfram Media.

8