/sci/ - Science & Math

>>9485989
It's an unfalsifiable hypothesis and these are not worth entertaining, similar to hypotheses that invisible omnipotent Gods created the universe then decided not to interfere with it anymore, or that there is a teacup floating around Mars

These are just the sorts of things that are outside the limitation bubble created by Godel's Incompleteness Theorems and Turing Computability

>>9446068
Sorry anon but this is not a valid proof.

>1. You have a finite set of binary strings.

>2. Each binary string consists of an infinite number of random bits. For example: ...1011.
A Turing Machine cannot work with infinite lengths in any finite amount of time, period. Proof is likely going to unravel from here due to this point alone.

>3. An oracle can reduce a set of binary strings under xor in O( 1 ) time. For example: {...1101, ...0100, ...0111} → ...1101 ⊕ ...0100 ⊕ ...0111 → ...1110.
As I thought. No oracle can reduce even one subset of infinite binary strings into its cumulative XOR because the strings are infinite in length.

>4. You are asked to find a subset that the oracle can reduce to x.
It cannot reduce any subsets into x for the aforementioned reasons.

>5. This problem is NP-complete because it’s hard to find a solution but easy to verify a solution.
It's actually impossible due to infinite lengths, and this is an oversimplification of what NP-complete means.

>6. If x = a ⊕ b ⊕ c ⊕ ..., you can determine one of the unknown variables (x, a, b, c, etc) if and only if you know all others, presuming the bits are actually random. This is a well known property of xor and often used in cyphers.
No you can't, because the strings are infinite in length.

>7. Because of that, even if you know x, it is impossible to select a, b, c, etc from a set of objects without also knowing their values beforehand. The only way to find them is through trial and error.
Impossible always due to infinite length.

>8. Using the oracle, trial and error has a worse case time of O( 2^n ), where n is the number of elements in the finite set. This is exponential and not polynomial.
No, this decision problem is undecidable for all inputs.

>9. Therefore, P ≠ NP.
No. Sorry OP.