Polynomial-time Show that the computational problem has a polynomial-time verifies; you need to state what the certifica
Posted: Fri May 20, 2022 6:12 pm
Polynomial-time
Show that the computational problem has a polynomial-time
verifies;
you need to state what the certificate is in each case, and
what 𝑉 does to verify it.
1. 𝐸Q_𝐷I𝑉 = {〈𝑆〉: 𝑆 is equally
dividable}.
Here we call a set 𝑆 of integers
equally dividable if 𝑆 = A ∪ 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.
Show that the computational problem has a polynomial-time
verifies;
you need to state what the certificate is in each case, and
what 𝑉 does to verify it.
1. 𝐸Q_𝐷I𝑉 = {〈𝑆〉: 𝑆 is equally
dividable}.
Here we call a set 𝑆 of integers
equally dividable if 𝑆 = A ∪ 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.