-10
$\begingroup$

My understanding had been badly lacking in just what complexity theory was in the context of computer science. I thought it was abstracted to all mathematical problems applicable outside the realm of computation. Truthfully, I doubt I understand it. But seeing as how this is here to stay, here's an idea for a P=NP proof that is hopefully less embarrassingly off. The heart of the question being can NP problems be both solved in polynomial time and verifiable in linear time.

Take P to mean all problems that are solvable in polynomial time, and verifiable in linear time. Take NP to mean all problems that are solvable in non-polynomial time, and verifiable in P.

Problems exist that have been solved in P and verified in Linear time. Problems exist that have been solved in NP and verified in P. There exist solutions to problems in NP that are considered P.

Alright here's where it gets weird. Problems in NP can be solved in P, if a solution is found rapidly enough to be considered P. Such a problem in NP would be considered verified in Linear time if a correct solution was found in P. That would mean that for some problems P=NP (call this getting lucky). Problems in NP are not all solved in P, which means they are not verified in Linear time. This means P=/=NP. P=NP iff all NP were solved in P and verified in Linear, which is not the case.

/shrug That's my best guess.

$\endgroup$

closed as off-topic by Discrete lizard Apr 23 at 17:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ So if you could make it a rigorous proof, what would it look like? What I've shown is fundamentally sound. $\endgroup$ – Michael Barry Aug 24 '18 at 17:20
  • 1
    $\begingroup$ NP means “non-deterministic polynomial”, which is just a shorthand for “checking all candidate solutions in parallel, using polynomial time”. There’s no mention of “non-existence” in the definition of class NP. $\endgroup$ – Dmitri Urbanowicz Aug 24 '18 at 18:16
  • 1
    $\begingroup$ I'm sorry but this is just nonsensical. Nowhere do you use the defintion of either $\mathbf{P}$ or $\mathbf{NP}$, so your argument can't possibly derive any facts about them. Furthermore, you appear to be under the mistaken belief that "NP" means something like "not polynomial". If that were the case, we would have $\mathbf{P}\neq\mathbf{NP}$ by definition and there would be nothing to prove. And it is completely possible for both a set and its complement to exist. $\endgroup$ – David Richerby Aug 25 '18 at 11:08
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it is a purported solution to the P vs NP problem $\endgroup$ – Yuval Filmus Aug 25 '18 at 18:10
  • 1
    $\begingroup$ @MichaelBarry I see you tried to 'remove' your post with an edit. Please do not do that. We prevent deletion on questions with positively voted answers for a reason. If your concern is that your post leads others into wrong ideas, put a disclaimer at the top. If you no longer wish to be associated with this post, you can request that as well. $\endgroup$ – Discrete lizard Apr 23 at 17:31
4
$\begingroup$

There a lot of assumptions here that fall to "common sense" without scrutiny, but that's the point of rigor; it's the scrutiny that leads intuition.

Anyway, a number of your statements are vague and unproven.

  1. "By definition, everything in existence is in existence. This means nothing can't exist."

Whose definition? What are the consequences of this definition? We can't even prove that there's a set that contains all sets out there. Furthermore, how does this mean nothing cannot exist? If "nothing" is a word we use to describe the absence of objects, how does "nothing" not exist? Without harping too much on the metaphysics, these broad modes of reasoning and loosely connected ideas don't really say much about the problem but muddy the water with vague beliefs.

  1. "Therefore the concept of not or non, can’t exist, as this implies non existence. This means that Non-polynomial time problems can’t exist."

The negation of something (its NOT) and its non-existence (being "non") are two different things. For some proposition A, I can describe its negation ~A and have little trouble convincing myself and peers of its existence. Furthermore, what is the relationship between negation to non-polynomial time?

  1. "Existence can’t equal non-existence. Thus, P=/=NP. As a result, there is only P."

Where do you claim that existence cannot equal non-existence? I agree in broad, but I don't really see any steps leading up to it or its relevance to complexity classes.

In general, I think you have mixed up the negation of a proposition with the difference between complexity classes. We want to find out if the boundary between P and NP is arbitrary. If you want to prove that NP doesn't exist, then you might want to start by trying to prove that a general NP problem can be solved in P.

$\endgroup$
  • $\begingroup$ 1) What does it matter whose definition it is? Are you trying to argue that everything isn't everything? We're describing concepts. The concept of everything and the concept of nothing. I also just proved there's a set that contains all sets. That's the proof you're reading. $\endgroup$ – Michael Barry Aug 24 '18 at 19:27
  • $\begingroup$ 2) Are you trying to argue that negation isn't the opposite of what exists? The opposite of everything is nothing. Or is this incorrect? $\endgroup$ – Michael Barry Aug 24 '18 at 19:28
  • $\begingroup$ 3) Later I show that P=NP & P=/=NP both have to exist. However that can't exist at once, therefore they must exist separately. $\endgroup$ – Michael Barry Aug 24 '18 at 19:30
  • 1
    $\begingroup$ The definition matters since it's not widely agreed on. A definition is supposed to be precise and encompass the consequences of its claim; many would argue that yours isn't really precise at all. I even agreed that in some broad sense, everything could be everything However, there is blatant proof naive set theory is flawed, and based on its construction, the structure that contains all set cannot be itself a set (since it cannot be determined if it contains itself) $\endgroup$ – dweeby Aug 24 '18 at 21:00
  • 1
    $\begingroup$ I forgot to address this, but a few people have: NP and EXP are two different classes. Based on your faulty basis of reasoning, I cannot say your proof for P and NP's mutually exclusive existence is correct, rigorous, or valid. You don't really use any deductive rules or inferences that are necessarily true. If you make a proof that uses proper structure and doesn't rely on vague notions of "existence" (which aren't rigorously defined), I can examine a proof. Until then, you're just taking shots in the dark $\endgroup$ – dweeby Aug 24 '18 at 21:04
3
$\begingroup$

This is not a proof of P != NP nor does it approach one.

Among other issues, we have very similar classes to P and NP where they are in fact equal. For example, we know that PSPACE = NPSPACE by Savitch's theorem https://en.wikipedia.org/wiki/Savitch%27s_theorem but nothing in your suggested proof uses at all that one is distinguishing time from space.

You appear to be under a misconception that P and NP have to do with some sort of broad notion of "existence"- this is not the case. While the definition of NP does talk about the existence of specific types of proofs, that's not the same thing.

"However, there also needs to exist a reality where paradoxes are true because paradoxes are included in everything. Therefore, there are 3 realities. One where P=NP, one where P=/=NP, and one where both exist at once. The other can't exist because both p=np and p=/=np are false. Making true nothingness."

I'm not sure what you mean by "reality" here, but it sounds like it has little resemblance to anything connected to theoretical computer science. It is possible that P != NP is independent from the standard set of mathematical axioms of ZFC, in which case one could construct models where P != NP or where P= NP, but that's very different from what you appear to be talking about.

"By the way, this is also The Theory of Everything"

The Theory of Everything is an idea about physics. P != NP is an idea in math/theoretical computer science. By nature they cannot be the same thing. One is a description of our specific universe, and one is a proof about an abstract mathematical fact. If one thinks this is somehow the "Theory of Everything" then it is likely that one doesn't understand what we mean by a Theory of Everything or what we mean when we talk about a mathematical proof.

Speaking more broadly, let me give some general advice:

First, if you want to attack a problem, make sure you actually understand the problem in question. There are a lot of good introductions to theoretical computer science out there; my preferred book is Moore and Mertens, but others will have other texts; many people like Sipser "Introduction to the Theory of Computation."

Second, don't expect that you are going to solve some well known open problem and certainly don't expect that you are going to solve it in a paragraph. If you are wondering if you have single paragraph answer to any famous open problem that myriad very smart people have thought of, the answer is definitely no. In general, the vast majority of mathematicians and computer scientists don't go around solving the very biggest problems in their fields, and don't expect to do so. What we do spend time on is solving little, approachable problems, and we occasionally nibble away at the big ones, hoping to make enough progress that eventually someone will put everything together to solve the big ones. If you go into any of these areas hoping to solve the largest problems, you will almost certainly end up disappointed.

$\endgroup$
  • $\begingroup$ I do appreciate the advice Joshua, and you are correct in that I don't know where to put it, because it is so broad reaching. That's the nature of everything. I will look into Savitch's Theorem and get back to this, but I do think I'm onto something here. The problem isn't with the the structure of the theory itself but with the overall completeness (which is hilariously enough the point of the problem, go figure). Let me think on this and get back to you! $\endgroup$ – Michael Barry Aug 24 '18 at 20:03
  • 1
    $\begingroup$ You appear to be using a lot of terms where you still haven't learned what they mean. "EXPTIME" (or just "EXP") contains EXPSPACE, so your "EXPSPACETIME" is just "EXPTIME"- - please try to sit down with an actual computational complexity book. These terms have meanings and relations, and you cannot just figure out what they are or make up your own meanings without having some detailed exposure. $\endgroup$ – JoshuaZ Aug 25 '18 at 16:54
  • 1
    $\begingroup$ @JoshuaZ Actually, it's the other way around: EXPSPACE contains EXPTIME, because a Turing machine can't use more space than time. But a halting TM that uses exponential space could use doubly exponential time, so we can't guarantee that a problem in EXPSPACE is in EXPTIME (singly exponential). $\endgroup$ – David Richerby Apr 23 at 16:15
  • $\begingroup$ @DavidRicherby Yes, thank you. You are completely correct. $\endgroup$ – JoshuaZ Apr 24 at 16:37
3
$\begingroup$

You also don't seem to know what NP is. NP is not non-polynomial time, but nondeterministic polynomial time, big difference, since there are complexity classes like EXP, which are proven to be non-polynomial time.

Edit: removed wrong part

$\endgroup$
  • $\begingroup$ Sorry I was arguing this in multiple locations and forgot to update the computer science part. Silly me. I updated the proof. $\endgroup$ – Michael Barry Aug 24 '18 at 19:31
  • 2
    $\begingroup$ Actually, we don't know that $\mathbf{EXP}\neq\mathbf{NP}$. But we do know that $\mathbf{NP}\subseteq\mathbf{EXP}$ and, by the time hierarchy theorem, $\mathbf{EXP}\subsetneq\mathbf{2EXP} = \mathrm{DTIME}[2^{2^{n^{O(1)}}}]$. $\endgroup$ – David Richerby Aug 25 '18 at 9:10
  • $\begingroup$ I edited. Thank you all for your input. :) $\endgroup$ – Michael Barry Aug 25 '18 at 16:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.