Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
yes but that changes the problem and still there is the issue of all values can form a valid subset.. but a path may or may not exist (ordering matters) and so does existence of edges!
moreover there the ordering does not matter.. any sub set is a valid potential answer.. here a path may not exist (depending on the edge's direction, or if the edge exists at all)?
@Dmitry I am struggling to see how.. can you please elaborate: en.wikipedia.org/wiki/Subset_sum_problem - In subset sum we are given a fixed multiset (am I correct?) here I can repeat any edge any number of times. so doesn't it make them different ?
any directed graph. i mean other than a vertex having a direct edge to itself or the graph being disconnected pretty much any general graph not just digraphs.
Thank you. I understand. But this is regarding longest path. what about exact path. In that too it mentions negative and positive weights. why not just positive? for some similar reason (i don't see it why)?
2. In this link of problems in $P$ (en.wikipedia.org/wiki/P-complete) the examples are: "Circuit Value Problem (CVP) – Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate." Aren't they supposed to be just YES/NO problems in P. These seem functional version examples. I am confused here?
Thank you. I understood both parts. Follow up query though: 1. For an input $x$ with running time of $T_f$ given by some function $r_f(|x|)$ can we ALWAYS have a logic/function such that the decision version Turing machine $T_d$ has also the same running time i.e. $r_f(|x|)=r_d(|x|)$. Notice we even in decision variant are using the running time only over $x$?
