wu :: forums « wu :: forums - Worm Propagation » Welcome, Guest. Please Login or Register. Jan 26th, 2022, 3:38pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, Grimbal, ThudnBlunder, Icarus, SMQ, Eigenray, towr)    Worm Propagation « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Worm Propagation  (Read 9295 times)
Aryabhatta
Uberpuzzler

Gender:
Posts: 1321
 Re: Worm Propagation   « Reply #25 on: Oct 26th, 2004, 7:56pm » Quote Modify

Supposedly, 3 dimensional matching is reducible in a straight forward way to the minimum broadcast problem.

3 Dimensional Matching: Given a set S of 3n elements and a family F of subsets of S, such that each element of F is of cardinality 3, does there exist a subset H of F of cardinality n such that the union of elements of H is S.

(basically given some m > n, triples from S, can you find n triples which cover S. Since S is of size 3n, those n triples must be mutually disjoint, it is also known as the Exact Three Cover.)

3 Dimensional Matching is known to be NP-Complete.
 IP Logged
Sjoerd Job Postmus
Full Member

Posts: 228
 Re: Worm Propagation   « Reply #26 on: Mar 10th, 2005, 2:56pm » Quote Modify

I'm an infected computer, I will take these steps:
1. Enumerate the computers I can infect.
2. Choose uninfected computer that only I can infect, with the largest amount of links.
3. If that fails - all computers are somehow attached to other infects - choose one with as many links as possible, with the least amount of infected links, with the largest total of infect busyness.
4. If that fails, I can no longer infect anything, so I'm done !
 IP Logged
DewiMorgan
Newbie

Posts: 29
 Re: Worm Propagation   « Reply #27 on: Jun 2nd, 2006, 7:38pm » Quote Modify

Although it's NP-hard, the fun comes from constructing an effective, nearoptimal algorithm for a blind virus to spread most economically.

Longest-path and center-of-mass and most-grandchildren solutions all provide good general answers, but fail in some situations.

Consider a situation where you are attacking "target", which lies between a hub, connected in parallel to X machines, none of which are interconnected, and to a chain of Y machines.

X=Hub-target-A-B-C-D-E-...-Y

Clearly, if X>Y, then it's better to infect the hub machine first, so it can start infecting its children as soon as possible. This is despite the fact that it's not the "center" of the network, and it's not the longest path.

If X<Y, then it's best to infect the chain first, even though the first link only has a single outside connection, because that link leads to the majority of the network, which we want to infect.

It rapidly becomes more complicated when you start linking the leaves together, of course.

Any solution should be recursive (that is, each infected child should be able to run it too). And unless the infected machines broadcast which others they infect, and the machines can deliberate amongst eachother about who should infect whom, I's assume all machines are working blind.

As much as possible, though, each machine needs to mark already-infected machines in its internal map, remove the links between them, remove any subsequently isolated machines, and repeat the process each second (after it had connected to all its own children, it would consider itself an isolated node, and remove itself from the network, stopping its own action).

But guessing which others (other than its parent and the ones it infected itself) were infected, could be tricky.

This is because I think randomness may need to come into play. The chance of it selecting a target node could be divided by the number of available nodes, and multiplied by the suspected number of non-infected links from that node, for instance.

Also want to include a factor to compensate for the probability of another known infected node selecting that item. Possibly subtract 1/(number of nodes available to infected node) from the probability of selecting that item, for each infected node that shares it, capping at just over zero, but not marking it as actually infected unless the probability was 1/1.

Then scale all probabilities so the total probability of selecting SOME node is 1.

This algorithm would mean that nodes right in the center of a mass of infected machines might not get infected until one of the infected machines had exhausted all other probabilities, but that's probably not a bad thing.

I think the above is pretty close to optimal, though it  would be suboptimal for the first node in the Y>X state above.

It would also fail sometimes for:

x-x-infected-y

...since it would sometimes choose y first. Probably the choices should only be random where there are conflicts with other infected hosts, and should be deterministic for unshared nodes.

which brings us back to how to best choose deterministically.

THe weighting should include a measure of the netsork distance from other infected notes (other than passing through the current host), too. And probably a measure of the size of the tree behind it divided by the number of known-infected hosts on that tree.
 IP Logged
Newbie

Posts: 2
 Re: Worm Propagation   « Reply #28 on: Nov 26th, 2006, 6:10pm » Quote Modify

Very simple, most probably flawed logic while looking at this

after confusing ever myself with bad math here is an example for 7 seconds with infinit computers available infecting the maximum computers

0: x
1: x, 1x1
2: x, 2x1,1x2
3: x, 3x1,3x2,1x3
4: x, 4x1 6x2,4x3,1x4
5: x, 5x1,10x2,10x3,5x4,1x5
6: x, 6x1,15x2,20x3,15x4,6x5,1x6
7: x, 7x1,21x2,35x3,35x4,21x5,7x6,1x7

after 7 seconds you infect 127 computers
and now its so obvious, the equation for what i am now sure is probably the completely wrong problem is:
s = seconds assumeing you start at 0
x = number of computers infected

2^s-1 = x

this is assumeing perfect network layout and that the virus is smart enough to not infect the same computer more then once. which bwe have to assume to get any sort of real answer for this riddle

without more information about how the network is layed out the rest is theorycraft about 'weighting the larger branches of the network more heavily' and such

and now im ready for the flame about how i'm wrong and missed some big note, which is probably true because this just is too simply to have so many people thinking...

 « Last Edit: Nov 26th, 2006, 6:12pm by Shiladie » IP Logged
balakrishnan
Junior Member

Gender:
Posts: 92
 Re: Worm Propagation   « Reply #29 on: Jan 10th, 2007, 8:04pm » Quote Modify

Is this solved yet?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Worm Propagation   « Reply #30 on: Jan 11th, 2007, 1:51am » Quote Modify

on Jan 10th, 2007, 8:04pm, balakrishnan wrote:
 Is this solved yet?
Depends on what you consider solved. To do it perfectly is NP hard, and the brute force approach to do that was posted early on.
However a near optimal solution may be better in practice (especially if you don't know the entire layout beforehand). And there's nearly always room for improvement at that end.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
CowsRUs
Full Member

Why is it that cats are better then cows? Why not?

Gender:
Posts: 175
 Re: Worm Propagation   « Reply #31 on: Feb 12th, 2007, 9:19am » Quote Modify

I would infect other computers then infect more then infect more than start spamming emails and hope some idiot clicks on the spam with the virus
 IP Logged

"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
bosssssss3
Newbie

Posts: 4
 Re: Worm Propagation   « Reply #32 on: Mar 21st, 2007, 10:02am » Quote Modify

 IP Logged
Hippo
Uberpuzzler

Gender:
Posts: 919
 Re: Worm Propagation   « Reply #33 on: Apr 30th, 2007, 4:26am » Quote Modify

Sorry I had loooked for on all pages missing the title one ... this belongs here...

I will show that minimal gosip problem (worm propagation) is NP hard.

I will show that deciding whether mingosip=k providing you know mingosip in k,k+1 is NP complete.

I will show a reduction from the SAT CNF problem.

You have m clauses using n different variables alltogether.

Let k be chosen later.

I will construct graph with mingosip in k,k+1 having mingosip = k iff given formula is satisfable:

Construction will be started from starting vertex 0 for the gosip problem.

Let vertex 0 and newly created vertices xi,neg xi creates triangle.

Let vertex i is connected to both xi and neg xi.

And let us create path of length k-i-2 edges starting in vertex i.

Last vertex of the path being blotted before time k+1 forces that vertex i is blotted at time i+1.

In that case either xi or neg xi is blotted in time i.

Furthermore for i-th literal vertex (xi or neg xi vertex) we create hypercube sceletton connected to it such that under each literal there is at least m leaves in the last level.

This is the only bound for k (and it is lower bound).

And the last level is blottable in time k-2 iff the literal vertex is selected and in time k
iff it is not selected and the last vertex of path under vertex i is reachable in time k.

For l-th clause create and connect vertices cl,dl and for each literal y connect cl to l-th leave of the y tree.

Vertex cl must be blotable in time k-1 to
be able to blot dl before time k.

...
WQD
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »