/sci/ - Science & Math

>>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

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

* 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 largest element of PS(x)

* Let a "power key" be, for any set x, for any natural n, a natural such that PS(x)[n ⊕ (the power key of PS(x))] is the nth largest element of PS(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 poly time

* **NOTE: ⊕ is the exclusive or operation. 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 poly time, because every possible partial order of that set is embedded in its set of subsets. This forces the ordering of that set's subsets to run in ≥ O(2^(n)) time**

* Let the decision problem be "Given set A and 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 compare PS(A)[x ⊕ KEY] for all natural x < O(|PS(A)|), to find if any elements are not in order, and therefore must run in ≥ O(2^(n)) time, which is superpolynomial

* **NOTE: It's possible that a invalid power key orders a set of subsets such that only 2 elements are out of order**

* 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 PS(A)[x ⊕ KEY] > PS(A)[y ⊕ KEY]

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

**Statement**

S1. P ≠ NP

**Proof**

P1. let M = deterministic polynomial time Turing machine with input w that solves "x ∈ (P - A) ∧ x ∈ (P - B)" given:

* ∀x[x ∈ ℕ ∧ x & 2^(|w|) - 1 ⇔ x ∈ P]

* ∀x[x ∈ ℕ ∧ x % 2 = 0 ∧ x^(1/2) ∈ R - Q ⇔ first |w| symbols of fractional part of x^(1/2) ∈ A]

* ∀x[x ∈ ℕ ∧ x % 2 = 1 ∧ x^(1/2) ∈ R - Q ⇔ first |w| symbols of fractional part of x^(1/2) ∈ B]

note: w is not used except for |w|

P2. consider how |P - A| = O(2^(|w|))

P3. consider how |P - B| = O(2^(|w|))

P4. consider how "x ∈ (P - A)" takes ≥ O(1) time in deterministic Turing machine

P5. consider how "x ∈ (P - B)" takes ≥ O(1) time in deterministic Turing machine

P6. P2 ∧ P3 ∧ P4 ∧ P5 ⇒ "x ∈ (P - A) ∧ x ∈ (P - B)" takes ≥ O(2^(|w|)) time in deterministic Turing machine

P7. P6 ⇒ M not in P complexity

P8. consider how "x ∈ (P - A) ∧ x ∈ (P - B)" is verifiable in polynomial time

P9. P9 ⇒ M in NP complexity

P10. P7 ∧ P9 ⇒ S1

0x51B4908DdCD986A41e2f8522BB5B68E563A358De