note: for example, the first 3 symbols of the fractional part of 1.01000110… are 010
P3. let PROBLEM = "there exists some x ∈ S and there exists some y ∈ S such that x ⊕ y = w"
P4. let M be some deterministic Turing machine with input w that solves PROBLEM
P5. consider how M solves PROBLEM in ≥ O(log log ... repeat x times ... log |A|) time for some x ∈ ℕ
P6. consider how |A| may be ≥ 2 ^ 2 ... repeat x times ... ^ 2 ^ |w| for any x ∈ ℕ
P7. P5 ∧ P6 ⇒ for some A, M solves PROBLEM in ≥ O(2 ^ |w|)
note: regardless of how large S is, S is not guarenteed to contain all x ∈ ℕ such that |x| ≤ |w|
P8. P7 ⇒ M is not some polynomial time Turing machine
P9. consider how there exists some certificate c for PROBLEM such that c verifies a YES solution to PROBLEM in polynomial time
note: for example, if c = [ath prime, bth prime], |a| ≤ |w|, |b| ≤ |w|, and first |w| symbols of fractional part of c[0]^(1/2) ⊕ first |w| symbols of fractional part of c[1]^(1/2) = w
basically, no matter how many mobs you kill, there's a chance that you don't get any rare drops
using that fact, and the entropy created from your choice of how to encode binary numbers, you can create a really, really big pseudorandom search space that's not guaranteed to contain any element and tell someone to look for something in that space.
sure, they can use whatever patterns or tricks they want. you can just make the search space bigger to counteract their tricks. if they can solve the problem in O(n), just make n = 2^|w|
therefore, you can force a situation where a problem exists that's hard to solve but easy to verify, implying P ≠ NP
Anthony Roberts
>basically, no matter how many mobs you kill, there's a chance that you don't get any rare drops Yes, but you need to actually kill them. Trying to kill the boss every day with your insufficient gear will not help until you gear up or level up.
>if they can solve the problem in O(n), just make n = 2^|w| You must not sacrifice polynomial-time verifiability, though. If you make n exponentially large, then it will take exponential time to verify the solution.
Kevin Garcia
Watch your language please
Nolan Flores
some solutions become hard to verify, but not all solutions, and that's the trick!
for example, say your search space is the first 2 ^ 2 ^ 2 ^ 2 ^ 2 ^ 2 ^ 2 ^ 2 ^ |w| primes, but the certificate is just {11, 17}. with that certificate, you can verify the solution in polynomial time.
you don't have to be able to verify ALL yes solutions in polynomial time, only A SINGLE POSSIBLE yes solution
if it's YES solution contains something like TREE(3) + x such that TREE(3) + x is prime, good luck performing a xor on that. i considered this already though, and it doesn't hurt this proof
Brayden Sullivan
to clarify, {11, 17} needs to be a valid yes solution in this example. the hardest math problem is, specifically:
"does there exist a problem that's hard to solve but easy to verify its solution?"
if the solution is {11, 17} but the search space is stupidly large, the answer to the hardest question is yes, P ≠ NP
Easton Nguyen
>you don't have to be able to verify ALL yes solutions in polynomial time, only A SINGLE POSSIBLE yes solution Yes, but there isn't necessarily a single positive solution verifiable in polynomial time for every input.
NP requires that for every input with a positive answer, there is a certificate (i.e. a solution) that can be verified in polynomial time. If your smallest possible solution for a particular input w has x = 2^2^2^2^something, then it cannot be verified in polynomial time.
Zachary King
to clarify further, presume a valid yes solution lies in the first |w| primes but you don't know it
you can just search the first |w| primes and find the solution, but if it doesn't exist in that space you have to search the rest of the space so your algorithm is super-polynomial
if you stop your search after |w| primes, then your algorithm can't find a yes solution that's in the higher space, and it's not a valid algorithm to solve the problem
William Green
yes, i understand that. slightly confusing part is that there are infinite possible Ms. I'm not saying every M is in NP, by the way, only some of them are.
it's impossible for M to know if it's in NP or not without actually searching the space, and any algorithm that could possibly return YES could also possibly run in superpolynomial time.
I see how that can be confusing, i should probably add a note
Henry Campbell
fags
Matthew Watson
To be honest, I can't really make heads or tails of your argument either way. Your earlier attempts I could usually decode with some guesswork, but this is just too far off. I suggest putting some work in expressing your ideas in terms of actual math that people can follow.
Christian Hernandez
consider M0 such that every input with a positive answer is in the first |w| primes.
consider M1 such that not every input with a positive answer is in the first |w| primes.
M0 and M1 have the same algorithm, and the only difference is A.
I'm only trying to prove P != NP for M0, and I don't care about M1
Carter Gutierrez
it is in actual math, and that's why it's confusing. "explaining more" doesn't do shit because nothing is vague in the proof, but i can add notes
Asher Williams
As a working mathematician in the field of computer science, you can take it from me that it is not. You are imitating the symbology, but the substance of your argument is anything but.
Isaac Thomas
i think proving some M are in NP needs to be more rigorous, that's probably the most confusing bit because not all M are in NP.
Part of the confusion is how you have to frame things in terms of Turing machines and can't just say what you mean intuitively
Isaiah Reed
>Part of the confusion is how you have to frame things in terms of Turing machines and can't just say what you mean intuitively But the real confusion is that you make it completely unclear what are inputs, what are defined terms, what are background constants, what are free variables to be filled in with substance later (which you then never actually fill in), and which of those depend on which others. Without that, anything else is too inscrutable to even attempt to decode.
Kevin Butler
that's a fair criticism. can you point out what points are vague or wrong? i think there is something here, and i'm probably just shit at using the correct terms or not understanding that something isn't trivial
Colton Sanders
good point, consider this a first draft then. i'll define everything clearly up front.
Jonathan Morales
If you really do care about working on this sort of task enough to go back on your promise not to try doing this again, why don't you go back to school and get a formal mathematics / comp sci education so you can know what you're doing? There are a lot of subtle ways you can fuck up "learning" topics like this when you try to self-teach, and if you're serious about going after what might be one of the most difficult open problems in existence then you might as well get the formal background so you aren't stuck being completely unable to distinguish between reasonable approaches vs. blatantly flawed or incoherent formulations.
Nolan Bell
i never promised not to post here, just to stop spamming the math reddit with attempts
Lucas Garcia
To give you a quick idea -- and I want to make it clear that this is not an exhaustive list, just some starting points -- consider the following:
>P1. let A = first n primes What is n? The entirety of the argument is inscrutable without that understanding. Are you trying to say "for natural number n, let A(n) (or A_n, depending on taste) be the list of the first n primes"?
>P2. let ∀x[x ∈ P ⇔ first |w| symbols of fractional part of x^(1/2) ∈ S] What is w, and what is S? I am guessing that w corresponds to an input somehow, based on P3; are you trying to define S here? Do you want something along the lines of "for w (what type is it? natural number? is |w| its bit size?), let S(w) be..."? I am guessing that P is the set of primes?
>P3. let PROBLEM = "there exists some x ∈ S and there exists some y ∈ S such that x ⊕ y = w" Where w is the input, which is a bit sequence?
>P5. consider how M solves PROBLEM in ≥ O(log log ... repeat x times ... log |A|) time for some x ∈ ℕ >P6. consider how |A| may be ≥ 2 ^ 2 ... repeat x times ... ^ 2 ^ |w| for any x ∈ ℕ >P7. P5 ∧ P6 ⇒ for some A, M solves PROBLEM in ≥ O(2 ^ |w|) >P8. P7 ⇒ M is not some polynomial time Turing machine Can't make sense of this without clarifying P1. What does A depend on, exactly?
>it is in actual math, and that's why it's confusing. >Part of the confusion is how you have to frame things in terms of Turing machines and can't just say what you mean intuitively Formalism doesn't make math. You don't make your argument more mathematical by writing ∀ and ⇔ or even Turing machines rather than saying the same thing in more informal wording. Most actual mathematics is not written like this. It's clear relations in the structure of your argument that makes or breaks it.
Christopher Jenkins
>i never promised not to post here, just to stop spamming the math reddit with attempts You lied multiple times there and multiple times here about not posting this again. warosu.org/sci/thread/S9522189#p9522634 >I'm not making another attempt after this
Cameron Young
There's a typo in the proof, P is meant to be A. But those are all fair points.
The proof is invalid. I accept that from the responses here.
Michael Cook
I think he is saying:
A = a set, containing the first n primes
So A has size n.
Problem: The input to your Turing machine A is a string w and a number n, and you want to output YES if "two of the first n primes have fractional parts whose first |w| digits XOR to w". There are "n choose 2" pairs, and the problem size is |w| + log(n).
This is is NP, because your certificate is the pair of primes that work, which is of polynomial size because of Chebychev's theorem.
Then he claims that the problem is NOT in P. Then he claims that trying all combinations takes more than polynomial time. I think he is trying to make n much larger than w.
Or maybe he means are there ANY two primes such that the first |w| digits of their square roots XOR to w, in which case it is not obvious that the problem is in NP at all, since the certificate can be arbitrarily large.
In any case, he did not show that there is no way faster than trying all combinations.
Liam Russell
>fags Why the homophobia?
Lucas Hall
my proof is wrong because the certificates are too big. i didn't realize the verifier has to be able to verify ALL possible certificates, not just the winning ones
Cooper Ortiz
Here is the proof reworded, but it's wrong I think:
**Statement**
S1. P ≠ NP
**Proof**
P1. for all n ∈ ℕ, let M_n be some deterministic Turing machine with input w that solves "there exists some x ∈ S and there exists some y ∈ S such that x ⊕ y = w" such that ∀x[x ∈ first n primes ⇔ first |w| symbols of fractional part of x^(1/2) ∈ S]
note: for example, the first 3 symbols of the fractional part of 1.01000110… are 010
P2. consider how, for all n ∈ ℕ, for some x ∈ ℕ, M_n runs in ≥ O(log log … repeat x times … log n) time
P3. consider how, for all w, for all x ∈ ℕ, there exists n ∈ ℕ such that n ≥ 2 ^ 2 … repeat x times … ^ 2 ^ |w|
P4. P2 ∧ P3 ⇒ for some w, some n ∈ ℕ, M_n runs in ≥ O(2^(|w|)) time
note: regardless of how large S is, S is not guaranteed to contain all x ∈ ℕ such that |x| ≤ |w|
P5. P4 ⇒ for some n ∈ ℕ, M_n is a deterministic superpolynomial time Turing machine
P6. consider how, for some deterministic superpolynomial time M_n, there exists some polynomial time verifier V_n exists such that V_n can verify certificate c such that c… **(error: some certificates are too big)**
