(Polynomial-time verifies, 20pt) Show that the following two
computational problems have
polynomial-time verifies; to do so explicitly state what the
certificate ππ is in each case, and what
ππ does to verify it.
Polynomial Time Verifies 20pt Show That The Following Two Computational Problems Have Polynomial Time Verifies To Do 1 (15.37 KiB) Viewed 52 times
= a) [10pt] SUBGRAPH = {{G, H): G contains H as a subgraph}. (See Section 0.2 for definition of subgraph.) b) [10pt] EQ_DIV = {(S):S is equally dividable}. Here we call a set of integers equally dividable if S = AU B for two disjoint sets A, B such that the sum of the elements in A is the same as the sum of the elements in B. E.g. {-3,4,5,7,9} is equally dividable as A = {-3,5,9} and B = {4,7} but S = {1,4,9} is not equally dividable. =
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!