(Polynomial-time verifies, 20pt) Show that the following two computational problems have polynomial-time verifies; to do
Posted: Fri May 20, 2022 4:47 pm
(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.
= 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. =
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 53 times