Google and Oracle’s $9 billion “copyright case of the decade” could be headed for the Supreme Court Computer Science

---

• Google and Oracle’s $9 billion “copyright case of the decade” could be headed for the Supreme Court
• What does E[...|...;...] mean in a mathematical formula? E.g. the state value function in Markov decision processes
• How can I excel in my comp sci degree when I’m not good at math?
• Math MS to CS PhD: Suggestions
• Highly confident that this is NP-hard, and I try to show it with generalization
• Complexity of a code
• Intuition and generalization for NP-completeness of deciding correct mapping of a Sudoku puzzle??

Google and Oracle’s $9 billion “copyright case of the decade” could be headed for the Supreme Court Posted: 25 May 2019 03:50 PM PDT submitted by /u/pacinothere [link] [comments]

What does E[...|...;...] mean in a mathematical formula? E.g. the state value function in Markov decision processes Posted: 25 May 2019 11:23 AM PDT I'm trying to implement this paper about Markov decision processes but am struggling with some of the formulas, for example the state value function definition at the end of the second page. I can understand everything in it except the double struck E[...] notation at the start, I've never seen it before, can't derive what it means from the formula and don't know what to look up. The only thing I can think of is set builder notation considering the 'where pipe "|"' and the big double struck letter but that wouldn't make any sense here. Could anyone help me out with this? Thanks a lot for reading! submitted by /u/LetsGetTrashed [link] [comments]

How can I excel in my comp sci degree when I’m not good at math? Posted: 26 May 2019 12:43 AM PDT Hi everyone, I switched my major from biology to CompSci this last year and I'm finally taking a course where math is necessary. I still have to take the first year Calculus's and discrete maths. In the class we are learning Java and I feel so discouraged because I can't even compile a simple code using factorials. Honestly speaking, this class is kicking my ass. Can someone who was terrible at math and still got through their degree give me some advice on how I can get through the math part without dropping out??? Any advice is appreciated, I'm really lost out here. Thank you! submitted by /u/pengupants [link] [comments]

Math MS to CS PhD: Suggestions Posted: 25 May 2019 11:09 PM PDT Hi, ​ After completing my MS in Math, I'm looking to apply to CS PhD programs, primarily as I'm interested in quantum computation and that I want to work on inter-disciplinary projects. ​ Would anyone have any recommendations for CS programs that may be interested in accepting a student with a math/physics background. Any recommendations for schools someone like me could target. submitted by /u/JM753 [link] [comments]

Highly confident that this is NP-hard, and I try to show it with generalization Posted: 25 May 2019 06:56 PM PDT My motivations is to show that given some X problem such n^2 x n^2 Sudoku Puzzle. There is a valid subset of poly-time algorithms that can generate their n^2 x n^2 solutions in a constrained environment. ​ Figuring out how to generate their solutions in poly-time in constraint I believe to be NP-hard and I intend to make a generalization to show just that. ​ To prove I created an algorithm. To test for n^2 x n^2 try it yourself by changing the numbering to a valid output. (eg. 12 x 12 is a 4 x 3) ​ ​ https://cs.stackexchange.com/questions/107183/will-this-algorithm-always-solve-a-constrained-sudoku-puzzle-in-quadratic-time ​ I created a constraint environment it shifts the elements to generate n! subsets of n^2 x n^2 ​ l = [1,2,3,4,5,6,7,8,9] squares = [] for index in range(len(l)): l.append(l.pop(0)) squares.append(l.copy()) #Everything below here is just printing for s in range(3): for d in range(0,9,3): for si in range(s,9,3): for li in range(d,d+3): print(squares[si][li], end = '') print('') ​ Decision Problem I believe is NP-hard ​ Deciding Shift of Elements or DSE ​ Suppose, I want to create another constraint poly-time semi-solver that takes in a n x n box so that it can recover the remaining puzzle in poly-time. ​ The decision problem we must face when coding a Semi-Solver Algorithm.... Is DSE it's solved when we brute-froce a correct solution to a random n^2 x n^2 Sudoku. We take that mapping into a constraint to permute n! solutions to a subset of Sudoku. (Refer to algorithm link to clarify confusion) ​ Now, for intuitive concept. Let's take a look at this pseudo-code ​ ../Backtracking n^2 x n^2 puzzle ../Solution recovered and checked! [123][456] [456][789] [789][123] ../Discovering mapping of n^2 x n^2 [123][000] [000][000] [000][123] ./Row-1 and Row-6 DSE found ..../Finding remaining shifts ​ ​ Deciding Problem for General Sudoku is NP-complete ​ Under the knowledge of this fact ​ It is safe to say that any variation and generalization of the Decision Problem of Sudoku is NP-hard. ​ Therefore, I am generalizing that finding a poly-time semi-solver for any n^2 x n^2 puzzle is NP-hard, because it is akin to the Decision Problem of Sudoku. ​ Heck, I can make a game that didn't use numbers but just shapes and it still would be NP-complete. submitted by /u/Hope1995x [link] [comments]

Complexity of a code Posted: 25 May 2019 06:32 AM PDT If I have a code that goes once to every cell of an array and repeat doing it "the highest value in the array" times, is the complexity of the code is O(n)? submitted by /u/orenog [link] [comments]

Intuition and generalization for NP-completeness of deciding correct mapping of a Sudoku puzzle?? Posted: 25 May 2019 02:42 PM PDT ​ Definitions Semi-Solver - Suppose we have an algorithm that solves in poly-time for subsets of n^2 x n^2 Sudoku if and only if a n x n box is mapped out into a correct solution. ​ Shifting Elements- Suppose, we use a backtracking solver for any random n^2 x n^2 puzzle. After the solution is recovered, the computer analyzes the ordering of the elements (numbers) and we hard-code that same mapping so that it can create a new n! set of valid solutions. ​ DSE-Decision problem of correct Shifting of Elements to recover solutions efficiently. ​ The Another Solution Problem (ASP) of a problem Π is the following problem: for a given instance x of Π and a solution s to it, find a solution to x other than s. ​ Decision Problem- When given any puzzle of n^2 x n^2 size with completing the n x n box, what is the correct Shifting elements we should use to efficiently recover the remaining solution? ​ Suppose, we take the Sudoku problem and see if it can be reduced into Deciding Shifting Elements for arbitrary Sudoku Puzzles. ​ ​ For illustration, suppose I fill in the bottom-left box correctly. Now, to show that finding the correct DSE for any puzzle is in NP. A non-deterministic machine finds at least one possible correct permute-shifting of the n x n box that yields a valid grid. [0, 3, 4][0, 0, 0][8, 0, 1] [5, 0, 7][0, 9, 0][0, 3, 0] [0, 9, 1][2, 3, 0][0, 6, 7] [3, 0, 0][6, 0, 8][9, 0, 2] [0, 7, 0][9, 0, 2][0, 0, 5] [0, 1, 2][3, 0, 0][0, 7, 8] [0, 5, 6][7, 0, 0][1, 2, 3] [0, 8, 9][1, 0, 3][4, 5, 6] [0, 2, 3][0, 0, 6][7, 8, 9] ​ After finding at least 1 DSE (by backtracking or NTM) I can now solve subset puzzles more efficiently. It is now possible to efficiently solve these puzzles on a Deterministic machine. ​ The deterministic Machine can now poly-time solve the n! subset. ​ [2, 3, 4][5, 6, 7][8, 9, 1] [5, 6, 7][8, 9, 1][2, 3, 4] [8, 9, 1][2, 3, 4][5, 6, 7] [3, 4, 5][6, 7, 8][9, 1, 2] [6, 7, 8][9, 1, 2][3, 4, 5] [9, 1, 2][3, 4, 5][6, 7, 8] [4, 5, 6][7, 8, 9][1, 2, 3] [7, 8, 9][1, 2, 3][4, 5, 6] [1, 2, 3][4, 5, 6][7, 8, 9] ​ Recap for Clearer Intuition ​ ​ The Another Solution Problem (ASP) of a problem Π is the following problem: for a given instance x of Π and a solution s to it, find a solution to x other than s. ​ ​ The Another Solution Problem (ASP) of a problem Sudoku is the following problem: for a given instance of a n^2 x n^2 puzzle of Sudoku and a DSE s to it, find another DSE to Sudoku other than s. ​ Non-Deterministic Algorithm ./Taking n^2 x n^2 puzzle and completing special n x n box ./Permute all possible mappings to find correct DSE's ./Found 3 correct DSE semi-solvers for Deterministic Machine ​ ​ Proving that hard-coding any of the sub-set cyclic languages of valid n^2 x n^2 latin sqaures. Can generate valid latin squares in poly-time on a deterministic machine. And in some poly-time solve the rest of a puzzle. Thinking about it all valid general n^2 x n^2 grids are trivially following a poly-time mappable cyclic/shift language. Those latin squares can be generated in poly-time. ​ [2, 3, 4][5, 6, 7][8, 9, 1] [5, 6, 7][8, 9, 1][2, 3, 4] [8, 9, 1][2, 3, 4][5, 6, 7] [3, 4, 5][6, 7, 8][9, 1, 2] [6, 7, 8][9, 1, 2][3, 4, 5] [9, 1, 2][3, 4, 5][6, 7, 8] [4, 5, 6][7, 8, 9][1, 2, 3] [7, 8, 9][1, 2, 3][4, 5, 6] [1, 2, 3][4, 5, 6][7, 8, 9] ./Analyzing shifting of elements to create n! constrained subset for efficient solving ​ ​ DSE is probably just as hard as ASP ​ SAT has been proven to be ASP-complete in a poly-time reduction. SAT <p ASP DSE is in ASP So DSE for general n^2 x n^2 Sudoku must be hard. ​ So, finding a poly-time algorithm that can decide on its own for which DSE isn't likely going to work. ​ ​ ​ ​ http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf submitted by /u/Hope1995x [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States