6 ms·

No nonempty interval of real numbers can be represented in a finite number of bits.

tgflynn 14y ago
That's exactly what floating point numbers are: representations of real number intervals as finite length bit strings. The number of bits simply determines the granularity of the representation (ie. the width of the intervals).
- konstruktor 14y ago
  Floating point numbers are approximations of real numbers, which isn't sufficient in this context. Solving a lossy representation of the problem isn't a reduction in the complexity theoretic sense.
  - tgflynn 14y ago
    In the case of this problem the set of possible paths is finite so it can, in principle, be sorted in order of increasing cost. The smallest cost delta between any 2 paths in the sorted list is the lowest cost edge in the graph (this probably assumes that all edge costs are positive) so you only need to continue the binary search until intervals of this size are reached. At that point the exact solution has been found. EDIT: There might be multiple paths with the same minimal cost but binary search will still find this value.
Fargren 14y ago
That depends on how you define your representation. It is useful for some problems to represent an interval with it's first bits, e.g. to take 0.101 as representing all numbers in the [0.101, 0.110) interval.
- konstruktor 14y ago
  You are correct. What I meant to say was: You cannot represent all the distinct real numbers in a nonempty interval using a finite number of bits.
  - mikeash 14y ago
    Why is that relevant?
mikeash 14y ago
I choose the nonempty interval [0, 1]. I have just represented it here in 48 bits (many of which are unnecessary, but bits are cheap). I don't think your statement is correct.
anothermachine 14y ago
Fortunately, non-empty intervals of real numbers do not exist in computer science.
- konstruktor 14y ago
  Did I get my mathematical terms wrong or are you confusing number representations on computers with computer science?

That's exactly what floating point numbers are: representations of real number intervals as finite length bit strings. The number of bits simply determines the granularity of the representation (ie. the width of the intervals).

konstruktor 14y ago
Floating point numbers are approximations of real numbers, which isn't sufficient in this context. Solving a lossy representation of the problem isn't a reduction in the complexity theoretic sense.
- tgflynn 14y ago
  In the case of this problem the set of possible paths is finite so it can, in principle, be sorted in order of increasing cost. The smallest cost delta between any 2 paths in the sorted list is the lowest cost edge in the graph (this probably assumes that all edge costs are positive) so you only need to continue the binary search until intervals of this size are reached. At that point the exact solution has been found. EDIT: There might be multiple paths with the same minimal cost but binary search will still find this value.

Fargren 14y ago

That depends on how you define your representation. It is useful for some problems to represent an interval with it's first bits, e.g. to take 0.101 as representing all numbers in the [0.101, 0.110) interval.

konstruktor 14y ago
You are correct. What I meant to say was: You cannot represent all the distinct real numbers in a nonempty interval using a finite number of bits.
- mikeash 14y ago
  Why is that relevant?

mikeash 14y ago

I choose the nonempty interval [0, 1]. I have just represented it here in 48 bits (many of which are unnecessary, but bits are cheap). I don't think your statement is correct.

anothermachine 14y ago

Fortunately, non-empty intervals of real numbers do not exist in computer science.

konstruktor 14y ago
Did I get my mathematical terms wrong or are you confusing number representations on computers with computer science?