1/

2/

Suppose we want to show that the problem HamPath is NP-hard, using the fact that we already know the problem SubsetSum is NP-hard. Then we must show... HamPath /P and SubsetSum /P. HamPath sp SubsetSum. HamPath NP and SubsetSum /P. HamPath NP and SubsetSum NP. SubsetSum p HamPath. HamPath /P and SubsetSum NP. If we say that HamPath P Sat, this means... (mark all that apply) If there is a polynomial-time algorithm for indicating whether a graph has a Hamiltonian path, then there is a polynomial-time algorithm for indicating whether a Boolean formula has a satisfying assignment. There is a polynomial-time computable function f such that, for every graph G with a Hamiltonian path, f(G) is a Boolean formula with a satisfying assignment, and for every graph G without a Hamiltonian path, f(G) is a Boolean formula without a satisfying assignment. There is a polynomial-time computable function f such that, for every graph G and potential witness p,f(G,p) outputs 0 or 1 to indicate whether p is a Hamiltonian path in G. There is a polynomial-time computable function f such that, for every graph G,f(G) is a Boolean formula with a satisfying assignment. If there is a polynomial-time algorithm for indicating whether a Boolean formula has a satisfying assignment, then there is a polynomial-time algorithm for indicating whether a graph has a Hamiltonian path. There is a polynomial-time computable function f such that, for every graph G,f(G) outputs 0 or 1 to indicate whether G has a Hamiltonian path