Computers and Technology, 07.03.2020 05:15, Miamonroe2004

Consider the problem COMPOSITE: given an integer y, does y have any factors other than one and itself? For this exercise, you may assume that COMPOSITE is in NP, and you will be comparing it to the well-known NP-complete problem SUBSET-SUM: given a set S of n integers and an integer target t, is there a subset of S whose sum is exactly t?Clearly explain whether or not each of the following statements follows from that fact that COMPOSITE is in NP and SUBSET-SUM is NP-complete:a. SUBSET-SUM ?p COMPOSITE. b. If there is an O(n3) algorithm for SUBSET-SUM, then there is a polynomial time algorithm for COMPOSITE. c. If there is a polynomial algorithm for COMPOSITE, then P = NP. d. If P ? NP, then no problem in NP can be solved in polynomial time.

Answers: 1

Show answers

Other questions on the subject: Computers and Technology

Computers and Technology, 22.06.2019 10:00, danthehero56

Which of the following is true of operations within a spreadsheet program’s built-in functions? a. operations within parentheses, then multiplication and division, and then addition and subtraction are computed. b. operations within parentheses, then addition and subtraction, and then multiplication and division are computed. c. multiplication and division, then addition and subtraction, and then operations within parentheses are computed. d. addition and subtraction, then multiplication and division, and then operations within parentheses are computed

Answers: 2

continue

Computers and Technology, 22.06.2019 20:40, broang23

Write a program that begins by reading in a series of positive integers on a single line of input and then computes and prints the product of those integers. integers are accepted and multiplied until the user enters an integer less than 1. this final number is not part of the product. then, the program prints the product. if the first entered number is negative or 0, the program must print “bad input.” and terminate immediately. next, the program determines and prints the prime factorization of the product, listing the factors in increasing order. if a prime number is not a factor of the product, then it

Answers: 2

continue

Computers and Technology, 22.06.2019 21:30, mima851

Elements such as fonts colors visual structure graphics and the interface of a web page should complement each other to ensure blank

Answers: 3

continue

Computers and Technology, 23.06.2019 00:30, lm18618

Which one of the following is considered a peripheral? a software b mouse c usb connector d motherboard

Answers: 2

continue

Do you know the correct answer?

Consider the problem COMPOSITE: given an integer y, does y have any factors other than one and itsel...