subject

Suppose there are three languages (i. e., problems), of which we know the following: 1. li is in p. 2. l2 is np-complete. 3. l3 is not in np. suppose also that we do not know anything about the resolution of the "p vs. np" question; for example, we do not know definitely whether p=np. classify each of the following languages as (a) definitely in p, (b) definitely in np (but perhaps not in p and perhaps not np-complete) (c) definitely np-complete (d) definitely not in np: l1 intersection l2.l1 [union] l2. l2cl3, where c is a symbol not in the alphabet of l2 or l3 (i. e., the marked concatenation of l2 and l3, where there is a unique marker symbol between the strings from l2 and l3). the complement of l3. based on your analysis, pick the correct, definitely true statement from the list below: a) l2cl3 is definitely in np. b) the complement of l3 is definitely not np-complete. c) l1 [union] l2 is definitely in np. d) l1 intersection l2 is definitely in p.

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 22.06.2019 22:00, robert7248
Competent nonverbal communication involves interacting with others in a manner that is appropriate for which of the following? select all that apply. situation task individuals
Answers: 3
image
Computers and Technology, 23.06.2019 03:50, nakeytrag
Iam a bacterium. i cause stomach cramps and diarrhea. i am caused by eating rotten foodssuch as chicken, fish, or eggs. sometimes turtles carry my bacteria. what am i?
Answers: 2
image
Computers and Technology, 23.06.2019 15:00, herchellann302
To check whether your writing is clear , you can
Answers: 2
image
Computers and Technology, 24.06.2019 08:00, nataliamontirl4230
Java the manager of a football stadium wants you to write a program that calculates the total ticket sales after each game
Answers: 1
You know the right answer?
Suppose there are three languages (i. e., problems), of which we know the following: 1. li is in p....

Questions in other subjects:

Konu
Mathematics, 08.04.2021 14:40
Konu
Mathematics, 08.04.2021 14:40
Konu
Social Studies, 08.04.2021 14:40
Konu
Mathematics, 08.04.2021 14:40