/sci/ - Science & Math

[Anonymous No.9539037]

latest version of the proof

[Anonymous No.9539049]

this is super cringy. you're not going to prove the biggest unsolved question in computer science on a single sheet of paper with help from a bunch of 20 year olds on 4chan. Just give up.

[op No.9539051]

>>9539049
The proof is 10,000% valid, though.

[Anonymous No.9539060]

>>9539051

I'm 10.000% sure you missed something. I can't be bothered to check because I get confused trying to parse all this autism wording

[Anonymous No.9539062]

>>9539051
If it's valid send it to the Clay Mathematics Institute

[op No.9539063]

>>9539062
>if

did you even read the paper, bro?

[Anonymous No.9539069]

>>9539063
Then send it to the damn institute and become a world genius and push science forward instead of just posting it on 4chan.

[op No.9539080]

>>9539069
You have to have your paper peer reviewed before they look at it. You are my peers. Review it!

[H No.9539096]

>>9539080
It's shit.

[Anonymous No.9539099]

>>9539037
There is no need to create new threads, you retarded redditor.

[Anonymous No.9539105]

>>9539037
>For this proof, presume "naturals" are 64 bit unsigned integers
>Let the decision problem be "Given unordered list A and natural KEY as input, is KEY not the valid power key of A?"
If the number of possible naturals is bounded by a constant (2^128), how can this problem be in NP?

[op No.9539108]

>>9539105
The size of A, that's how.

[op No.9539111]

>>9539105
Both A and KEY are inputs, though encoded as a binary string before being parsed

[op No.9539114]

>>9539105
I'll clarify that point, thanks!

[Anonymous No.9539118]

STOP CREATING NEW THREADS, PLEASE. POST IN THE OLD ONES, WHAT THE SHIT MAN

[Anonymous No.9539119]

>>9539037
>Let the decision problem be "Given unordered list A and natural KEY as input, is KEY not the valid power key of A?"
Okay, so if I give you a specific KEY, how do you propose to verify the answer to that question in polynomial time?

[Anonymous No.9539120]

>>9539080
okay, I peer reviewed it. Here is my counterpoint

>consider a turing machine which is able to deconstruct KEYs and valid power keys at the God level
>you considered it, so it absolutely exists
>it can solve any KEY that is solveable
>therefore it can solve your key
>assume it can also travel through time so it's not constrained by polynomial time
>so by the way it also does that
>P = NP because God can solve any problem instantly

this is basically what you wrote, but the opposite

[Anonymous No.9539125]

>>9539120
lol kek

[Anonymous No.9539143]

>>9539037
Seems legit so far. Post it on http://vixra.org/ so people have a better chance of taking you seriously.

[op No.9539167]

>>9539143

posted!

[Anonymous No.9539188]

>>9539167
I don't think your proof is sound, but I like this picture, thank you for posting it OP.

[Anonymous No.9539191]

>>9539167
Link?

[Anonymous No.9539215]

>>9539037
Repeating my point from last thread (unfortunately I didn't have time to explain it in detail):

So, OP, we come at last to the crux of the matter. There don't seem to be any serious technical mistakes with this proof (just a few minor ones that don't really affect anything); all that remains broken is your fundamental misunderstanding of the problem, which keeps the proof from working.

>Because A is unordered [...] all deterministic Turing machines that decide the problem must compare [...] the sequence of 2^n elements
This does not follow. What stops me from finding a clever shortcut by analyzing X, rather than analyzing PS(x) directly?

It is true that if I write an algorithm that (1) computes PS(x), lazily or otherwise, and then (2) tries to scan PS(x) by in-order traversal, this will take Ω(2^n) time. But that does not apply to algorithms that try to work with X directly, and you have not proved that no such algorithm can exist.

There are a few minor things wrong with your proof, but they are easily fixed. This is the big one.

[Anonymous No.9539216]

>>9539037
What does it mean to "fold over the sum operation"? Your clarification doesn't help whatsoever, you need to actually learn at least some naive set theory so you can make it clear what you're doing. It seems x is a finite set whose elements are natural numbers. You then introduce what I assume is the powerset of x, but it isn't at all clear how you are ordering Px, since its elements are not natural numbers but sets of natural numbers. If you're saying that we should produce a new set whose elements are natural numbers by summing the elements of the subsets of x, you should be aware that this set could be strictly smaller than Px, since different subsets of x can have the same sum.
You're misusing the term "well ordered", which has a mathematical definition already -- you should talk about the order inherited from the naturals, but again this only applies to sets whose elements are all natural numbers.
The XOR operation is typically defined for only 0 and 1, or "true" and "false", you haven't defined what you mean by the XOR of two general natural numbers, and I don't see what this has to do with ordering anything.
You claim that ordering A (wasn't this x a moment ago?) "invalidates the power key of PS(A)", but you haven't proven that. Indeed, you haven't really defined what that means!
You then finish by claiming that it is impossible to solve this problem in polynomial time, but aside from the fact that your problem isn't well defined as far as I can tell, you haven't proven this claim. You are assuming a solution must go through every element of this list and order it, but that might not be so. You don't know how a potential polynomial algorithm will work. For example, you could make similar claims about deciding whether a number is prime, because you have to go through and check if it's divisible by all smaller numbers, but primality testing CAN be done in polynomial time, just not by trial division.

[Anonymous No.9539221]

Is this a joke? Honest question. I can’t come to terms with the idea of some fucking moron on 4chan thinking he can prove this shit let alone in 1 page.

[op No.9539228]

>>9539216
[1, 2, 3].fold(sum) = 1 + 2 + 3

[Anonymous No.9539233]

>>9539221
Stranger things have happened. Unfortunately, it seems that OP doesn't understand the basics of the problem, so this is certainly a lost cause.

[op No.9539236]

>>9539215
Thanks for the feedback! You are given:

KEY (64 bit integer)

A (unordered list; ordering breaks KEY)
PS(A) (subset sums of A; unordered)

KEY is the sorting order of PS(A) which you have to verify. Examining KEY is exactly what you're asked to do!

I'll think about your question a bit more, since obviously if you have it then I'm not clear.

[Anonymous No.9539247]

>>9539236
Wait, I am given both A and PS(A)? I thought A was an input, and PS() was a well-specified algorithm. If PS(A) is an input, then that itself is already exponentially large, and the problem disappears.

[op No.9539254]

>>9539216
the formal language used is a bit confusing. I have to word it like that, since the order things are defined in. with PS(x), x is the input. PS(A) is a possible input for PS(x).

[Anonymous No.9539259]

>>9539215

basically this. You try to hide behind the fact that it's "multiple keys" and layering multiple functions and definitions, but essentially you're just performing one long complicated algorithm.. It doesn't matter if it's a series of keys, an algorithm, or sudoku puzzles it doesn't change the problem. You're just assuming some algorithm exists that always takes Ω(2^n) time to solve, and in doing so you're begging the question. If such an algorithm (or series of keys, or sudoku's, or whatever) exists, then you must first prove P = NP in the first place.

In order to actually solve the problem at hand, you would have to find an actual algorithm and then rigorously test it and prove mathematically beyond a shadow of a doubt that NO other direct path to a solution exists. And if that sounds impossible, then congrats, you just found out why this has never been solved.

[op No.9539265]

>>9539215
here's another way to answer your question:

the thing you have to show is that PS(A)[x xor KEY] is ordered. You question can be stated as "Can you just examine A and KEY?"

No, you can't, because that's mathematically equivalent to sorting a set of 2^(|A|) size

[op No.9539270]

>>9539215
I'll definitely add a clarification for that point, if you just skim the paper it's easy to overlook some things that show that's not possible, so I'm not being clear maybe

[Anonymous No.9539278]

>>9539265
>the thing you have to show is that PS(A)[x xor KEY] is ordered. You question can be stated as "Can you just examine A and KEY?"
Indeed it can.

>because that's mathematically equivalent to sorting a set of 2^(|A|) size
Yes, so? The key point is that this is not an arbitrary list of 2^|A| elements -- it's a list *that I know to be generated by the PS() function*. Which means I know a great deal about the structure of PS(A); and if you know something about the structure of a piece of data, you can often avoid examining the whole thing. Just like you can search a sorted array in logarithmic time, by making use of your knowledge of the ordering-structure present in the data; likewise, I may be able to use the structure I know to be present in PS(A) to compute the problem you are after, in vastly less time than |PS(A)| = 2^|A|.

I can mathematically search a sorted array A in O(log |A|) time, by making use of the structure I know to be in it. I claim that I can likewise solve the problem we are looking at here in O(log(|PS(A)|) = O(log(2^|A|)) = O(|A|) time, by making use of the structure I know to be in it generated by the PS() function. Your proof is not done until you can prove me wrong.

(I don't actually claim to be able to do this, and I do think that P != NP. But proving me wrong on this IS the essential part of the P != NP problem.)

>No, you can't,
Prove it.

[op No.9539286]

>>9539278
If you're making this argument then my proof is not clear. I'll think of ways to clarify, thanks. If the problem isn't solved, it's at least damn close at this point

[Anonymous No.9539294]

>>9539286
>it's at least damn close at this point
It really, really isn't. What remains is the whole problem. Everything you have been doing so far is just getting the bookkeeping right.

>If you're making this argument then my proof is not clear
No. The problem is not that the proof is unclear. The problem is that you don't have anything to support this central point at all, in your proof OR in your head.

[Anonymous No.9539301]

>>9539286
No it isn't, because the "final step" that you need to correct is "proving that there can be no clever algorithm that solves it quickly", and that is the same step that is missing from EVERY potential proof that P=/=NP !!
Think about the primality test analogy, it would take exponential time to go by trial division, but the AKS algorithm is an unexpected algorithm that solves the problem in polynomial time.

[Anonymous No.9539305]

>>9539278
also you can exploit the fact that the (x xor KEY) also is a special kind of sequence, not just any permutation of 1, 2, ... 2^|A|

[Anonymous No.9539310]

>>9539037
Okay, I'll go with the new thread if you insist on claiming the whole board with your proof attempt.

First of all, assuming a fixed bound on the input size means you no longer are making a claim about P vs NP, as those are infinite classes of problems parameterized by the naturals (okay, thats not exactly true either, but you may assume this for your proof)

My point about the keys remains unanswered: how do you guarantee that the keys are unique for every list of sets? If you don't, then first of all the name 'key' is confusing (keys refer to a unique value, it could be considered a hash otherwise). Second, why don't the keys have to be unique?

Next, do you have a guarantee that the keys will be of polynomial size? If not, your problem doesn't even lie in NP!

Also, it remains unclear to me what 1. is the input to your problem, PRECISELY and 2. What is its size?

[Anonymous No.9539314]

>>9539305
I wasn't going to complain about that part, because it's part of the easily fixed errors in the proof, and OP can fix that particular part by replacing his xor scheme by an arbitrary permutation input (you can specify one in O(n log n) bits, after all, meaning it doesn't significantly change the input length). But yes.

[Anonymous No.9539319]

>>9539314
I don't think you can specify an arbitrary permutation of the powerset in O(n log n) bits.

[Anonymous No.9539322]

>>9539310
Just to clarify, you stating that 'the key length is very tiny' doesn't answer my question at all. Prove it my man!

[Anonymous No.9539324]

>>9539120
holy fuck i fell on the ground laughing

[Anonymous No.9539344]

>>9539310
What OP is trying to get across is the following:

- There is a function P(S) that for a set S generates the powerset of S in a particular specified order.
- There is a function V(T) that for an element of P(S) computes a natural-valued value. V(T) = sum(T), but that's not really relevant.
- There is a restricted class of permutations of P(S), let's call it X(S). This can express some particular permutations of P(S), details irrelevant; but the size of an element of X(S) is polynomial in |S|.
- Consider the problem where you have an input S, and a permutation sigma in X(S). Problem: is the list [V(P(S)[sigma(i)]) for i in |P(S)|] non-sorted?
- This problem is in NP (the is-sorted version is in co-NP), for a certificate can consist of elements i, j in [0, |P(S)|) such that V(P(S)[sigma(i)]) >= V(P(S)[sigma(j)]).
- It also requires Ω(|P(S)|) = Ω(2^|S|) time to compute, because checking for sortedness of [V(P(S)[sigma(i)]) for i in |P(S)|] requires | [V(P(S)[sigma(i)]) for i in |P(S)|] | = Ω(2^|S|) time, and therefore so does checking nonsortedness in the worst case.
- Thus the problem is in NP but not in P.

Finding the central flaw is left as an exercise to the reader.

[Anonymous No.9539345]

>>9539286

not him, but your argument basically boils down to

>here's this really hard thing to solve (NP)
>it takes exponential time to solve normally but with keys we can prove a solution easily (P)

that's the fucking easiest part. Anyone can do this, congratulations. There's thousands of NP- complete problems without a known solution that you're pretty sure is unsolvable. Nobody cares about that part. The problem here is this part:
>therefore a turing machine with perfect information about all of the algorithms with all of the maths ever can't solve it

I'm sorry but you can't just glance over this part. This is the very crux of the P = NP problem, the rest of this stuff isn't important at all. You are just assuming it can't solve it due to the complexity of your algorithm. But are you sure there are no short cuts? Yes, 99% sure whatever, but can you mathematically prove it? You are trivializing the most important part of the proof.

No, it's not proving P=NP because the algorithms are really hard and your puny human mind can't come up with a way to solve them.
No, it's not proving P=NP because the search space is too big for an ordinary search algorithm to brute force through

You have to prove mathematically that the keys you are using have no mathematical flaws or loopholes that can be exploited by a Turing Machine and prove WHY.

I recommend reading this article:
https://en.wikipedia.org/wiki/P_versus_NP_problem

if you still don't know why your proof is just wrong, read it again. And again. And again. And then click the little links at the bottom and read those too. I'm sorry but it's not about us misunderstanding you, you just don't understand what you're dealing with.

[Anonymous No.9539380]

>>9539344
Ah, well that is obviously insufficient for completely different reasons. The OP confused me with the talk about keys and such. In fact, I think confusion is the best result OP is going to get.

So, basically an obfuscated version of the well-known 'surely computations with my permutation are hard'-problem

[op No.9539397]

Adding a FAQ

~~~
Frequently asked questions
~~~
Q. Can you compare A to KEY to get any useful information?
A. No, not in polynomial time. Notice how only indexes and not elements are considered when PS(A) is constructed (the nth unordered element is replaced with the nth ordered power of 2). The problem is basically "is this PS(A)'s well order?" and this FAQ question is basically "Can you use A to determine if the presented order for PS(A) is its well order?" Yes, by comparing elements of PS(A) to PS(A)[x ⊕ KEY], which takes superpolynomial time! No other comparisons give any useful information at all (for example, A's order is ignored when constructing P(A), reordering A breaks KEY, A[x ⊕ KEY] would overflow, and applying the key to any element is simply absurd).

[Anonymous No.9539398]

>>9539380
Yes.

>In fact, I think confusion is the best result OP is going to get.
I have tried to explain this to them, but to no avail. They have over the course of several threads gotten considerably closer to an understandable argument that does not go completely off the rails on unrelated technicalities, but I have not managed to convince them that they are not even looking at the interesting part of the problem.

[op No.9539410]

>>9539397
any mention of P(A) i mean PS(A), i'm used to typing P(A) but changed it to avoid confusion with the P in P != NP

[op No.9539411]

>>9539398
you think you can compare KEY to A to get some useful information. The information you get is exactly what you use to search PS(A)[x xor KEY]

[op No.9539413]

>>9539398
what are you going to do? apply the key to A to cause overflow? sort A to break KEY? come on man, i'm adding a FAQ just for you now

[Anonymous No.9539417]

>>9539411
>you think you can compare KEY to A to get some useful information. The information you get is exactly what you use to search PS(A)[x xor KEY]
Yes it is. But that doesn't mean it necessarily takes the same amount of time. What is your proof that I can't acquire the same information this way in less time?

>>9539397
>No other comparisons give any useful information at all
Prove it.

[op No.9539419]

>>9539417

Here, I just listed all other possible comparisons. Done. Proven.

[Anonymous No.9539423]

>>9539413
>come on man, i'm adding a FAQ just for you now
Well, don't; I understand your argument perfectly, and there is no need to clarify things on my behalf. I am pointing out to you what's wrong with your proof, not asking for clarification. Use it or ignore it, as you prefer.

[op No.9539426]

>>9539417
literally proof by exhaustion, are you going to argue such an elementary proof? Go on, ask about comparing bits. To what now? exactly

by the way, i really do appreciate your attacks. other people will ask the same stuff, so it's good to clear any confusions out now

[op No.9539431]

>>9539423
yes, there 100% is because the same questions will be asked by others, and you're giving good feedback

a proof isn't a proof if anything is unclear. for example, "what is fold"? good question, so i well defined it in the paper, even though it is already well defined and has a wiki article

i can't be vague with P != NP

[Anonymous No.9539434]

>>9539426
>literally proof by exhaustion

this thread is proof by exhaustion

[op No.9539447]

>>9539434

a proof is a proof :p

fixed a typo and cropped the proof better

[Anonymous No.9539569]

>>9539398
Yes, I was hopeful at first that the flaw would be interesting, but alas.

Additionally, the OP appears beyond help. Your revised first line (claiming we can consider the naturals as 64-bit integers) tells me you don't even fully understand the problem!

Tell me, OP, do you know what a language is (in complexity theory)? A computational problem? A Turing machine? Do you even know the definition of P and NP? If the answer to any of these questions is 'no' (or worse, incorrect), then please take a course/read a book on complexity theory. Please don't enter the long line of idiots that present approaches to P vs NP without even understanding the problem!

You appear to be very invested in this proof of yours. Accept that you can be wrong, even the smartest people are wrong at times. In fact, they're smarter because they see they are wrong at times. Only a fool believes he is always right.

[Anonymous No.9539623]

>>9539447
>applying the key to any element is simply absurd
why though
why can't you have an implementation of Haskell (or whatever language you're using) that implements lists, folding etc in such a way that applying the key returns a meaningful value from which I can deduce the solution in polynomial time?

i mean, Haskell already lets you get away with bullshit like manipulating infinite lists with finite time and space, so why can't they do something like that for your problem?

[Anonymous No.9539807]

>>9539096

[Anonymous No.9539838]

>>9539051
I just don't understand how you shit these out every hour

[Anonymous No.9539907]

>>9539037

new version

>>9539890
>>9539890
>>9539890
>>9539890
>>9539890