Hallucinated Abstract
I actually thought this up around sometime in Feb 2007; I had been reading Sipser’s Intro to Computer Science text, and hallucinated the following abstract while drifting off to sleep:
This paper presents an isomorphism between the set of problems in P and the Natural Numbers, and an isomorphism between the set of problem in NP and the reals. Using this isomorphism the properties of the equivalent classes P and NP are investigated. A property is found which holds for one class but not the other, thus P != NP. The isomorphisms are then used to prove that the Continuum Hypothesis is false because of the relationship between P and NP.
It’s pretty likely that this approach would have a fundamental flaw, but if so, I don’t have enough background to know what it is. Hopefully, I will be able to gain insight on the problem while here at University. Specifically, I’ll begin with the question: What is the cardinality of P?
How will it prove CH to be false? You still have to find a set that contains but is not isomorphic to P, and that is contained by NP but not isomorphic to it. How else can you disprove it?
Well, if P = Naturals, and NP = Reals, but several complexity classes are already known to exist between P and NP, then due to the hypothetical isomorphism, there must exist number sets between the Naturals and Reals, that correspond to the complexity classes between P and NP.
I should learn more about P vs. NP, but it’s just so adversarial.
P and NP are both of \Aleph_0 cardinality, because all programs are expressible in the language (0|1)*.
This was embarrassingly explained to me in the “Cardinality of P” post in comp.theory