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, 21.06.2019 14:00, ashley1460

Mr. johnson creates a game in which the players see the world from their avatar’s perspective. what genre of game is this?

Answers: 2

continue

Computers and Technology, 22.06.2019 10:00, IHeartDarkSide03

Which is a false statement considering copyright law? a. when people upload something to the internet they automatically receive a copyright for the work b. the work does not have to contain a copyright notice to be considered having a copyright c. copyright is legal term describing rights given to the creators for literary and artistic works d. personal pictures are always covered by copyrights

Answers: 1

continue

Computers and Technology, 22.06.2019 21:00, mazolethrin9632

Which of these is most responsible for differences between the twentieth century to the twenty-first century?

Answers: 2

continue

Computers and Technology, 24.06.2019 01:30, BIKRAMlawati5544

Could you find out how im still getting an 83 percent on this in edhesive a = input("enter an animal: ") s = input ("enter a sound: ") e = "e-i-e-i-o" print ("old macdonald had a farm, " + e) print ("and on his farm he had a " + a + "," + e) print ("with a " + s + "-" + s + " here and a " + s + "-" + s + " there") print ("here a " + s+ " there a " + s) print ("everywhere a " + s + "-" + s ) print ("old macdonald had a farm, " + e)

Answers: 2

continue

You know the right answer?

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