subject

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.

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
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
image
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
image
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
image
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
You know the right answer?
Consider the problem COMPOSITE: given an integer y, does y have any factors other than one and itsel...

Questions in other subjects:

Konu
History, 02.06.2021 02:30