7 ms·

Great essay. Maybe another thing to note is that in industry we often don't need the singular best answer, but one that is "close" or "good". In fact, sometimes

Great essay. Maybe another thing to note is that in industry we often don't need the singular best answer, but one that is "close" or "good". In fact, sometimes this is a requirement - like a sudoku solver that can handle impossible boards by generating a solution with a small number of collisions. As evidenced by the fact that traveling salespeople exist (and are not, in general modeling experts or big AWS users), approximate solutions are often significantly easier to find - both practically and in theory. I bring this up because it's interesting... and because my professors really didn't emphasize it until deep into my undergraduate career. So someone today might be one of today's lucky 10,000.

Animats 4y ago
Right. Both the traveling salesman problem and linear programming are problems that are worst-case NP-hard, but far easier for almost all cases. The halting problem is an extreme case of this. While there are programs for which halting is either undecidable (with infinite memory) or NP-hard, for most useful programs, it's decidable. The Microsoft Static Driver Verifier is a proof of correctness system used by Microsoft to eliminate crash-type bugs from Windows drivers. It's the main reason that kernel drivers don't crash Windows any more. It decides the halting problem for drivers. If it can't reach a decision in some fixed length of time, the driver is rejected. If it's that difficult to decide if a kernel driver finishes, you're doing it wrong.
- aleph_minus_one 4y ago
  > linear programming are problems that are worst-case NP-hard Linear Programming (with rational coefficients; to avoid sophism) can be solved in polynomial time.
  - dragontamer 4y ago
    Hmm, the above poster probably meant "linear programming with integers" being NP-hard (because it is). When its "smooth", its actually solvable in polynomial time.
    - Animats 4y ago
      Right, see [1]. Same concept, though - worst case far harder than the average case, and the worse case is rare. [1] https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency_in_the_worst_case https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency_i...
- OkayPhysicist 4y ago
  A problem I've thought about lately has been making a programming language that optimizes for being expressive up to, but not including, being Turing complete (specifically, making non-terminating programs unexpressible).
  - Kranar 4y ago
    Yeah you can definitely make a language that is not Turing complete but your goal of "up-to" is not possible. For any complexity class C that is not Turing complete, there is a complexity class C' that is a strict super-set of C and is also not Turing complete.
    - convolvatron 4y ago
      sorry, really genuinely interested in the structure here, reference?
      - Kranar 4y ago
        Sure, the insight/intuition comes from diagonalization, or perhaps more directly from Cantor's theorem. For any complexity class O(F(N)), there must exist a complexity class O(2^F(N)) that is strictly a superset of O(F(N)). If F(N) is decidable then so too is 2^F(N). https://en.wikipedia.org/wiki/Cantor%27s_theorem https://en.wikipedia.org/wiki/Cantor%27s_theorem
    - deleted 4y ago
      [deleted]
  - chaosite 4y ago
    The go-to example for something like that is Datalog.
  - lapinot 4y ago
    Basically you disallow general recursion (while loops, etc) and just allow structural/well-founded/inductive recursion (for loops, finite structure walking, etc). https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming Type-theory based proof assistants (coq, agda, lean, idris, ..) are like this.
- Ar-Curunir 4y ago
  linear programming is not NP-hard. Integer linear programming is, but that's a different problem
taeric 4y ago
In optimization terms, this is the "optimality gap." And, often you can set bounds on that, as well. :D
- deong 4y ago
  Yep. And there are the formal optimality gaps like "this algorithm provably finds a solution in polynomial time no less than twice the optimum tour length", and there are also the informal "I have no proof of anything, but this algorithm usually finds optimal tours or tours within 1% of optimality on problems of up to 10 million cities" type of gaps. Both are useful to know and understand in practice. If my job were to solve TSP instances, I'd not bother trying to tell someone why it's hard. I'd through Iterated Lin-Kernighan or something similar at it and go get some lunch.
OkayPhysicist 4y ago
That's interesting. My Algorithms professor illustrated this point by handing us Kirkman's schoolgirl problem[0] as a homework assignment. Sure the naive solution falls into the category of "intractable withing the lifespan of the universe", but with some clever heuristics you can find one of the solutions quickly (A lackluster program in a couple minutes, a well-thought-through one instantly). [0] https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem
JohnFen 4y ago
> one that is "close" or "good" I remember an old physicist friend's comment about his books of tables to look up common things (sine, cosine, log, etc. -- yes, this was a long time ago). They had a precision of three decimal places. He said "for almost every problem, three is plenty. More than that just increases the work for the same result in the end."

Animats 4y ago

Right. Both the traveling salesman problem and linear programming are problems that are worst-case NP-hard, but far easier for almost all cases. The halting problem is an extreme case of this. While there are programs for which halting is either undecidable (with infinite memory) or NP-hard, for most useful programs, it's decidable. The Microsoft Static Driver Verifier is a proof of correctness system used by Microsoft to eliminate crash-type bugs from Windows drivers. It's the main reason that kernel drivers don't crash Windows any more. It decides the halting problem for drivers. If it can't reach a decision in some fixed length of time, the driver is rejected. If it's that difficult to decide if a kernel driver finishes, you're doing it wrong.

aleph_minus_one 4y ago
> linear programming are problems that are worst-case NP-hard Linear Programming (with rational coefficients; to avoid sophism) can be solved in polynomial time.
- dragontamer 4y ago
  Hmm, the above poster probably meant "linear programming with integers" being NP-hard (because it is). When its "smooth", its actually solvable in polynomial time.
  - Animats 4y ago
    Right, see [1]. Same concept, though - worst case far harder than the average case, and the worse case is rare. [1] https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency_in_the_worst_case https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency_i...
OkayPhysicist 4y ago
A problem I've thought about lately has been making a programming language that optimizes for being expressive up to, but not including, being Turing complete (specifically, making non-terminating programs unexpressible).
- Kranar 4y ago
  Yeah you can definitely make a language that is not Turing complete but your goal of "up-to" is not possible. For any complexity class C that is not Turing complete, there is a complexity class C' that is a strict super-set of C and is also not Turing complete.
  - convolvatron 4y ago
    sorry, really genuinely interested in the structure here, reference?
    - Kranar 4y ago
      Sure, the insight/intuition comes from diagonalization, or perhaps more directly from Cantor's theorem. For any complexity class O(F(N)), there must exist a complexity class O(2^F(N)) that is strictly a superset of O(F(N)). If F(N) is decidable then so too is 2^F(N). https://en.wikipedia.org/wiki/Cantor%27s_theorem https://en.wikipedia.org/wiki/Cantor%27s_theorem
  - deleted 4y ago
    [deleted]
- chaosite 4y ago
  The go-to example for something like that is Datalog.
- lapinot 4y ago
  Basically you disallow general recursion (while loops, etc) and just allow structural/well-founded/inductive recursion (for loops, finite structure walking, etc). https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming Type-theory based proof assistants (coq, agda, lean, idris, ..) are like this.
Ar-Curunir 4y ago
linear programming is not NP-hard. Integer linear programming is, but that's a different problem

taeric 4y ago

In optimization terms, this is the "optimality gap." And, often you can set bounds on that, as well. :D

deong 4y ago
Yep. And there are the formal optimality gaps like "this algorithm provably finds a solution in polynomial time no less than twice the optimum tour length", and there are also the informal "I have no proof of anything, but this algorithm usually finds optimal tours or tours within 1% of optimality on problems of up to 10 million cities" type of gaps. Both are useful to know and understand in practice. If my job were to solve TSP instances, I'd not bother trying to tell someone why it's hard. I'd through Iterated Lin-Kernighan or something similar at it and go get some lunch.

OkayPhysicist 4y ago

That's interesting. My Algorithms professor illustrated this point by handing us Kirkman's schoolgirl problem[0] as a homework assignment. Sure the naive solution falls into the category of "intractable withing the lifespan of the universe", but with some clever heuristics you can find one of the solutions quickly (A lackluster program in a couple minutes, a well-thought-through one instantly). [0] https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem

JohnFen 4y ago

> one that is "close" or "good" I remember an old physicist friend's comment about his books of tables to look up common things (sine, cosine, log, etc. -- yes, this was a long time ago). They had a precision of three decimal places. He said "for almost every problem, three is plenty. More than that just increases the work for the same result in the end."