[ 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   
>> No.1574549

Does /sci/ really not care about this? God this board sucks.

P=/=NP, by the way. Mistype.

>> No.1574557

So the most important man in the 21st century is a fucking Indian?

>> No.1574562

>>1574549
we cared for the first 200 thread

>> No.1574563

It's not that /sci/ doesn't care, it's just that this is the ninth thread or so about this.

>> No.1574564

>>1574524
We don't really care about computer "science"

>> No.1574579

no surprise right? cause most people believed P =/= NP.

>> No.1574592

i will get excited when it gets confirmed, people have claimed proofs of this before.

>> No.1574607

So, this is important how?

Chemfag here. I probably won't get what it all means, just tell me what we can/can't do with this.

>> No.1574614
File: 21 KB, 512x384, 1216077385267.jpg [View same] [iqdb] [saucenao] [google]
1574614

>>1574524

Those fucking news pages man.

Especially the last one.
Just look at it!
>biggest mystery is solved
>deolalikar used reasoning and application
>the process took a lot of work
>this revelation is one of the best
>he gets a million dollar for sure

WTF at least try to sound professional.

The others also have errors, but this one is of the hook

>> No.1574615

>>1574607

probably nothing because if P=/=NP, then it just confirms what most people already believe anyway.

>> No.1574624

>>1574607

this basically means nothing, computer scientists have already been assuming that P =/= NP so its no surprise. if it was proven that P =NP, now that would be something to get excited about.

>> No.1574634

>>1574624
Oh.

So this isn't important except that we know for certain what we thought anyway?

>> No.1574636

I'm still not sure what P != NP means, and I'm a CS student.
meh, I'll read the wiki article later
I won't read the paper yet, it's like 100 pages and I don't even fully understand what P = NP means

>> No.1574637

I saw this on slashdot yesterday, and was hoping for a sticky on /sci/ (wishful thinking, apparently).
Anyway, expect about a year of peer review before the proof is solidified.

Here is the paper:
http://www.scribd.com/doc/35539144/pnp12pt

>> No.1574641

>>1574607

it means there is no efficient way to calculate e.g. protein structure prediction (refering rosetta@home).
So if you ever had the dream of calculating some complex chemical reactions through computer simulation .. you can forget that now

>> No.1574652

>>1574636
If you're a CS student, you wanna eventually take a class on complexity theory.
There are two types of problems:
Problems in P (which are solvable in a polynomial number of steps)
and
Problems in NP (which have solutions that are verifiable in a polynomial number of steps).
It is pretty obvious that P is a subset of NP.
The P NP problem asks if the reverse inclusion is also true.

For example, sorting is a problem in P, and sudoku is a problem in NP.

>> No.1574658

>>1574636

What semester are you?
You probably weren't introduced to Computability and Complexity Classes yet .. it's all a part of theoretical computer science

>> No.1574664

>>1574652
(continued)
You might know from calculus that polynomials grow relatively slowly (compared to, say, exponential functions). This is why "polynomial time" algorithms are good: because they can solve problems faster.

>> No.1574669

>>1574664
>>1574658
>>1574652
Yes, I took a lot of classes about complexities (O notation and all that), but not about P and NP, I'll see it later. College in my country is slow

>> No.1574680

>>1574652
yeah, I heard about that from other students talking.
Basically if P = NP is true it means that if you can check if an answer for a problem is valid in polynomial time then you can solve the problem in polynomial time too somehow.

>> No.1574684

>>1574680
Exactly right.

>> No.1574687

are there problems that cant be verified in P?

>> No.1574697

>>1574687
I'm not sure what you mean.
Are you asking if there's a problem in P that is not in NP? The answer is no, since P is a subset of NP.

>> No.1574699

>>1574687
P is a set of problems
if by problems that can be verified in P you mean problems that can be verified in polynomial time then you are asking if there are NP problems. Yes, there are.