4 ms·
That doesn't seem at all obvious. It's pretty easy to prove that if you can answer whether or not there exists a path of length k in polynomial time then you ca
by gweinberg 13y ago
That doesn't seem at all obvious. It's pretty easy to prove that if you can answer whether or not there exists a path of length k in polynomial time then you can also find what that path is in polynomial time. They prove this in the Udacity course on complexity, which I found very interesting if not necessarily practically useful. But it seems to me that the possible values of k you can get grows exponentially with problem size, so you can't just use your decision algorithm on various kays to find the optimal k in polynomial time.
- ColinWright 13y agoThe maximum is bounded by the number of edges times the maximum edge cost.
- wolfgke 13y agoIt depends what encoding is used. If the edge costs are integers, this is true. Also such bounds are possible for rational costs (but you have to pay more attention). It gets a lot more difficult if non-rational edge weights are allowed.
- tgflynn 13y agoI think we're talking here about problems that can be fed to a digital computer and hence can be represented by a finite number of bits. I believe that would exclude non-rational weights.
- ColinWright 13y agoNot necessarily - quantities like, for example, sqrt(2) can be represented symbolically. So can quantities like e and pi. You can get around this by multiplying all edge costs by twice the number of edges divided by the smallest non-zero difference between costs, then rounding to integers. Or something similar.
- wolfgke 13y agoNo, it wouldn't exclude non-rational weights. Consider for example the field Q[sqrt{2}]. Any element a+b * sqrt{2} of it can be represented by two rational numbers a, b. Since any field extension is a vector space (in this case of dimension 2) the addition can be implemented trivially and the multiplication is (a1, a2) * (b1, b2) = (a1 * b1 + 2 * a2 * b2, a1 * b2 + a2 * b1) (#) A formula for inversion can easily be derived from (#). TLDR: there are different kinds of encoding than binary fractions.
- tgflynn 13y agoThe size of the set k may be exponential but if you have a decision function D(C) == 1 iff there exists a path of cost < C you can use that function to do a binary search over all k's in polynomial time because binary search is log time. Each call to D should give you 1 bit of the solution and with n bits you can represent numbers from 0 to O(2^n).