NP算法代写 | Algorithms 3027/3927 Assignment 4

本次澳洲代写主要为np算法的assignment,分为三个部分

Algorithms 3027/3927 Assignment 4

Task 1: Among Us [50 marks]
You are playing your favourite social deduction game, Among Us, and it has nally come time to accuse
the imposters. You have kept track of which players have been cleared and by who, which players have
been accused and by who, and how sus each player is in general. You trust that any crewmate would only
clear a crewmate, and any crewmate would only accuse an imposter, but imposters cannot be trusted at
all. You must determine a group of players that could be imposters such that the sum of their sus is at
least some threshold.
Formally, you are given
 n: the number of players
 k: the number of imposters
 t: sus threshold
 s1; s2; :::sn: a number representing the sus of each player
 C: a list of ordered pairs (p; q) indicating player p has cleared player q
 A: a list of ordered pairs (p; q) indicating player p has accused player q
A subset I of the players f1; 2; : : : ; ng could be imposters if
 I contains exactly k players
 For any clear (p; q) in C, if p is not in I then q is not in I
 For any accusation (p; q) in A, if p is not in I, then q is in I
The sus of a subset I of the players is the sum of the sus of each player, ie
Pi2I si. The Among Us
decision problem is to determine if there exists a subset of players that could be imposters with sus at
least the threshold t.
Sus: 69

Figure 1: Example: Top = batman, right = cat, bottom = mini, left = shrek.
In Figure 1, each of the 4 players has sus, red double-arrows indicate accusations, blue single-arrows
indicate clears, and we are trying to nd 2 imposters. Formally:

 n = 4
 k = 2
 t = 105
 sbatman = 69; scat = 0; smini = 100; sshrek = 42
 C = [(shrek; batman); (cat;mini); (batman; shrek)]
 A = [(shrek; cat); (mini; shrek); (batman; cat)]
There are 6 subsets of size 2:
 fbatman; shrekg could be imposters, total sus: 111
 fbatman; catg could not be imposters because mini is accusing shrek, and because shrek is clearing
batman
 fbatman;minig could not be imposters because shrek is clearing batman, and because cat is clearing
mini, and because shrek is accusing cat
 fshrek; catg could not be imposters because batman is clearing shrek
 fshrek;minig could not be imposters because batman is clearing shrek, and because cat is clearing
mini, and because batman is accusing cat
 fcat;minig could be imposters, total sus: 100
Since there are two subsets that could be imposters with total sus 100 and 111, the answer to the Among
Us decision problem is YES.
Task 1a: Prove decision problem is in NP
(a) Describe a certi cate and a veri er.
(b) Give a brief justi cation of the correctness of the veri er.
(c) Give a brief justi cation that the veri er runs in polynomial time.
Task 1b: Prove decision problem is NP-hard
Your task is to give a polynomial-time Karp reduction from an NP-complete problem (see Appendix) to
the Among Us decision problem

(a) Describe how you transform an instance of the NP-complete problem into an instance of the Among
Us decision problem.
(b) Prove the correctness of your reduction, i.e. the instance of the NP-complete problem is a YES-
instance if and only if the instance of the Among Us decision problem created by your reduction is
a YES-instance.
(c) Prove that your reduction is polynomial-time.