1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
RUDIKE [14]
3 years ago
12

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and

S is polynomial time reducible to R. Which of the following statements are true?
A. R is NP complete
B. R is NP Hard
C. Q is NP complete
D. Q is NP hard
Computers and Technology
1 answer:
levacccp [35]3 years ago
5 0

Answer:

B. R is NP Hard

Explanation:

Given:

S is an NP complete problem

Q is not known to be in NP

R is not known to be in NP

Q is polynomial times reducible to S

S is polynomial times reducible to R  

Solution:

NP complete problem has to be in both NP and NP-hard. A problem is NP hard if all problems in NP are polynomial time reducible to it.

Option B is correct because as given in the question S is an NP complete problem and S is polynomial times reducible to R.

Option A is not correct because R is not known to be in NP

Option C is not correct because Q is also not known to be in NP

Option D is not correct because Q because no NP-complete problem is polynomial time reducible to Q.

You might be interested in
The radix sort
Taya2010 [7]

Answer:

A.Treats array entries as if they were strings that have same length.

Explanation:

The radix sort treats the array values as the strings.First it compares the LSB(Least Significant Bit) of the array values and then moves to the right one by one upto MSB(Most Significant Bit).So we can say that the radix sort treats the entries of the array as strings and compare them.So the answer is option A.

4 0
4 years ago
People express more. often through the ___. language than written language
Oxana [17]
Verbal language because somebody's verbal words are more receptive then ones written word
5 0
4 years ago
Read 2 more answers
7. Accepting things that happen without trying to change them is known as
alukav5142 [94]

Answer:

accept people for who they are instead of trying to change them

Explanation:

i don't know if this is right or wrong but i hope this helped you :)

3 0
3 years ago
You used range in definite loops earlier in the course. The output of the range function is a sequence, which is a list of integ
Leya [2.2K]

Answer:

The answers is [0,1,2,]. I hope this helps you out. Have a wonderful rest of your day. <3  <3  <3

Explanation:

3 0
3 years ago
Write an application that displays every perfect number from 1 through 1,000. A perfect number is one that equals the sum of all
matrenka [14]

Answer:

Written in Python

for num in range(1,1001):

    sum=0

    for j in range(1,num+1):

         if num%j==0:

              sum = sum + j

                   if num == sum:

                        print(str(num)+" is a perfect number")

Explanation:

This line gets the range from 1 to 1000

for num in range(1,1001):

This line initializes sum to 0 for each number 1 to 1000

    sum=0

This line gets the divisor for each number 1 to 1000

    for j in range(1,num+1):

This following if condition line checks for divisor of each number

<em>          if num%j==0: </em>

<em>               sum = sum + j </em>

The following if condition checks for perfect number

                   if num == sum:

                        print(str(num)+" is a perfect number")

5 0
3 years ago
Other questions:
  • Write a program that reads an unspecified number of integers, determines how many positive and negative values have been read, a
    13·2 answers
  • Variables set equal to patterns are said to be:_______.
    7·1 answer
  • In the case below, the original source material is given along with a sample of student work. Determine the type of plagiarism b
    7·1 answer
  • Which of the following statements are not true about TCP? (Multiple answers)
    6·1 answer
  • Describe security risks associated with downloading items online
    8·1 answer
  • If you have a database of books in the library and you would like to find all books published after January 1, 2008, what criter
    7·1 answer
  • Your manager has requested you keep a timesheet showing how many hours you work each day and what projects you work on during th
    13·2 answers
  • Who is the host in super monkey ball?
    14·1 answer
  • How are online sources used? Check all that apply.
    6·2 answers
  • South Africa is the main supplier of which minerals in the world​
    10·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!