[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 21 KB, 306x320, archie_bunker.jpg [View same] [iqdb] [saucenao] [google]
6202108 No.6202108 [Reply] [Original]

Reminder that P=NP has been proven as of yesterday

http://arxiv.org/abs/1208.0954

Expect this to be big news in the coming weeks

>> No.6202115

>Constant ∆ (in the propositions) depends on transition relation of Turing machine MhNPi.

wouldn't this make it pseudopolynomial?

>> No.6202116

wrrrrooooonnnggg

>> No.6202119

P=0 and N=1

I can do algebra too.

>> No.6202120
File: 23 KB, 264x104, proof.png [View same] [iqdb] [saucenao] [google]
6202120

>release 30 versions
>not proof
>release 31th version
>proof

>> No.6202122

>>6202120
>31th

lrn2english

>> No.6202123

crank

>> No.6202124

>>6202119
this original joke brought to you by /sci/

>> No.6202125

>>6202108
>http://arxiv.org/abs/1208.0954
submitted august 2012

>> No.6202127

You're very late. Someone proved that this was impossible over a year ago.

http://arxiv.org/abs/1211.3492

>> No.6202129

Who cares?

>> No.6202130

>>6202127
>proved

they proved it in the same way this guy proved P=NP

>> No.6202138
File: 13 KB, 318x335, the joke.jpg [View same] [iqdb] [saucenao] [google]
6202138

>>6202130

>> No.6202140

Until a real-world solution is solved in polynomial time, no one will care about a strictly theoretical P=NP or P!=NP proof

>> No.6202141

>>6202140
>solution is solved

well, you know what I meant

>> No.6202145

It certainly isn't true. Equality doesn't hold. For example consider P=1 and NP=0.999...

>> No.6202212

So did anyone actually determine why this proof isn't valid or are we just going to be good /sci/entists and not consider it?

>> No.6202228

Hey OP, what is peer review?

>> No.6202231

This was already posted here. It is fatally flawed in that, although the theoretical computing time is polynomial, the memory required grows exponentially. If there is an exponential memory growth, then there is exponential computing time because memory growth doesn't happen magically. A polynomially bounded (in time) machine cannot use exponential memory because reading 2^n cells on a tape requires 2^n time steps.

>> No.6202243

>In the present paper
1) all the propositions whose proofs are obvious or follow from the previous text are omitted, and

>> No.6202248

>>6202108
>Submitted 4 Aug 2012
>Sergey E. Yakhontov (Russian: Серге́й Евге́ньевич Я́хонтов, Sergej Evgen'evič Jaxontov; December 13, 1926, Leningrad) is a Russian linguist
Nah.

>> No.6202252

>>6202145
If you're having math problems, I feel bad for you son. I have 98.9 repeating problems but 0.9 repeating is one.

>> No.6202256

>>6202248
the author is Sergey V. Yakhontov

lrn2read

>> No.6202258

>>6202228
>http://arxiv.org/abs/1208.0954
We are supposed to be the peer review before it gets submitted to be considered for publication.

>> No.6202302

>>6202231
>what is turing machine

>> No.6202303

N=1

>> No.6202333

>>6202302
what?

>> No.6202336
File: 92 KB, 200x200, ascetic.png [View same] [iqdb] [saucenao] [google]
6202336

Okay guys, I've to tell you this.

I didn't read the paper fully as I can't understand it, but I was thinking about the P, NP problem sometime back and somehow I _felt_ that it can be solved using a method employing a graph which shows a path exists or not for a particular class of problems, constructing Turing machine for the same. I know this sounds very vague, but It just felt right to me. If I'm not mistaken the paper seems to have a similar approach.

Maybe I've tapped into the higher conciousness or something.

>> No.6202341
File: 35 KB, 642x482, 1360540349466.jpg [View same] [iqdb] [saucenao] [google]
6202341

>>6202336
>I didn't read the paper fully as I can't understand it
>If I'm not mistaken the paper seems to have a similar approach

>> No.6202343

>>6202336
I've had moments where an idea felt right and even worked under many randomly generated sets of data, but eventually failed for some fundamental reason.

Implement your idea anon

>> No.6202345

>Implying papers claiming to prove it aren't common

>> No.6202356

>>6202341
I know my post is stupid and also I'm incredible sleepy atm. I just skimmed through it to grasp the basic approach.

>>6202343
I know that. I'm not implying anything with that stupid earlier post of mine. Just saying.

Anyway, good night.