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
hammer [34]
3 years ago
14

Let X and Y be two decision problems. Suppose we know that X reduces to Yin polynomial time. Which of the following statements a

re true?Explain
a. If Y is NP-complete then so is X.
b. If X is NP-complete then so is Y.
c. If Y is NP-complete and Xis in NP then X is NP-complete.
d. If X is NP-complete and Y is in NP then Y is NP-complete.
e. If X is in P, then Y is in P.
f. If Y is in P, then X is in P.
g. X and Y can't both be in NP
Computers and Technology
1 answer:
DerKrebs [107]3 years ago
4 0

Answer:

d. If X is NP - complete and Y is in NP then Y is NP - complete.

This can be inferred

Explanation:

The statement d can be inferred, rest of the statements cannot be inferred. The X is in NP complete and it reduces to Y. Y is in NP and then it is NP complete. The Y is not in NP complete as it cannot reduce to X. The statement d is inferred.

You might be interested in
A search engine that crawls uses
RoseWind [281]

Answer:

web crawlers or spider software

Explanation:

A search engine that crawls uses the web crawler or the spider software. And it also uses the server side JavaScript based crawlers and programming languages like Python and PHP. The search engine finds the content category through the meta keywords and directs the page to the index. The index contains details of similar types of pages, And each page has one category, and if category is not found which is rarest, a new category is being created.

7 0
3 years ago
Look at the data set below. {9, 12, 12, 15, 18, 20, 25} in this data set, what is the median
cluponka [151]

. Answer: Median: 15

8 0
3 years ago
Read 2 more answers
Declaring single arrays is done with a0 set(s) of straight brackets.
Nataly_w [17]
<span>The answer is False.  When declaring an array, we use 1 set of square brackets.</span>
7 0
2 years ago
Computer is an example of​
MAXImum [283]

Answer:

Computer is an example of electronic device.

7 0
3 years ago
Read 2 more answers
A palindrome is a string that reads the same from left to right and from right to left. Design an algorithm to find the minimum
stepladder [879]

Answer:

Explanation:

The following code is written in Python. It is a recursive function that tests the first and last character of the word and keeps checking to see if each change would create the palindrome. Finally, printing out the minimum number needed to create the palindrome.

import sys

def numOfSwitches(word, start, end):

   if (start > end):

       return sys.maxsize

   if (start == end):

       return 0

   if (start == end - 1):

       if (word[start] == word[end]):

           return 0

       else:

           return 1

   if (word[start] == word[end]):

       return numOfSwitches(word, start + 1, end - 1)

   else:

       return (min(numOfSwitches(word, start, end - 1),

                   numOfSwitches(word, start + 1, end)) + 1)

word = input("Enter a Word: ")

start = 0

end = len(word)-1

print("Number of switches required for palindrome: " + str(numOfSwitches(word, start, end)))

3 0
2 years ago
Other questions:
  • The _____ dialog box lets you specify which files are to be merged.
    14·1 answer
  • For what purpose is keylogging software used? a. To automatically translate input to another language as the user enters data b.
    10·1 answer
  • Wireless networks use radio frequency (RF) or radio techniques, which allows wireless transmissions to reach out in all directio
    6·1 answer
  • How do you know where the home row of the keyboard is?
    14·2 answers
  • A location in memory which stores a value, the value can change as the program is running is
    12·1 answer
  • HELP FAST
    14·1 answer
  • Can someone take away your points
    15·1 answer
  • search engines use software that combs the web to find webpages and add new data about them to the database. what is this softwa
    5·1 answer
  • If a friend gave a used Wii disc to someone, and they put it in their Wii, could they play it? Nintendo Switch games can only be
    14·1 answer
  • [2]<br> (c) Describe how the microprocessor can determine when to sound the clock alarm.
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!