Pages: [1] 2 :: one page |
|
Author |
Thread Statistics | Show CCP posts - 1 post(s) |
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 16:43:00 -
[1]
Edited by: Eventy One on 10/08/2010 16:44:30 This post is for you computer scientists / mathematician types.
The hardest problem in Computer Science is undoubtably the P=NP problem which deals with the concept of non-determinism in polynomial time. It is of interest to computer scientists because it is a measure of how hard a problem actually is. Imagine, for example, entrusting all of your EVE Secrets to a crytographic key that was 'easy' to solve rather than 'hard'. How do you measure 'easy to solve' and 'hard to solve' in a computer science sense.
Enter P=NP.
Many have long felt that P!=NP but could not prove it. Proving it was considered to be so hard it made the top ten Millennium Prize Problem list which meant if you could solve the P=NP problem you'd be given $1,000,000 and a whack of mathematical/CS awards.
Recently somebody has put forward an apparent proof. The jury is still out on this, but if his proof proves correct THIS IS BIG NEWS.
|
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 16:46:00 -
[2]
Edited by: Stick Cult on 10/08/2010 16:46:37 Congrats, this has nothing to do with Eve.
ibtm
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 16:48:00 -
[3]
Originally by: Stick Cult Congrats, this has nothing to do with Eve.
Hmm. Eve being a computer simulation, you don't think CCP deals with hard problems? Let me correct you:
Originally by: Stick Cult Congrats, this has nothing to do me.
|
Culmen
Caldari Blood Phage Syndicate Dead Terrorists
|
Posted - 2010.08.10 16:49:00 -
[4]
This is astounding news, but its not eve related.
Still alot of comp sci people are going to be disappointed if it's true. and further more why do i even need a sig? |
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 16:52:00 -
[5]
Edited by: Stick Cult on 10/08/2010 16:52:22
Originally by: Eventy One
Originally by: Stick Cult Congrats, this has nothing to do with Eve.
Hmm. Eve being a computer simulation, you don't think CCP deals with hard problems? Let me correct you:
Originally by: Stick Cult Congrats, this has nothing to do me.
Congrats, you also fail at grammar. Yes, CCP deals with hard problems, but mostly problems with server load balancing, rather than cryptography, which you cite as a use in the OP. Now, if this has any relevance to an MMO, please share.
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
Liang Nuren
Parsec Flux War.Pigs.
|
Posted - 2010.08.10 16:59:00 -
[6]
Originally by: Stick Cult
Congrats, you also fail at grammar. Yes, CCP deals with hard problems, but mostly problems with server load balancing, rather than cryptography, which you cite as a use in the OP. Now, if this has any relevance to an MMO, please share.
There are lots of reasons why P != NP is important in a MMO. Here's one that touches on the heart strings of anyone with goods scattered over the universe: http://en.wikipedia.org/wiki/Travelling_salesman_problem
"In the theory of computational complexity, the decision version of the TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly."
-Liang -- Eve Forum ***** Extraordinaire On Twitter Blog
|
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 17:03:00 -
[7]
Originally by: Stick Cult Yes, CCP deals with hard problems, but mostly problems with server load balancing, rather than cryptography, which you cite as a use in the OP.
P=NP is not a cryptographic problem. I cited that as an example. It is a problem difficulty problem, or an algorithm problem; which is why it is so important in computer science / math.
Do you enjoy lag? If not - what exactly do you think CCP looks at to solve lag? They look at how long an algorithm should take against how long it actually takes.
The lag solvers in Eve deal with P=NP problems.
|
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 17:05:00 -
[8]
Edited by: Stick Cult on 10/08/2010 17:06:11
Originally by: Liang Nuren
Originally by: Stick Cult
Congrats, you also fail at grammar. Yes, CCP deals with hard problems, but mostly problems with server load balancing, rather than cryptography, which you cite as a use in the OP. Now, if this has any relevance to an MMO, please share.
There are lots of reasons why P != NP is important in a MMO. Here's one that touches on the heart strings of anyone with goods scattered over the universe: http://en.wikipedia.org/wiki/Travelling_salesman_problem
"In the theory of computational complexity, the decision version of the TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly."
-Liang
Autopilot optimization? Very important issue... However, I will never stop poasting.
edit: Now seems like a good time to say that I have no clue what the uses of this are.
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 17:07:00 -
[9]
Originally by: Stick Cult Autopilot optimization? Very important issue... However, I will never stop poasting.
You mock, but the same algorithm that optimizes the autopilot confirms that all systems in eve are connected, and that routes can actually be flown.
From the perspective of the server, which you connect to, to play this game, EVE systems are all nodes in a connected graph.
Still - you can be forgiven for not understanding that.
|
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 17:10:00 -
[10]
Originally by: Eventy One
Originally by: Stick Cult Autopilot optimization? Very important issue... However, I will never stop poasting.
You mock, but the same algorithm that optimizes the autopilot confirms that all systems in eve are connected, and that routes can actually be flown.
From the perspective of the server, which you connect to, to play this game, EVE systems are all nodes in a connected graph.
Still - you can be forgiven for not understanding that.
Of course I mock, I'm half troll, from my father's side.
Tbh, the more I keep reading about the applications of this, the more interested I am. And it also reminds why I quit computer science... MY HEAD!!!
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
|
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 17:13:00 -
[11]
Originally by: Stick Cult Of course I mock, I'm half troll, from my father's side.
Tbh, the more I keep reading about the applications of this, the more interested I am. And it also reminds why I quit computer science... MY HEAD!!!
Ever notice that the lag solvers in EVE rarely post to the forums?
My theory is that their heads are spinning so much, (from looking at P=NP problems) that they just never get a chance to post.
|
Cebraio
|
Posted - 2010.08.10 17:16:00 -
[12]
Originally by: Eventy One ... but if his proof proves correct THIS IS BIG NEWS.
fixed
The IF is the important part.
I found this interesting read today: 10 signs a claimed mathematical breakthrough is wrong
Also this does not belong into "EVE General Discussion". Be it MMO related or not.
|
Rakshasa Taisab
Caldari Sane Industries Inc. Initiative Mercenaries
|
Posted - 2010.08.10 17:17:00 -
[13]
Every comp. scientist already assumed P!=NP and based all their practical applications of on that assumption. If the proof turns out to be good it's up at the level of those not expunged upon due to margin size, which do not really change practical applications at all.
|
Exordium8
Minmatar Hell's Horsemen HYDRA RELOADED
|
Posted - 2010.08.10 17:18:00 -
[14]
Well, I kind of hope that there is a flaw in the proof somewhere. As someone who works with software, I was hoping someone would find p=np. Still, if it's correct, good for him. 100 page proof though --------------------------------- Pillage, then burn. Everything is air-droppable at least once. There is no 'overkill.' There is only 'open fire' and 'time to reload.
|
wizard87
|
Posted - 2010.08.10 17:20:00 -
[15]
Originally by: Eventy One
Originally by: Stick Cult Congrats, this has nothing to do with Eve.
Hmm. Eve being a computer simulation, you don't think CCP deals with hard problems? Let me correct you:
Originally by: Stick Cult Congrats, this has nothing to do me.
My grandma has a computer. Can we talk about her here too?
She's quite old.
|
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 17:23:00 -
[16]
Originally by: wizard87
Originally by: Eventy One
Originally by: Stick Cult Congrats, this has nothing to do with Eve.
Hmm. Eve being a computer simulation, you don't think CCP deals with hard problems? Let me correct you:
Originally by: Stick Cult Congrats, this has nothing to do me.
My grandma has a computer. Can we talk about her here too?
She's quite old.
Does she still use AOL?
My grandfather does, it's quite sad.
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
Kazuo Ishiguro
House of Marbles
|
Posted - 2010.08.10 17:25:00 -
[17]
Originally by: Cebraio
Originally by: Eventy One ... but if his proof proves correct THIS IS BIG NEWS.
fixed
The IF is the important part.
I found this interesting read today: 10 signs a claimed mathematical breakthrough is wrong
Also this does not belong into "EVE General Discussion". Be it MMO related or not.
Until it passes peer review, I would invite people to read the paper for themselves. --- 34.4:1 mineral compression |
Richard Christy
|
Posted - 2010.08.10 17:26:00 -
[18]
ibtm
|
Culmen
Caldari Blood Phage Syndicate Dead Terrorists
|
Posted - 2010.08.10 17:26:00 -
[19]
Originally by: Stick Cult Edited by: Stick Cult on 10/08/2010 17:06:11
Originally by: Liang Nuren
Originally by: Stick Cult
Congrats, you also fail at grammar. Yes, CCP deals with hard problems, but mostly problems with server load balancing, rather than cryptography, which you cite as a use in the OP. Now, if this has any relevance to an MMO, please share.
There are lots of reasons why P != NP is important in a MMO. Here's one that touches on the heart strings of anyone with goods scattered over the universe: http://en.wikipedia.org/wiki/Travelling_salesman_problem
"In the theory of computational complexity, the decision version of the TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly."
-Liang
Autopilot optimization? Very important issue... However, I will never stop poasting.
edit: Now seems like a good time to say that I have no clue what the uses of this are.
Here' another NP-hard problem The Bin Packing Problem
Suppose you have a Freighter and a hanger full of Ships of various sizes. There's not enough room for all of them, so you'll have to make multiple trips.
Figure out how to load the freighter in a manner that minimizes the number of trips.
Also related is the Knapsack Problem, in which you try to fill your cargohold to maximize the profit when it reaches Jita. Figure out a way and further more why do i even need a sig? |
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 17:28:00 -
[20]
Originally by: Culmen Here' another NP-hard problem The Bin Packing Problem
Suppose you have a Freighter and a hanger full of Ships of various sizes. There's not enough room for all of them, so you'll have to make multiple trips.
Figure out how to load the freighter in a manner that minimizes the number of trips.
Also related is the Knapsack Problem, in which you try to fill your cargohold to maximize the profit when it reaches Jita. Figure out a way
CCP solves this one by leaving it to the player
|
|
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 17:29:00 -
[21]
Originally by: Culmen
Originally by: Stick Cult Edited by: Stick Cult on 10/08/2010 17:06:11
Originally by: Liang Nuren
Originally by: Stick Cult
Congrats, you also fail at grammar. Yes, CCP deals with hard problems, but mostly problems with server load balancing, rather than cryptography, which you cite as a use in the OP. Now, if this has any relevance to an MMO, please share.
There are lots of reasons why P != NP is important in a MMO. Here's one that touches on the heart strings of anyone with goods scattered over the universe: http://en.wikipedia.org/wiki/Travelling_salesman_problem
"In the theory of computational complexity, the decision version of the TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly."
-Liang
Autopilot optimization? Very important issue... However, I will never stop poasting.
edit: Now seems like a good time to say that I have no clue what the uses of this are.
Here' another NP-hard problem The Bin Packing Problem
Suppose you have a Freighter and a hanger full of Ships of various sizes. There's not enough room for all of them, so you'll have to make multiple trips.
Figure out how to load the freighter in a manner that minimizes the number of trips.
Also related is the Knapsack Problem, in which you try to fill your cargohold to maximize the profit when it reaches Jita. Figure out a way
I typically just throw in the big stuff then fill up the remaining nooks and crannies with small stuff like isotopes (when hauling pos fuel) or trit or something... Also interesting, again.
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
Akita T
Caldari Caldari Navy Volunteer Task Force
|
Posted - 2010.08.10 17:38:00 -
[22]
Edited by: Akita T on 10/08/2010 17:39:15
For those that do not know what the heck P=NP implies.
Quote: In essence, the question P = NP? asks: Suppose that "yes"-answers to a "yes"-or-"no"-question can be verified "quickly". Then can the answers themselves also be computed "quickly"?
There ya go.
_
Beginner's ISK making guide | Manufacturer's helper | All about reacting _
|
Eventy One
Magellan Exploration and Survey Mordus Angels
|
Posted - 2010.08.10 17:41:00 -
[23]
Originally by: Akita T
Quote: In essence, the question P = NP? asks: Suppose that "yes"-answers to a "yes"-or-"no"-question can be verified "quickly". Then can the answers themselves also be computed "quickly"?
There ya go.
Nice. Thanks Akita.
|
Culmen
Caldari Blood Phage Syndicate Dead Terrorists
|
Posted - 2010.08.10 17:41:00 -
[24]
Edited by: Culmen on 10/08/2010 17:44:00 Edited by: Culmen on 10/08/2010 17:42:45
Originally by: Stick Cult
Originally by: Culmen
Here' another NP-hard problem The Bin Packing Problem
Suppose you have a Freighter and a hanger full of Ships of various sizes. There's not enough room for all of them, so you'll have to make multiple trips.
Figure out how to load the freighter in a manner that minimizes the number of trips.
Also related is the Knapsack Problem, in which you try to fill your cargohold to maximize the profit when it reaches Jita. Figure out a way
I typically just throw in the big stuff then fill up the remaining nooks and crannies with small stuff like isotopes (when hauling pos fuel) or trit or something... Also interesting, again.
Ah, but supposes you freighter has 980k m3s , and you got 20 battleships(50k m3 each) and 63 battlecruisers(15k m3 each).
You load all the battleships first, and fit 19 of them. do the run You then load the other battleship 1 battleship, and can only fit 62 battlecruisers you end up doing a third run with only one BC in your hold
Now suppose you had a Bin packing algorithm. You punch it up and spits back out. Load 1: 18Battleships 5 Battlecruisers. Load 2: 2Battleships 58 Battlecruisers.
There you just saved yourself a trip.
Now imagine doing the math if you had hundreds of BSs and BCs, and threw in frigs cruisers and destroyers. That's where a bin-packing algorithm would be useful.
And this is just the pretend simplified eve universe, IRL stuff gets worse. And thats just the basic bin packing problem, try the Multi-Dimensional Bin Packing Problem (With/without rotation) Where you try fit an actual 3-dimensional object in a bin and factor in weight.
and further more why do i even need a sig? |
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 17:48:00 -
[25]
Quote: And thats just the basic bin packing problem, try the Multi-Dimensional Bin Packing Problem (With/without rotation) Where you try fit an actual 3-dimensional object in a bin and factor in weight.
Now THAT'S some cool ****. Never knew any of this had to do with P=NP/P!=NP...
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
qpod
Caldari Q-POD
|
Posted - 2010.08.10 18:09:00 -
[26]
I hope it will help to fight lag.
|
Kiritsubo
Ritual Suicide
|
Posted - 2010.08.10 18:29:00 -
[27]
Edited by: Kiritsubo on 10/08/2010 18:29:18 Fixing rockets is hard.
|
Stick Cult
Unspoken Autonomy.
|
Posted - 2010.08.10 18:30:00 -
[28]
Originally by: Kiritsubo Edited by: Kiritsubo on 10/08/2010 18:29:18 Fixing rockets is hard.
You know what else is hard?
Originally by: CCP Tuxford my bad. Rest assured I'm being ridiculed by my co-workers.
|
Cade Windstalker
Caldari
|
Posted - 2010.08.10 18:33:00 -
[29]
This is, I would hope, covered in Akita's link but basically P = NP means that if you solve the P subset of the NP problem space then, IF we prove P = NP, you can simply apply that solution to the entire problem space.
To put this in Eve terms it means you only need to invade and conquer one system to know that you'll be able to take all the other systems =P
(please note, P = NP does NOT hold for system takeovers, I was making a joke)
P = NP DOES have a lot of implications for algorithm optimization. Not necessarily for Eve but it might and if not now then maybe in the future
Yeah, great news, thanks for the heads up Eventy
|
|
CCP Zymurgist
Gallente C C P
|
Posted - 2010.08.10 18:49:00 -
[30]
Moved from General Discussion.
I want to read his paper
Zymurgist Community Representative CCP Hf, EVE Online Contact Us |
|
|
|
|
|
Pages: [1] 2 :: one page |
First page | Previous page | Next page | Last page |