Thread replies: 25
Thread images: 3
Thread images: 3
File: 1449610785504.jpg (247KB, 1280x1206px) Image search:
[Google]
247KB, 1280x1206px
IT'S HAPPENING!!!1!!1
>We shall define an interesting problem called MAS. We show MAS is a succinct version of
the known problem SUBSET–PRODUCT.
>When we accept or reject the succinct instances of MAS, then we are accepting or rejecting the equivalent large instances of SUBSET–PRODUCT.
>If we assume that P = NP, then the problems MAS and SUBSET–PRODUCT could be in
P–complete.
>However, this would imply that MAS is also in EXP–complete, because MAS is a succinct version of
SUBSET–PRODUCT and SUBSET–PRODUCT would be in P–complete.
>Nevertheless, MAS cannot be in EXP–complete and P–complete at the same time, because this will be a contradiction.
>Therefore, we can claim that P≠NP as a result of applying the reductio ad absurdum rule.
https://hal.archives-ouvertes.fr/hal-01233924v2/document
>>
>>7710842
>applying the reductio ad absurdum rule
No real proof would ever say that.
>>
Is this for real? Could OP remind the general public what the complexity classes P and NP mean?
>>
>>7710847
>P=NPists in denial
>>
>>7710847
>no real proof would use proof by contradiction
how's Calc treating you?
>>
>>7710850
>Is this for real?
No. This is student work making some student mistakes. Nothing to see here, move along.
>>
>>7710850
P = solvable on a deterministic Turing machine in polynomial time
NP = solvable on a nondeterministic TM in polynomial time = verifiable on a deterministic TM on polynomial time
>>
>>7710842
who is this semen demon
>>
File: CS "math".png (423KB, 490x684px) Image search:
[Google]
423KB, 490x684px
>>7710864
They wouldn't call it "a rule" and they would just say by contradiction and not "reductio ad absurdum". That's something a high school discrete math student would write
>>
>>7710898
Well then, he gets a D for form, but in terms of content it remains the same
>>
>>7710903
I think the girl in OP also gets a D for form.
>>
>>7710924
I'd prove her NP if you know what I mean
>>
>>7710842
Lara Croft?
>>
> MAS and SUBSET–PRODUCT could be in
P–complete.
> could be
Either I'm misreading this entirely, or there is a fundamental logical error.
Also, and probably more importantly, it's not clear that moving from EXP/NEXP to P/NP preserves complexity in the way that the author implies. (It's actually not even clear that his algorithm as described is in the appropriate complexity classes.)
Anyway, check out his previous work on the topic. It's similarly unlikely: http://arxiv.org/abs/1011.2730?context=cs
>>
Tfw p probably != np
>>
>>7710924
Looks like she might have Turner syndrome - small narrow shoulders, sort of a webbed neck. Still qt tho.
>>
File: 435435345.png (547KB, 800x533px) Image search:
[Google]
547KB, 800x533px
>>7711132
>nitpicking this hard in an attempt to find non-existent flaws
>>
>>7710847
You're right that no math person would end their proof like that but comp sci people learn to write proofs from the department of philosophy.
>>
>>7711318
The author isn't really a comp sci person. Pretty sure he's not even a professor anywhere. He's just some guy who posts a lot of attempted proofs of this thing.
>>
>>7710842
If p=np why do they have differenr names
Cekm8 meme scientists
>>
>>7710842
Can anyone confirm?
>>
>>7710842
Solved it for x.
> XMAS
Seasons greetings anons
>>
>>7710927
>nice pucci?
>>
>>7710955
I wouldn't trust what Vega writes either: he has tried (and failed) this proof many times
Thread posts: 25
Thread images: 3
Thread images: 3