CMSC351 Kruskal NP Completeness Assignment Spring 2025 This assignment is designed to be an introduction to the concepts used in our study of NP completeness later in the semester Some of the questions are trivial some are subtle You should have enough background to answer these questions 1 Comparison Networks An Analogy to NP completeness See the Wikipedia article on Sorting Networks Just read down to but not including the zero one principle We will be concerned with comparison networks in general not just sorting networks The size of a comparison network is the number of comparators and the depth is the number of levels of comparators For example in the Wikipedia article the initial sorting network for four inputs has size ve and depth three Notice that the rst two comparators can execute simultaneously so they are actually at the same level The parallel bubble sort network for six inputs has size fteen and depth nine In general a parallel bubble sort network for n inputs has size n n 1 2 and depth 2n 3 A minmax network inputs a list of size n and outputs a list of size n with the smallest value at the beginning of the list the largest value at the end of the list For example if the input is the list of size n 8 The output would be 1 Let n be a power of 2 40 80 30 60 10 70 20 50 10 80 a Show how to construct an e cient minmax network with n inputs Primarily minimize the depth and secondarily minimize the size Just describe the network do not justify b What is the exact size of your network c What is the exact depth of your network It turns out that comparison networks are very important on Mars where they have many applications A merging network inputs two sorted lists each of size n 2 and outputs the total list of values in order The Martians have discovered e cient merging networks Theorem There exist n input merging networks with depth lg n O 1 1 The Martians are especially interested in sorting networks They have proven that any sorting network must have depth at least lg n and size at least about n lg n They know that there are sorting networks with depth O log n 2 but do not know whether they can attain depth O log n A problem similar to sorting that Martians often need to solve is half sorting The input is two lists each of size n 2 and the output is the two lists independently sorted For example if the input is the list of size n 8 A standard sorting network would output 40 80 30 60 10 70 20 50 10 20 30 40 50 60 70 80 1Such merging networks were independently discovered on Earth by Batcher CMSC351 Kruskal NP Completeness Assignment Spring 2025 A half sorting network would output Not surprisingly sorting and half sorting are closely related 30 40 60 80 10 20 50 70 2 a Show that if sorting can be solved on a comparison network in depth O log n then half sorting can be solved on a comparison network in depth O log n b Show that if half sorting can be solved on a comparison network in depth O log n then sorting can be solved on a comparison network in depth O log n 2 Your two reductions show Corollary There exists a depth O log n sorting network if and only if there exists a depth O log n half sorting network The Martians extended this result to show that many other important comparison problems are equivalent to sorting and half sorting Any one of these special problems is solvable in depth O log n if and only if all of them are solvable in depth O log n Recently two Martian computer scientists Koco and Nevil made a startling discovery De nition A function f n is polylog n if there exists a constant k such that f n O log n k We will just say polylog when the parameter n is implicit Theorem If there exists a depth O log n sorting network then for every problem solvable on a comparison network in polylog depth there exists a depth O log n comparison network For details see their article in the prestigious Martian Online Journal Of Computer Science otherwise known as MOJO CS To nish the analogy Let L for Log depth be the class of problems solvable in depth O log n on a comparison network with n inputs Let PL for PolyLog depth be the class of problems solvable on a comparison network in polylog depth The theorem of Koco and Nevil shows that sorting is PL complete in other words if sorting is in L then every problem in PL is also in L The open problem on Mars is Does L PL 3 Is half sorting PL complete Justify Note that on Earth L and PL are used to represent di erent classes Also on Earth we have discovered an O log N depth sorting network but the constants are too large to be practical 2A plausible solution would be to take a half sorting network with 2n inputs and only use the top n inputs and outputs This is a way that a half sorting network could be used to sort but it is not a sorting network with n inputs Page 2 of 13 CMSC351 Kruskal NP Completeness Assignment Spring 2025 2 Boolean Formula Evaluation 4 a Consider the formula A B A C B C with assignment to the variables A B TRUE C FALSE Evaluate the formula You do not need to show your work b Consider the following Boolean circuit with assignment to the inputs A B TRUE C FALSE Evaluate the Boolean circuit Show your work by indicating the truth value produced by each gate Use the table in the back of this assignment A B C 1 2 3 4 5 6 7 8 10 output 9 Your manager calls you into the o ce with the following comment Starting next month every morning we will be receiving a large number of large Boolean formulas For each formula the assignment of TRUE s and FALSE s to the variables will be given We will evaluate each formula We at Alpha Beta Gamma believe that we can rely on you to write a lightning fast program to evaluate these Boolean formulas 5 You have no idea how to write such a program You scour the internet but cannot nd a satisfactory program to evaluate Boolean formulas However you do nd a great program to evaluate Boolean circuits You realize that you can evaluate a Boolean formula by converting it into an equivalent Boolean circuit in linear time and then evaluate the Boolean circuit with the computer program Convert following formula from Part 4a into the equivalent circuit Just draw the circuit A B A C B C 6 Assume the scenario is reversed You need to evaluate Boolean circuits but you …