Proof P ≠ NP

so the instance is a set of binary strings, and some x. and the problem is find a subset that xors to x, that's how I understand it.

i dont think using infinite strings is well defined, because how would you verify the answer? that would take infinite calculation.

but besides that, the thing is that we intuitively think to ourselves "no way we can beat brute force for np-complete problems". But no one has been able to formally prove that. You need a formal proof saying there's no way to beat brute force for your problem.

You can't really use the notion of randomness in the problem instance (that's like saying take a random 3SAT instance. The instance is just given to us).

Complexity is sweet tho hope you keep studying it!

The oracle and infinite strings are a simplification. People are retarded. I'll formalize with integers.

You're overlooking how xor works. It completely, mathematically, hides information.

>easy to verify a solution
How do you verify that two infinite strings are equal?

Sorry user 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.

THE ORACLE HANDLES THE INFINITE STRINGS IN O(1) TIME, MY GOD.

I'm reworking this to use finite integers. It literally doesn't matter. Now let's enjoy faggots getting confused and think n = the bit string length.

Above post was too long. That all being said, remove the infinite string requirement and this looks kind of cool.

But you haven't proven anything you've just given an intuitive explanation of why it kind of makes sense that this problem seems exponential.

Have you researched optimizations to solving the decision problem? I can think of a few at the tip of my tongue. The problem space can likely be pruned by looking at each bit-index individually. And in this case the worst case scenario is where no new information is presented by earlier bit-indexes until the very end. How this would occur I'm not sure. I don't think this is even exponential. It has been a while since I took theoretical computer science but the burden of proof is on you anyway to prove that this decision problem is exponential.

I don't think you know what the typical theoretical computer science usage of the term "oracle" means. It is not used for verifying already provided answers, it is a Turing Machine that generates answers within the time limits of a certain complexity class. It is an abstract mathematical formulation used to simplify problems and reason about related algorithms.

user no offense and it's cool that you're trying to write proofs and stuff, but:
a) This is not a proof, this is an informal conversation
b) Every step is flawed in some way
c) You aren't even using the words correctly

Have you studied Computer Science in-depth or are you an amateur? No offense. Keep trying OP but I suggest you stop being so self righteous and getting mad at people for pointing out flaws in your supposed proof. The only way to grow is to have your work criticized.

Lol man I admire the commitment but you gotta be a little more open minded, otherwise you're not going to go very far, especially in research..

Here, I've super simplified it:

1. Let A be a set of n integers of length o. For example: {...1101, ...0100, ...0111}.
2. Let f be an oracle such that f(B) reduces a set B of integers under xor in O(1) time. For example: {...1101, ...0100, ...0111} → ...1101 ⊕ ...0100 ⊕ ...0111 → ...1110.
3. Let the problem be: find subset C of A such that f(C) = 0.
4. The problem is NP.
5. It is well understood that if x = a ⊕ b it is impossible to know the values of x, a, or b without knowing the values of all the others.
6. As such, given x, there is no algorithm that can select a from a set without also selecting b. That’s because values of a or b can only be known after performing f({x, a}) = b, f({x, b}) = a, or f({a, b}) = x.
7. The same logic applies to all subsets of A. Until you perform f(C) = 0, you gain no information about C.
8. As such, the only way to find C is with trial and error, which takes O( 2^n ).
10. Therefore, P ≠ NP.

2) That's not what oracles do, oracles provide answers to decision problems they don't determine whether a provided answer is valid
4) You have to prove that this decision problem is in NP user.
5) Fair enough
6) You have to prove this
8) Prove that there is no faster way
10) No

user you're just making tons of big statements without proving anything. The point of proofs is that every statement has to follow from previous ones. You're just laying out a concept you think is right without disproving alternatives

Anyway I'm leaving this thread. Please read Sipser to get started

Protip: if your proof is

What if you're wrong, OP?

What if it isn't a small, tiny mistake, but what if the whole 'proof' is wrong?

rekt

Dude, the point of an Oracle is to do a proof by contradiction. You assume a particular machine could be built and then show that if you used it in conjunction with other machines, you reach a logical contradiction. Where is the contradiction?

You need to write this a lot better, including the proof that verification of certificates to the decision problem you are describing can in fact be done in polynomial time.

stop posting retarded nonsense here you dumbass