Harvey Friedman, in his remarkable paper Finite functions and the necessary use of large cardinals, Ann. of Math.. 148:803-893, 1998, and in a technical report, Applications of large cardinals to graph theory, Dept. Math. Ohio State Univ, presents numerous combinatorial statements with clear geometric meaning that are proved using large cardinals and shown to require them. By slightly extending some of Friedman’s results, we construct an infinite class of structurally similar statements which can be proved using the same large cardinals but also can be proved from the statement “subset sum is solvable in polynomial time.” This curious connection between the P vs. NP problem and the theory of large cardinals seems to suggest that P = NP is either false or otherwise not provable in ZFC. We give the latest version of this discussion below,. This work appears in arxiv.org/abs/1907.11707v2 and in the refereed journal, Journal of Combinatorics: Combinatorics in ZFC limbo. JOC Vol. 10, Num. 3, 579-593, 2019. The JOC volume is dedicated to my UCSD colleague and good friend, Jeff Remmel (1948 - 2017). Likewise, I dedicate the paper attached below to Jeff. |
||
ON THE DIFFICULTY OF PROVING P=NP IN ZFC | ||
Jump free condition: the heart of all search algorithms. |
||||
Information flow in a bureaucracy: key to ZFC independence. |
||||
Multiverse-like properties that challenge mathematical physics |
||
An Elementary Discussion (very little mathematics) |
||
Physics develops by combining mathematics with experiments and interpretations of what it all means (a story). The story suggests new concepts which often call for more sophisticated mathematics, stories and experiments. Physicists and philosophers of science have expressed concern about this process "breaking down" when faced with concepts such as multiverses and string theory landscapes. We take a more naive, but not trivial, approach here. We construct mathematical models which have the basic features of a multiverse: something that defines an infinity of universes, possible states of these universes and properties of the multiverse itself. These models can be called "toy versions" of multiverses because their mathematical theory is simpler than that needed for multiverse theory or string theory. We show, however, that even these toy versions give rise to natural mathematical questions that are provably beyond the range of mathematical physics. We first give an admittedly silly "elementary discussion." However, this silly version leads naturally to the conjectures that will stump mathematical physics. |
||
Rooms, tunnels,labels: Each room in Figure TL has a number or label beside it. A label z on a room (x,y) tells you that, by starting at (x,y) and following tunnels, it is possible to find a terminal (dead end) room (x',y') with "lattice-exit distance" z =min(x', y')). Moreover, z is the minimum such lattice-exit distance to be found in this manner. For example, the room (7,9) has label 2. By inspecting Figure TL, you can see that the terminal rooms reachable from (7,9) are the rooms (2,3), (4,3), and (5,8), with lattice exit distances 2, 3, and 5 respecively. The minimum of these terminal lattice exit distances is 2, so (7,9) has label 2. A universe: We think of the 10 by 10 lattice of Figure TL as a "universe" with structure and rules for exploring and computing things. For example, if you are an inhabitant of this universe, you might be placed in a room such as (7,9) with label 2 and asked to explore to find the promised terminal room that is distance 2 from the lattice. You then bring back (going reverse direction in the tunnels) a list of the rooms on this path (i.e., (7,9), (2,8), (1,6), (2,3)), and display it on the wall of room (7,9). Lets call this list-making task the "basic TL task." Imagine that you are placed another room to repeat this basic task. For example (5,6) or (8,7). Room (5,6) has label 3, so you return with the path (5,6), (4,3). Room (8,7) has label 2, but you have aleady found a path to a terminal distance 2 room. In such a case you are not required to repeat the basic TL task at room (8,7). Because of this no repeat condition, if you go through the rooms (x,y) of Figure TL in any order, the number of times you will have to do the basic TL task is the number of elements in the set {z | z < min(x,y)}. This set is called the set of significant labels for the rooms and tunnels of Figure TL. Checking out Figure TL you will see that this set is {2,3}. Multiverses: Imagine Figure TL (without the labels) extended so that the axes are all non-negative integers, N = {0, 1, 2, ... }, instead of just {0, 1,..., 9}. Such an infinite collection of rooms and tunnels is what we call a multiverse M. There are infinitely many possible multiverses M. Given any finite subset E of N, such the set E={0, ..., 9}, we can restrict the edges and tunnels of M to just those with axes E (as in Figure TL). This restriction process is how the multiverse M creates its collection of universes. |
||
Figure TL Terminal Labels |
||
What we will show: In terms of our discussion above, our program is to define and analyze multiverses M, where each such multiverse is an infinite collection of Figure TL - type universes. Similarly we are going to define "SL-type" multiverses. For each multiverse, we will prove a theorem that states that there are universes with arbitrarily large, nicely shaped ("large cubical") subregions with very few significant labels (less than 4 for the 2 dimensional problem). Our large-cube theorems for the cases TL and SL are proved using mathematics that extends the existing ZFC axioms of math (see Wikipedia). In addition, for SL it will turn out that we must use ZFC+ mathematics. None of the mathematics currently in use by physicists can prove the large cube theorem for SL. |
||
For the multiverses TL and SL see the article Lattice Multiverse Models . For a discussion of computational issues for the string theory landscape see On the computation of non-perturbitive effective potentials in the string theory landscape. (For an overview, General Conclusions start on p. 27). |
||
Multiverses and Large Cube Theorems (a solid discrete math course needed) |
||
All of the above depends upon the important work of Friedman, Applications of large cardinals to graph theory . This latter paper depends in part on Friedman's paper, Finite functions and the necessary of large cardinals, Annals of Math., Vol. 148, No. 3, 1998, pp. 803-893. For discussion of a simpler multiverse PL see Proof of Large-cube Theorems for Multiverse PL ( pdf). |
||