Let a "power key" be, for any set x, for any natural n...

* Let P(x) be a list of all subsets of x, with each subset folded over some operation to a natural, such that, given natural n, P(x)[n] is the nth element of P(x)

* Let a "power key" be, for any set x, for any natural n, a natural such that P(x)[n ⊕ (the power key of P(x))] is the nth largest element of P(x)

* Calculating a power key is the same as well ordering a set of all subsets, with each subset folded over some operation to a natural, which can't be done in polynomial time

**NOTE: ⊕ is the exclusive or operation. For all natural n, if you apply ⊕ against some natural to every natural from 0 to 2^(n) - 1, those naturals are reordered to the order encoded in that natural**

**NOTE: There exists some set such that it is impossible to well order that set's subsets in polynomial time, because every possible partial order of that set is embedded in its subsets. This forces the sorting of that set's subsets to run in ≥ 2^(n) time**

* Let the decision problem be "given set A as input, given natural KEY as input, is KEY not the power key of A?"

* Let A be a set, given as input

* Let KEY be a natural, given as input

* Let n be the cardinality of the binary string representing the input of the decision problem

* All deterministic Turing machines that decide the decision problem must iterate over P(A)[x ⊕ KEY] for all natural x < |P(A)|, to find if any elements are not in order, and therefore must run in ≥ O(2^(n)) time, which is superpolynomial

* A deterministic polynomial time verifier can verify a YES solution to the decision problem if set A, natural KEY, natural x, and natural y are given, such that x < y and P(A)[x ⊕ KEY] > P(A)[y ⊕ KEY]

* Because a deterministic polynomial time verifier exists for a decision problem such that any deterministic Turing machine deciding it must run in superpolynomial time, P ≠ NP

0x51B4908DdCD986A41e2f8522BB5B68E563A358De

what's the P(x)[ ] operation
what's the ordering on P(x) since you talk about the nth largest element
please first write the definitions then use them not the other way around

Usually there will be more than one biggest n element for any n

Let P(x) be a list of all subsets of x, with each subset folded over some operation to a natural, such that, given natural n, P(x)[n] is the nth element of P(x)

> P(x)[n] is the nth element of P(x)

That's fine, and not important to the proof

Here:

* Let PS(x) be a list of all subsets of x, with each subset folded over some operation to a natural, such that, given natural n, PS(x)[n] is the nth element of PS(x), in some order that's possible in polynomial time (for example, sets of subsets are usually ordered as if each element is a power of 2 and as if each subset is ordered by its sum in the same order as the naturals)

Is that clear enough?

Sets of subsets that are sorted in polynomial time are sorted by index, not value. For example, PS(x) is usually (but not always, as it's not important to this proof) ordered as if the nth element of x, in the same order as the naturals, is the nth power of 2 and as if each subset of x is ordered by its sum in the same order as the naturals. Notice how such an order only considers keys, not values, which allows lazy construction

so the algorithm should solve the problem only with regard to this particular ordering and this particular indexing?

Nope, the order doesn't matter. I originally didn't present an order because it doesn't matter, but I've given an example order because it was asked about.

The thing is, power sets are constructed lazily (they must be, to exist in polynomial time), so they must be therefore constructed by key and not value.

This has the side effect of every possible partial order of x being embedded in the power set of x, making it impossible to sort x in polynomial time

but that's more of a note that you write down in the margin and not really important to the bulk of the proof

Would you care to briefly sketch your idea? I'd like to check it but reading all these long ass posts is simply boring.

>the statement of the problem explicitly contains ordering and indexing
>uhhhhhh it doesn't matter
wow you are fucking retarded if i pick the ordering equal to the indexing then i can answer any query instantly since the only key is 0

1. power sets are constructed by key, not value, and therefore embed every possible partial order, and can't be sorted in polynomial time

2. if you take the numbers 0 to 2^n - 1 and xor all of them by some value, you just shuffle them. therefore, any shuffling order of a power set can be encoded as a single integer

3. you can ask: is this integer the order of this power set, if it's reduced by that reduction? which requires reducing every subset to see if any are in the wrong order

4. the answer to the question can be verified in polynomial time if you word it right (is this NOT the sorted order?)

5. this implies p != np

would require superpolynomial time to do that, order doesn't matter as long as the power set is lazily constructed, and that order you're talking about isn't possible with lazy construction

the important thing is that I've reduced all NP-complete problems to sorting a power set, which is a huge breakthrough. for example, the subset sum problem can be solved in O(n) time if the subsets are sorted, by just doing a binary search

the fact that you can't sort a power set is obvious because, again, power sets are generated lazily by ignoring their values, and all sorting algorithms sort in O(n) time or more (usually O(n log n)), and if n is 2^whatever like it is with a power set, you have a superpolynomial task on your hands

pretty trivial stuff, desu

and if anyone says you can sort a set in less than O(n), we are entering pure insanity mode because that would require ordering elements without ever looking at them

and you can't use the source set to hint at the order of the power set because:

1. the power set contains EVER possible partial order by definition, so it's as unordered as you could possibly get

2. power sets are constructed lazily, so the values are straight up ignored on construction

and you MUST construct power sets lazily because they're too big to exist in polynomial space.

this is all very simple stuff, and the proof is very, very straightforward

The notes in the proof have gotten too big for a post here. Here's a link that's a bit easier to read

reddit.com/user/cold-winter-night/comments/7ydw8c/p_np/

>4. the answer to the question can be verified in polynomial time if you word it right (is this NOT the sorted order?)
That sounds like the problem is in coNP, not NP.

>Calculating a power key is the same as sorting a power set, which can't be done in polynomial time
Whoa, easy there. Why are these the same? Finding the just the order of the n-th element sounds a lot simpler than sorting the entire set. In fact, exponentially simpler, as the power set is of size exponential in n.

I was sure you were trolling the first time, but looking at your posts more thoroughly now I suspect you might actually be that retarded

Yeah, I had to word it funny in he actual proof to force it to be in NP.

No, I've actually solved it. The proof is valid

I'll clarify. If you have the power key, you can treat the power set as a sorted power set by just xoring every index by the power key before

for example:

P(x)[y] = using P(x) unsorted

P(x)[key xor y] = using P(x) sorted

therefore, having the power key is identical to having the sorted set

if it's not clear, there's only 1 power key for the entire power set, and it works on EVERY index

Here, I've added a note:

Calculating a power key is the same as well ordering a set of all subsets, with each subset folded over some operation to a natural, which can't be done in polynomial time. To clarify, there's only 1 power key per set of all subsets. PS(x)[n] is the nth element of PS(x), unsorted, and PS(x)[n ⊕ (the power key of PS(x))] is the nth element of PS(x) sorted. The 1 power key works for all subsets, so having the power key of PS(x) means you effectively have a sorted PS(x)

>2. if you take the numbers 0 to 2^n - 1 and xor all of them by some value, you just shuffle them. therefore, any shuffling order of a power set can be encoded as a single integer
but 'xoring by a number' doesn't produce all possible shuffles

it does, every different number produces a different order. try it yourself, and think about logically what's happening

there are some invalid power keys by the way, such as really big numbers for a small power set.

the proof is about determining if a power key correctly sorts a set, which obviously has a worst case when the sorting order is either very close or perfect

yes every different number produces a different order
doesn't mean that any shuffling of power set arises in such a way

The middle statement is not true

maybe my wording is shit, here's what i'm saying:

you have a set of integers. you can generate the power set lazily. you can then generate subset sums lazily. you can check PS(n) to give the nth power set, but the power set is only partially ordered because it was generated lazily by key, and the values (and therefore subset sums) were ignored on construction

you are also given a power key, such that PS(n xor key) supposedly gives you the nth largest subset sum. power key works on all subset sums, supposedly. if that's the case, you can use the power key to binary search the subset sums to figure out which one sums to 14343.

but you don't trust the power key. how do you verify the person who gave you it wasn't lying? you can't, and that's what the proof is about.

which one?

i've edited for clarity

put me in screencap

easy to read version

If the proof was finished in one night, it isn't right

The proof is ground breaking because it invents the concept of a power key, proves P != NP, and reduces all NP-complete problems to sorting power sets, which is well known to be impossible in polynomial time

You are starting to sound Schizo my dude.

you need to see a psychiatrist

Yeah, my thoughts exactly, he's pretty obsessed with it while being unable to understand the error in his proof for the 3rd time
he needs to be put on meds

you didn't even mention the word 'integer' or 'sum' in the op post
let me clarify if i finally understood:
A is a set of n integers
P(A) is the powerset and we fix some easy to compute mapping from integers 0,1, ... 2^n -1 to P(A). For example, use the binary encoding, so that P(A)[0] corresponds to empty set, P(A)[1] corresponds to set consisting of first element of A, P(A)[2] corresponds to set consisting of second element of A, P(A)[3] - set consisting of first and second element of A, etc.
the problem: given set A and number KEY, is it true that P(A)[x ⊕ KEY] is the subset which has the x-th biggest sum?

now how did you arrive at the following conclusion
>All deterministic Turing machines that decide the decision problem must iterate over P(A)[x ⊕ KEY] for all natural x < |P(A)|

I've added a note for you:

It's important to stress that skipping any 2 elements leaves open the possibility of the power key being invalid

It's possible that an invalid power key orders a set of all subsets such that only 2 elements are out of well order

i was trying to explain with those terms to you, sum isn't important in the proof, it applies to all reductions

The OP was a first draft that I rushed out quickly, here's a revision with lots of notes and some fixes:

reddit.com/user/cold-winter-night/comments/7ydw8c/p_np/

new thread

>It's possible that an invalid power key orders a set of all subsets such that only 2 elements are out of well order
this is not obvious and might not even be true
there are only 2^n powerkeys, but (2^n)! ways to order the powerset
there may be a better way to solve this problem than just checking all possibilities
>sum isn't important in the proof, it applies to all reductions
i don't even know what 'reductions' are you thinking about
ill repeat once more: you failed to even specify the task precisely

it's obvious and true, but i'll add a clarification

also, the reduction doesn't matter for the proof. the proof reduces all NP-complete problems to problems of sorting power sets, with the difference between different NP-complete problems being what reduction

Dumb reddit-spacing unicode weeb.

Let, let, let, let

Is OP projecting something?

OP is a brainlet?

note added to the proof

It's possible that an invalid power key orders a set of all subsets such that only 2 subsets are out of well order, so it's impossible to skip any 2 subsets while verifying a power key. This can be proven trivially by calculating an invalid power key for a small set by hand that leaves only 2 subsets out of order

new thread

you failed to even specify the supposed NP problem precisely
please first provide a clear explanation of the problem
polite sage

congrats you just described a hash function

pic related is you