Recently two Martian computer scientists Koco and Nevil made a startling discovery. Definition. A function f(n) is polylog(n) if there exists a constant k such that f(n) = 0((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 finish 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 different classes. Also on Earth, we have discovered an O(log N) depth sorting network, but the constants are too large to be practical Recently two Martian computer scientists Koco and Nevil made a startling discovery. Definition. A function f(n) is polylog(n) if there exists a constant k such that f(n) = 0((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 finish 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 different classes. Also on Earth, we have discovered an O(log N) depth sorting network, but the constants are too large to be practical