/sci/ - Science & Math

>>9530403
FUCK OFF

>>9530405
I think this attempt is pretty solid.

>tbw I don't understand what op meant by this

>>9530405
>FUCK OFF
Do you need to swear?

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

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

>>9530405
Watch your language please

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

>>9530444

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

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

>>9530454

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

>>9530458

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

>>9530430
>>9530440
fags

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

>>9530458

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

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

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

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

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

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

>>9530488
good point, consider this a first draft then. i'll define everything clearly up front.

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

>>9530497
i never promised not to post here, just to stop spamming the math reddit with attempts

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

>>9530499
>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.
>>/sci/thread/S9522189#p9522634
>I'm not making another attempt after this

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

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

>>9530473
>fags
Why the homophobia?

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

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

https://en.wikipedia.org/wiki/Prime_number

https://en.wikipedia.org/wiki/Fractional_part

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

P7. P5 ∧ P6 ⇒ S1

https://en.wikipedia.org/wiki/P_versus_NP_problem

0x51B4908DdCD986A41e2f8522BB5B68E563A358De