I am inclined to consider that CH is irrelevant with regard to P vs NP, although Choice might be a concern somehow.

I say that with respect to CH because the ordinary models of computation are pretty much confined to the denumerable and rational terminating interpretations of reals. That functions (and all the predicates) are not denumerable, along with undecideability, does not require a commitment with respect to CH as far as I can tell.

I hope it is that simple.

With regard to P vs NP, there are odd situations in practice with regard to how some presumably NP hard worst cases can still yield significant quantities of actual cases to useful heuristics. I think it is this sort of thing that leads Knuth to surmise that eventually (in the limit?) P = NP will arrive. I worry that he's swimming against the tide, but ... Knuth.

With regard to axiomatic (not necessarily set) theories, if we have an axiomatic system sufficient for recursive function theory, then the more-relevant consideration might be the Church-Turing thesis. P vs NP might not be independent of that, and we get to deal with CT being a thesis, not a theorem :).

Dear Dennis,

>>>I hope it is that simple

Unfortunately I don't think it is. If you have been following along in this thread, I have been having a discussion with Jaykov re: the consistency of ZFC.

https://www.researchgate.net/post/Do_you_know_that_great_mathematician_Georg_Cantor_was_schizophrenis

It would appear that the argument of independence of CH from ZFC is really simply masking the fact that ZFC is inconsistent. Although there is only one degree of inconsistency (maybe there is a Cantorian multiplicity of degrees of inconsistency??) but there are multiple reasons for inconsistencies with multiple infinities probably being the biggest offender.

In fact the Diagonal Method (DM) is a paradox that there are different sizes infinities. Without DM there would be no CH. There is no other definition of cardinality (size) then DM, so without proceeding any further it seems clear that even there is no mathematical basis (i.e. a model of ZFC ) to support a proof of P vs NP (in CS cardinality is defined by DM and also is known to have a relativization barrier) so in effect CH and P vs NP suffer the same issue. If fact I would suggest given the even to prove something like FLT, you would have to create a new model of mathematics outside of ZFC to do that.

Regards,

Jim

Jim Moore The question you asked is about P vs NP and it doesn't matter whether CH is independent of ZFC, whether ZFC is consistent or not. None of that. The conversation on the other thread does not apply here nor does the mental state of George Cantor, Darwin, Kurt Gödel, you, or I.

I guess you are allowed to hijack your own thread, but it would be nice if you addressed the actual question that you asked.

Dear Dennis,

The question is about the unsolvability in ZFC of two open questions CH and P vs NP and the parallels of unsolvability between the two. Based on established results (independence of CH from ZFC), this logically leads to a bifurcation of possibilities that remains open for the specific reason that either :

A.) ZFC is inconsistent and any answer is possible or

B.) ZFC is consistent but unable to model basic objects with cardinality in P.

This "ZFC independence" bifurcation means there are only two possibilities to address. Although how this bifurcation effects CH as opposed to P vs NP is somewhat different, both are unsolvable in ZFC because at the most fundamental level there is an inability to model transfinite classes in P.

Perhaps the question is a bit deceptive as it assumes a certain level of understanding of the model theory. The question does not make it explicit, but it is understood that "independence" of CH from ZFC is indistinguishable from inconsistency of ZFC. This is part and parcel of the bifurcation above.

This is actually a very well defined question and on reflection think you will see that I have not really hi-jacked the thread as much as made assumptions about the reader understanding of model theory.

Regards

Jim

Jim Moore Peter Breuer I am aligned with Peter on this. P is a complexity class, not a set theory. It is about abstract computable functions independent of their formulation. The functions in P have algorithms the best of whose performance is a polynomial for time on a measure of the operand (such as length or size). The standard form is with respect to Turing Machines that provide an algorithm for the function. There is more to consider, such as encoding matters, but that is how computational complexity is grounded.

In this context, NP (non-polynomial) consists of algorithms in P that verify the result for a given operand of some computation. That is, the computation of the result might not be in P, but a verifier of the result is. Note that P must be a subset of NP. The important open question is whether the intersection of P and NP is NP.

This has nothing to do with set theory in its transcendent glory. All you need to consider is all (constructive) functions on the denumerable finite ordinals.

In any case, there are well-known problems in NP for which there is no known P formulation of the related function. If Boolean satisfiability (in NP) were found to be in P, various problems reducible to satisfiability would also fall into P. CH just doesn't matter here.

Hi Peter,

>>> What is "P" that one can "model transfinite classes in P"?

P is the P in P vs NP.

https://www.claymath.org/sites/default/files/pvsnp.pdf

P is generally problems solvable in Polynomial space (or time). This is clearly less than Exponential which the minimum is 2^N (Cantor's aleph1 and N size of the data set).

ZFC apparently lacks anything to model an object of cardinality c aleph0>>What does it even mean to "model transfinite classes"?

V=L is the constructability model of ZFC. This is an inner model of ZFC. It is a transfinite model because the iteration never ends unless it is a limit ordinal.

>>>>Never mind what the word "unsolvability" is supposed to mean! What!

The CH independence of ZFC result has two possible conditions which I coded as "unsolvable":

unsolvable = independent (logical) or inconsistent. (standard model theory definitions)

Regards,

Jim

Peter,

The focus of most of my work is to reconstitute a consistent model of set theory capable resolving P vs NP which basically amounts to identifying the cardinality furcation in set theory and relating that to a computational model and the related furcation of computational complexity classes. It did not take long to figure out that ultimately ZFC is a broken and inconsistent theory. The independence of ZFC from CH is I believe a symptom of this inconsistency.

Jaykov Foukzon treats this much more formally than I can, so I only strive to find out what is broken and how it fix it.

http://www.journalrepository.org/media/journals/JAMCS_69/2018/Feb/Foukzon2622017JAMCS38773.pdf

>>>> you would be making a mistake of grammatical and semantic category because you would be comparing Exponential, which is a (countable) set of problems, with 2^N, a cardinal, which is a class of sets. Those are different kinds of things, like pigs and the colour blue.

The association of transfinite cardinality and asymptotic computational complexity is not a trivial affair, but at the same time I am by no means the first to make this association. Lance Fortnow identifies the “Diagonal Method” (see Section 4.1) as one of the first approaches to attack P vs NP.

https://www.researchgate.net/publication/220423686_The_Status_of_the_P_versus_NP_problem

By now it is well understood (since 1975 Baker, Gill and Solovay) and accepted that there is a relativization barrier and that the Diagonal method cannot be used to resolve P vs NP. The question that arises immediately in my mind, “ Does the relativization barrier have anything to do with CH and the independence from ZFC?” What is even more interesting why Theoretical Computer Scientists don’t seem to ask the same question? The situation has been described to me as one in which limitations of the Diagonal Method are recognized, while at the same time asserting that DM is the (only) definition of cardinality and even more DM is freely used in other CS proofs.

I have constructed what I call the “Computable Universe” (CU) as an extension to NBG based on a constructability meta-model.

https://www.researchgate.net/publication/331544505_ComputableUniversePneNP_Preprint2019Mar5

I also constructed a system theoretic sequential specialization of the standard Touring Machine (see Cook definition of P vs NP problem) that is directly associated with the set theoretical CU. Of course this is not ZFC; I had to resolve inconsistencies.

For the purposes of this discussion I would assert that for Con(ZFC) there exists a relevant isomorphic relationship between a set theoretic model and a sequential touring machine (STM). Within the scope of asymptotic computational complexity, cardinality is a proxy that should be capable of segregating P from EXP (a member of NP).

A fundamental problem is that there is no model of Con(ZFC) capable of capturing CH. As I pointed out earlier, the models for aleph0, aleph1 are almost trivial which leaves with a lack of a model for any intermediate cardinality.

>>>>So that makes no sense and the one-point correction also makes no sense. Please fix.

I don’t know if the discussion above clarified any of the confusion?

>>>It would also be helpful if you mean independent to say independent, not unsolvable.

Unsolvable means the logical disjunction of { inconsistent , independent }.

The bottom line here is that it would appear that the independence of CH from ZFC is tantamount to a proof that ZFC is inconsistent something that Jaykov has already proven but we now have much more intuition about why.

Regards,

Jim

Peter,

Am I to assume you have nothing more substantive to say on the subject other than spelling errors? In as much as you are have not made a counter argument, I have to assume you simply do not know.

It is clear that the vast majority of mathematicians will not publicly contradict the dogma of the consistency ZFC even though in the case of ZFC+CH inconsistency and independence are indistinguishable. ~Con(ZFC) is the common thread in unsolvability of CH and P vs NP!.

Regards,

Jim

Jim Moore Unsolvable means the logical disjunction of { inconsistent , independent }.

That seems to be nonsense, since there are no unsolvable questions in an inconsistent system - everything is provable. I suspect that the Paris-Harrington result of something that is true (not independent) of PA and unsolvable in PA might created problems for that disjunction also.

I don't understand the introduction of "Touring" since I believe I'm the only one who introduced Turing and Church-Turing here. Did I misspell Turing somewhere?

Oh wait, I found it in reference to Cook.

Until this thread directly addresses P vs NP as separate from CH, I have no further observations here.

Dennis Hamilton,

Dennis Hamilton>>>>That seems to be nonsense, since there are no unsolvable questions in an inconsistent system - everything is provable.

Thanks for your answer, however I think you interpretation is inconsistent. You have asserted that “!unsolvable = provable” which is inconsistent with my prior definition. In fact you have implied a self-referential meaning to my definition.

Jim Moore >>>>Unsolvable means the logical disjunction of { inconsistent , independent }.

I consider either item above a condition of unsolvability and inadequacy of a model M.

I think the nonsense you refer to is of your own making by assuming “!unsolvable = provable”.

Regards

Jim

Dennis Hamilton>>>>>Until this thread directly addresses P vs NP as separate from CH, I have no further observations here.

Dennis,

I'm pretty sure that the intent of the question was to ask if con(ZFC) implies independence of CH has any bearing on the inability to solve P vs NP.

The independence results is essentially a statement about the strength of the model M for constructability V=L. In ZFC it is understood that natural numbers and the Power Set(X) both exists, the the question boils down to proving C with cardinality between these two established cardinalities.

Computability is a stronger form of consistency than simple constructability. So it is natural to ask why :

" If a standard model of constructability V=L from ZFC that can not determine CH , should it be able to determine P vs NP which requires a stronger model of computability?"

I guess if you believe that CH is independent of P vs NP, then you must believe that there is some other theory than ZFC that can be used to determine basic computability to determine P vs NP. Is this new model to solve P vs NP independent of ZFC as well?

Regards,

Jim

Dear Jim Moore.Pay attention. This guy Peter again babbles the topic with completely inadequate comments.

>objection to my mathematical analysis

Dear Peter. You "mathematical analysis" is a babble and nothing more since you

misunderstood basic notion of set theory and arithmetic.

???

I thought I responded to this before but I don't see it.

This is very simple. CH has nothing to do with P ?= NP. P ?= NP is about arithmetic and computational complexity. But inside arithmetic.

Gödel established that a system strong enough for formalization o arithmetic was either incomplete or inconsistent. That proof does not depend on CH. That is, we don't have to know the cardinality of all the functions on N, we just know they are uncountable.

The (reachable?) computable functions are necessarily expressible in the system, so there cannot be more than a subset of denumerable well-formed expressions of functions. It is among those that expressions are assigned to complexity classes.

The question is whether or not ones that are determined to fall into NP always have equivalent expressions in P (i.e., P = NP). CH is irrelevant, whether or not it is independent in the particular system. It is a red herring to introduce it into the P ?= NP question. The (non-)independence of CH with respect to the system just doesn't matter. Sufficiency for arithmetic and expression of arithmetic functions is what matters.

Peter Breuer

I think we're forgetting that there are at most denumerable computable functions on N, because they have to be written down in finite expressions over a given theory that is strong enough for arithmetic. And the set of all finite strings over a fixed alphabet is denumerable. So we don't need to know what the cardinality of the set of all functions over N happens to be.

That's how I mean CH is not a consideration. Even though we might be concerned about the existence of the set of all functions over N, and what the cardinality might be, it doesn't enter into P ?= NP because of the computability constraint. That's not a tight bound but it is sufficient to establish that CH is not a factor.

Well, the limitation on programs is sufficient to confine P ?= NP and not have to be concerned about CH.

1. Also, the correspondence of programs to functions is not a bijection. There are many programs that correspond to the same function, although the equivalence of two programs is generally undecidable. It is this multiplicity of programs that makes P ?= NP a meaningful question. It is all about computability, and this limitation does not involve CH. That's my point. Tying the two together as in the title of this discussion is a red herring.

2. The Axiomatic Set Theory in the framing of the question also presumes more than required for systems strong enough for arithmetic. One can clearly represent arithmetic (i.e., PA on N) in set theory, starting with the von Neumann ordinals, for instance. That's painful and a difficult way to get to computability because it involves constraint of function to a denumerable domain and that condition has to be honored everywhere in the formulation. And P ?= NP is still about computational complexity and classes of complexity. So we're back to the preceding (1) anyhow.

3. Computational complexity was originally related to Turing Machine computations, as I recall, so that makes computation rigorous even though not particularly appealing for informal purposes. Instead, we talk about asymptotic cases, using Big-O, Big-Omicron, Big-Theta, etc. The counting involves the cases in the expression of a function and the number of certain operations that arise for a given argument value.. That's how we get to Boolean satisfiability being O(2^n) when accomplished by enumeration of the possible assignments of n variables. That's the poster child for P ?= NP determination. If satisfiability is in P, there are many other cases that fall into P along with it.

Dear Jim Moore. Of course P.Cohen proved nothing, since ZFC is inconsistent.

Only the blind can't see it. Dear Peter one of them, since this guy never read P.Cohen handbook.

Jaykov Foukzon exactly where does Paul Cohen make a claim that ZFC is inconsistent? In his _Set Theory and the Continuum Hypothesis_, he relies heavily on ZFC and gave proofs that C and CH are each independent of ZF. That does not strike me as a support for ZFC being inconsistent. This is different than ZF (and ZFC) not being provably consistent.

Perhaps Scott Aaronson doesn't think the question I posed is quite so silly:

https://www.academia.edu/14192801/Is_P_Versus_NP_Formally_Independent

Quoting Aaronson from the bottom of page 1:

Attitudes toward the last question have shifted over the past fifty years. In G¨odel’s famous 1956 letter to von Neumann (translated in [60]), where

P vs. NP was first posed, G¨odel apparently saw the problem as a finitary analogue of the Hilbert Entscheidungsproblem 2

2 The Entscheidungsproblem asks for a procedure that, given a mathematical statement, either finds a proof or tells us that none exists.P = NP asks for an efficient procedure that finds a short proof. In one sense, however, P vs. NP is not a finitary analogue of the Entscheidungsproblem. For once we require all branches of a computation to halt eventually, the‘nondeterministically recursive’ languages are just the recursive languages themselves, not the recursively enumerable languages.So the distinction between finding and verifying a bounded-size object is one that doesn’t exist in the recursion-theory world.

In what is perhaps a naive appraisal of the question, P vs NP when viewed from an optimality standard point asks "is there is a way to selectively trim well-ordered solutions so that combinatorial (i.e. exponential ) growth is avoided?" Or alternatively, "when faced with combinatorial brute force requirements to expand all possibilities, does a solution exist to avoid the full brute force solution?"

I would argue that while exponential growth well-ordered solutions are iff related to unordered input data sequences.

To trim the solution space would require some apriori knowledge about which combinations are optimal. If this were possible then we have violated the proof of the Entscheidungs problem. Simply put it is impossible to know which paths to trim and therefore the full set of combinations must be exercised and there is no way to lower the complexity below EXP.