Hello, it's me again. I'm offering a $50 bounty in ETH or USD (through PayPal) for anyone who can disprove my proof:

maybe even mathoverflow or stack overflow for computer science

Thanks! I've posted it here upon your suggestion:

mathoverflow.net/questions/293180/50-bounty-show-my-p-≠-np-is-invalid

Haha, well hopefully you get an answer
Mathstackexchange is by far the best place for math. New question every minute as you can see
Mathoverflow is like math stack exchange, but with fewer users
Stack Overflow is mostly for computer science

I'm sure somewhere can answer your question though. They might not like the bounty as some of them are a stickler for rules, but a lot of heavy hitters use these websites

I've been offering money for an error for hours and all people do is shit talk me without saying what line is wrong.

I know I'm wrong, but God damn, just show me why. That's all I want, and no one can do it.

Three broad classes of attempted proofs have been proven to not be capable of working for this problem.
Do you know if your attempted proof can be considered a relativizing proof, a natural proof, or an algebrizing proof? And if it isn't an of those three, do you know what general class of attempted proof yours does belong to? That would probably help you identify if there's any hard proof against what you're trying to do.

I'll be a little explicit more explicit. If I were you, I would take this proof to math.stackexchange.com/
or stackoverflow.com/

The first will definitely do the trick. The second one is often for programming questions. There is many of these websites.

Then I would remove the 50$ bounty, because people will downvote you for not following the rules. They have lots of rules on these websites and it's heavily monitored by mods and other users. Wait a few days for an answer. Just because there isn't one, doesn't mean people aren't working on it.

That's interesting, thanks! Do you have a link where I can read more about how those are proven incapable?

I don't know what class of proof this is.

>All information that's not changed from unknown to known by comparing elements is presumed to be already known (or unknowable in some cases) in this proof.
That is not actually true, so your proof falls apart.

epubs.siam.org/doi/abs/10.1137/0204037
sciencedirect.com/science/article/pii/S002200009791494X
scottaaronson.com/papers/alg.pdf
From what I understand proving those three classes of attempted proofs cannot work was a big part of what's actually been accomplished so far on the P=NP problem. It wasn't as good as directly proving or disproving P=NP itself, but narrowing down the possible range of approaches that even have a chance of working is at least progress.

Maybe I should have reworded that by starting with a "Let". I was trying to force all operations other than making a comparison require O(0) time for the sake of the argument.

OP's attempted proof is none of those.

It's the kind of proof where you (1) take a particular NP-hard problem; (2) assume for no particular reason that any algorithm for solving it must repeat a particular operation; (3) show that you need exponentially many such operations. (I guess this has some similarity to natural proofs, but it's not quite the same.)

Problem is, what stops me from designing an algorithm that doesn't do any comparisons between elements of your set at all?

Step P3, specifically.

If you can prove S(A) contains a power of 2 without ever checking if an element has only 1 bit on (or something similar), it's a trivial case.

Okay. Now prove that there are nontrivial cases, under your notion of triviality.

Sure. Let A be a subset of B. Done. Or, let A be all the prime numbers greater than 2. If the Goldbach's conjecture holds, done.

There are a fuckton of trivial cases. I'm only concerned with cases that can't be solved in O(1).

Sorry, I've misread. Give me a second and I'll respond.

>disprove my proof.
>cash reward if you can (you can't).

A nontrivial case is with A being the set of the first n powers of 3. I like your angle, though... how do I know for sure I can't find a subset of the powers of 3 that sums to a power of 2 in O(1) time? I thought it was obvious it'd take at least O(|A|), let alone what the proof argues of O(|S(A)|), but I should add that to the proof.

Presuming you can't instantly know in O(1) time, do you have more criticisms?

ETH isn't actual money.

nuts like these are hilarious to watch flop around but it's kind of sad if he's actually given his own money away already like he claims

I've already given away $75 to someone who disproved my last version of the proof. I have over $1M from being an early ETH investor, so I give it away pretty easily. I still wage slave because women are fucking expensive, though.

This entire line of reasoning is asinine.
If you've computed S(A) from an arbitrary set A you've already performed exponentially many additions dependent on |A| and there's no point arguing further.

The further argument is wrong anyway because when you pass from A to S(A) you throw away a great deal of information about A. This lets you reduce to a completely trivial problem of brute-force checking if a set contains a fuckton of elements but the entire point of the problem is that maybe you can do better than blindly computing all the sums and checking them all.

You can construct S(A) lazily. If you couldn't, P!=Np would be trivial.

You also can keep A for reference. No one says you can't reference A.

>No one says you can't reference A.
Sure, of course you can reference A again. But his "proof" never does.

Proof that P =/= NP:
1. Assume P =/= NP
2. Then P =/= NP

Can I get my million dollars now?

Because it's not needed. The proof shows that.

No, the proof shows that given an arbitrary really big set, it takes a long time to check if an element is inside.
Nowhere in the proof does it even _matter_ that S(A) was constructed from A. All that matters is that it's big.

That's my point. It doesn't actually matter that S(A) is constructed from A. I've revised the proof slightly due to feedback from here, such that A is now the set of all powers of 3.

hey user I shouldn't even be on this board because I'm a genuine windowlicker and I don't understand anything anyone here is saying but assuming you're not trolling that's pretty cool that you're attempting this and I hope it goes well for you

Sorry, OP; in hindsight I did not give the most constructive feedback here, more in line with the standard Veeky Forums minimum-shittalking approach. Let me try again.

>A nontrivial case is with A being the set of the first n powers of 3.
I actually thought of an example just a few minutes ago along very similar lines.
Let A be any set of multiples of 3. Not powers, multiples.
Then the answer to the problem is simple: There is no subset of A that sums to a power of 2. For every subset of A sums to a multiple of 3, which therefore is not a power of 2.
So for this particular category of inputs A, I can write a simple algorithm that recognizes just those cases, and gives the correct answer ("no") for them. That algorithm runs in polynomial time. If I understand your reasoning correctly, you would classify this whole set of inputs as trivial. Is that right?

Now of course that algorithm covers only one particular small set of special-case inputs. But it is not the only special case category I can devise. Multiples of 5 will also work, and for multiples of non-2 primes in general; and if I sit down and think about it for an hour, I can probably think of several more unrelated patterns of inputs for which I can write an easy special-case algorithm.

Now, could I cover ALL possible inputs via one exception class or another, in such a way that I still have a finite set of exception classes? I don't think I could. But I can't PROVE it, and neither does your attempted proof argue for it. If I could, this would mean that all possible inputs of the problem are "trivial" by your reckoning; that is, by limiting your proof to nontrivial cases, you have accidentally assumed away the entire problem. Whoops.

[continued, 1/3]

[continued 2/3]

There ARE cases of algorithmic problems that seem difficult on the onset, except that all possible inputs can be classified into one of a small number of patterns, and any pattern has an easy solution. Proving that this is not the case for your power-of-2 subset-sum problem is pretty much the whole problem -- this is where the meat of the challenge lies; proving what happens afterwards is a triviality by comparison.

>I thought it was obvious it'd take at least O(|A|),
Your problem DOES always take at least O(|A|) in the worst case, for the last element of A might be a power of 2 on its own. Checking that A contains only multiples of 3 takes O(|A|) time, and this cannot be improved upon.

>Presuming you can't instantly know in O(1) time, do you have more criticisms?
Yes; but they are all insignificant next to this, which is the big one.

You have proven (some minor gotchas notwithstanding) that there is a particular class of algorithms that can never solve the problem in polynomial time. That is the class of arguments that (1) works by comparing members of S(A) and B, and (2) deducing from this whatever can be concluded based on transitivity. You have shown that this still requires exponentially many direct comparisons, which makes this class of algorithms impossible without further thought when we are aiming for polynomiality. This is similar to the proof of how all comparison-based sorting algorithms take O(N log N) at minimum.

But this does not prove P != NP. Algorithms could exist that do not fall into this category at all. I could do a number-theoretic analysis (like the multiples-of-3 thing), which is not covered by your analysis and which may or may not achieve polynomiality; or I could do any other number of things. Your proof covers ONLY a specific subset of possible algorithms.

[continued]

[continued 3/3]

If you could prove that all alternative algorithms behind the scenes do something similar to a number of comparisons that is polynomial in their running time, then your proof would have meaning. But that's not the case, for my multiples-of-3 thing doesn't do that.

If you could prove that every possible input to your problem can be solved EITHER by one of a list of patterns that you have listed in exquisite detail, or OTHERWISE must take an exponential number of comparisons, then you would have a real winner. But this would be MUCH MUCH harder than what you have done so far, and is probably still impossible.

Until then, I don't think there is any real point in salvaging the rest of your proof. The limits of a particular algorithm or class of algorithms is not the hard part; the hard part is showing that your class of algorithms somehow cover the entirety of the problem, in the sense that every possible algorithm can be reduced to your class without losing something.

>it's
are you ESL?

Yeah, I've revised the proof to use a specific example (powers of 3) for this exact reason. You are totally correct.

I also noticed that P5 is a bit of a hand wave. While it SEEMS true, nowhere is it implied, and actually it's the crux of the argument (it presumes a negative).

Basically I've been presuming a negative in P5 and then using that presumption to prove everything else. That is starting to look like the flaw.

Careful with powers of 3 -- 1 is a power of 3, and {1, 3} sums to 4. If you want positive powers of 3 only, then really it's the multiple-of-3 part that's doing all the work.

That's OK! It doesn't change the proof.

Actually, it is the ones doing all of the work.

You do realize no power of two is a multiple of three correct? No sums of multiples of threes is also thereby not a power of two.

The only powers that are important is 3^0. Derp.

>That is starting to look like the flaw.
Indeed it is. It is basically saying "presume that all forms of algorithmic analysis of A applicable to this problem can fit into this framework", which as you say is the fundamental issue.

I think strengthening that point is the next step. All the other points are rock solid.

I've slightly revised the problem, because I wasn't thinking about how 3^0 = 2^0.

You can reword it like this: does any power of 2, when written in binary form, have only 0 and 1 symbols?

Any power of 2 other than 1, I mean.

any power of 2 when written in base 3. god it's 2 am and i'm tired af.

>I think strengthening that point is the next step. All the other points are rock solid.
That point is not actually true, though. So strengthening it is a lost cause.

This proof is a dead end, OP. Trust me on this. Take it as an opportunity to learn what really is involved in P!=NP proofs, and move on.

It is pretty obvious that any power of 2 only has factors of 2 and any power of 3 only have factors of 3. Not sure what else you are trying to get at.

The sum of any multiple of three is divisible by three and there is no power of two divisible by three except when we consider sums including 3^0

Understanding why the proof is a dead end will help me get there. I'm not making another attempt after this, though. I've made a dozen attempts and this is basically the end of the line for me.

Sums of powers of 3. like 27 + 3.

Right, but no sums of powers of three will ever be a power of two except when we include 3^0.

You're right. I didn't see that, and that applies to all powers. You've disproven the proof. Thanks! :)

Keep your money. BTW

Suppose we included 3^0 because it is an interesting problem. We can identify all of

[math] S(A) \cap B [/math]

as an offset on powers of 3. This basically eliminates the second portion of the proof even in this scenario I do think.

The offset is interesting, but I'm basically at square 1 anyway because I need to prove a negative with my entire line of reasoning in P5.

P5 is trivially wrong because all subsets of length 1 can't be powers of 2, so you know if c != d without even checking {a, b}

what an asinine and stupid way to spend a fortune

although it all makes perfect sense. you lucked out enough to become a millionaire by adopting a long-shot esoteric currency, so obviously that makes you equipped to solve the world's hardest math problem with presumably no real background in theoretical math

>my fellow 12 year old
mods

>I have over $1M from being an early ETH investor, so I give it away pretty easily.
If this is true please stop wasting money like that. You sound like one of those self-bankrupting lottery winners.

Why do undergrads and pajeets always go for P=NP or Riemann? It's honestly sad.

People without a formal mathematical background are probably more likely to try solving problems like that because they're highly publicized (so laypeople are exposed to the fact they exist in the first place) and because not having a formal background means you won't have a very good understanding of how much you *don't* know. It's a case where the more actual experience you do have with the underlying topics the more aware you'll be of all the reasons why you almost certainly will not accomplish this task.
For a similar phenomenon there's the difference between what people in marketing or management at a company expect can be done vs. what the actual engineers / developers at a company expect can be done for a given pursued initiative. Generally the people who don't do any programming will have a more optimistic view of how much can be accomplished than the people who do carry out the programming. For the people not familiar with the implementation details it's much easier to imagine a given task will be tractable because their imagination of what the task is like has very little to do with what the task is actually like.

>I'm offering a $50 bounty in ETH
Translation: I am offering memes

>USD (fake paper money)
USD is arguably the most substantially "real" currency there is.
It's not really the same as a normal fiat currency because of Kissinger's deal with the Saudis to force everyone to pay for oil with US dollars.
As long as the modern world runs on and needs a continuous oil supply (and it definitely will for at least next hundred years), the modern world is effectively forced to run on and need US dollars.
Betting on continued dependence on oil is about as much of a risk as betting on there being a sunrise tomorrow morning.

Tesla made oil obsolete, the rest runs on coal and gas. Also bomb the shit out of saudis already, dammit.

>Tesla made oil obsolete
lol, no.
>Also bomb the shit out of saudis already
No you retard, that's the last thing you should do because this whole arrangement is what's keeping US currency and by extension the rest of modern global economics stable.
You Ron Paul buy gold plebs will never understand how much Kissinger saved everyone's asses with that deal.

Bullshit, normies will do everything TV tells them, there's no threat to economics there. They keep saudis as an excuse for terrorism to enslave people.

Are you claiming Henry Kissinger making a deal with the Saudis where they would force the rest of the world to purchase oil from OPEC using US dollars was just a made up story to distract people from secret US managed terrorism? Because that's one of the most idiotic conspiracy theories I've ever heard of. Most people don't even know about the Kissinger / Saudi petrodollar arrangement and it isn't a story that makes Kissinger or the US government look particularly noble, so I'm pretty sure it actually happened and other nations have actually been paying for oil with US dollars all these years and this has actually kept the US dollar valuable.