All categories

3 years ago

Assuming P != NP, which of the following is true ?

Computers and Technology

2 answers:

7nadin3 [17]3 years ago

8 0

Answer:

B. NP-complete \cap P = \Phi

Explanation:

The is because no NP-Complete problem can be solved in polynomial time.

Assuming one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time. If that is the case, then NP and P set become same which contradicts the given condition.

White raven [17]3 years ago

7 0

Answer:

Answer is B, see explanations.

Explanation:

Answer is (B) NP−complete∩P=ϕ

Since, P≠NP, there is at least one problem in NP, which is harder than all P problems. Lets take the hardest such problem, say X. Since, P≠NP,X∉P .

Now, by definition, NP−complete problems are the hardest problems in NP and so X problem is in NP−complete. And being in NP, X can be reduced to all problems in NP−complete, making any other NP−complete problem as hard as X. So, since X∉P, none of the other NP−complete problems also cannot be in P.

You might be interested in

You have been asked to write a program that will ask the user for his or her pizza order and display it. The order will include

Dvinal [7]

Q asks to write

1. input statement that prompts the user for the type of cheese:

What kind of cheese you like?

Input TYPE OF CHEESE

2. Print statement that clearly displays the output message related to the type of cheese:

Print "Pizza has" TYPE OF CHEESE "type of cheese."

5 0

3 years ago

Differentiated instruction is designed to educate children through ________ techniques in order to ensure every student is being

EleoNora [17]

They use multiple techniques to help children.

7 0

3 years ago

What dose AUP stand for??????????

kipiarov [429]

Answer:

Acceptable Use Policy

Explanation:

A: Acceptable

U:Use

P:Policy

3 0

3 years ago

Read 2 more answers

Proper __ management is essenciales for meeting project deadlines

trapecia [35]

Proper Project management is essential for meeting project deadlines.

4 0

3 years ago

Create a Python program in a file named loops1.py that does the following: a. Use a while loop to keep asking the user for input

Rashid [163]

Answer:

mystr = input("Enter a string ")

length = len(mystr)

while length<10:

mystr = input("Enter a string ")

length = len(mystr)

if(length>=10):

break

if len(mystr)%2==0:

print(mystr.lower())

else:

print(mystr.upper())

Explanation:

The variable mystr is used to save user's input which is received with the input function

A second variable length is used to save the length of the input string Using a while statement the user is continually prompted to enter a string while length is less than 10.

If length is greater or equal to 10. We check for even or odd using the modulo (%) operator.

We use lower() and upper() to change the case of the string

7 0

3 years ago

Read 2 more answers