Twilight comes to you for help with a special algorithmic friendship

>>29167305
Fuck her in the ponut

>>29167349
That doesn't solve the friendship problem

>>29167350
It makes her forget completely about it, problem solved

>>29167364
>Twilight would just forget about an exciting polynomial time reduction
u wot m8

>>29167305
i'm not too drunk and could try some advanced math but i'd have to translate it into my lang first to get everything and i'm too lazy for that

>>29167305
Come on guys, this is an easy question, you don't want to let twilight and pinkie down do you....?

>>29168658
(lol dw I have done the q, this isn't a hw thread)

Sounds like a weighted graph. Modified Dijkstra's should suffice. Too lazy to do a proof.

>>29167305
Independent set decision is np complete so there is probably no way. I have no idea how to prove anything like that.

>>29168722
You don't actually have to solve anything for the reduction
>>29168830
You have to do is reduce independent set to decent party, but I have no idea what to do lol

>>29168886
>independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.
We have to prove that all solutions to decent party are independent sets - the rest is already there in the definition.

Silly Twalot, we all know the answer is always 42

>>29168952
Wait, no. Fun table is complete graph - independent sets are impossible. I'm out of ideas.

>>29168952
>Prove that if there is a polynomial-time algorithm for solving DECENT-PARTY
then there is also one for the INDEPENDENT-SET decision problem.
Don't you have to construct a graph to be passed to INDEPENDENT-SET?

>>29167305
Fuck if I know, only math thing I understood was algorithm, but no clue what to do with that. The rest might as well be gibberish, I barely passed Pre-Calculus in highschool.

I know I solved this once in my life, but I totally can't remember right now since I am masturbating.

>>29167305
Does pinkie have a lookup table for the value of F[i,j] for all ponies, or is there some way to calculate that, or what?

>>29169408
It doesn't matter since you only need to show that it's possible in case you had.

>>29169421
But what's the point of showing if it's possible if we can't find values for F of [i,j]. It doesn't seem like a trivial data entry problem, but maybe I'm just autistic.

>>29167305

>Oversimplification.

The problem assumes that all guests invited to the party arrive at the same time and that fun remains constant over time.

Basic knowledge of parties will show that, for example, Rarity will arrive "fashionably late" and that interaction with Spike will degrade over time as he inevitable returns to "Did I mention how I saved the Crystal Empire?"

While C, the maximum capacity of the flat, can be determined by a fire marshal, fun can be reduced if the party feels "too crowded."

To maximize fun at a party, we must allow for guests to cycle in and out of the flat. For example, Fluttershy is uncomfortable with crowds but wants to get better at this. By inviting her to a "pre-party," she is able to interact with her close friends as they arrive, then be given an excuse to leave when she feels the party has become "too big."

Second, one must consider the helpful disposition of some friends. These are friends who may want to come early and help set up, or stay after and help clean. However, they have their limits, especially after an exhaustingly long party or when they feel they are being taken advantage of. The best way to deal with this is to "stagger" the guest list, say the party begins at a certain time to some friends, let the party approach C, then allow it to drain down to the point that it appears "over." This allows the helpful friend(s) to start the clean up early and leave before the party is technically finished, but it appears clean enough that the hostess can handle anything else herself.

Finally, there are the hardcore party ponies, they show up late and party until the sun comes up. They also have a tendency to scare shy friends, so keeping the two groups separate is beneficial. However, this third group is known for making parties epic, so it seems like the party would be less fun for not including them. Fortunately, this third group may not need to be invited as they often have a reputation for "crashing."

>>29169332
We already have a graph.

My troll instinct is telling me that it's inherently NP, but that's only after one quick read-through.

>>29171058
It's n*log(n) + n. Just sort the edges in descending order and then sum them until you either get T or exceed C. This is not what the problem is about. It's about complexity equivalence of two problems.

File: 1000000yrs in mspaint.jpg (86KB, 727x474px) Image search: [Google]

86KB, 727x474px

>>29168677
>you don't want to let twilight and pinkie down do you....?
I don't. But I want to let OP down because he's a faggot and deserves it. Besides, Twilight and Pinkie don't exist.

>>29171069
I'm pretty sure it's not that easy.
>>29167305
We're looking for a reduction from ISP to this one, which is trivial. For a graph and k, let C = k, T = k(k-1) and F[i,j] = 0 if i and j are connected and 1 otherwise. This means the ISP is no harder than the party problem.

>>29171383
i and j are always connected.

>>29167305
Get a bigger venue

I'm too hung over to deal with this shit.

>>29167305
I never took advanced maths beyond the basics because I hated it.

I still do and reading this annoys me because I feel it's just overcomplicating something simple. Like algebra.

>>29172399
It's an exercise for ponons who have been thinking about high tech computer maths. If you don't think about those things don't worry yourself about the problem being contrived. It's contrivances are for the sake of presenting the problem.