Hacker News Reader

Comment by jkaptur | Hacker News Reader

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.

View on HN

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.

> linear programming are problems that are worst-case NP-hard

Linear Programming (with rational coefficients; to avoid sophism) can be solved in polynomial time.

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.

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_i...

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).

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.

sorry, really genuinely interested in the structure here, reference?

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

The go-to example for something like that is Datalog.

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

Type-theory based proof assistants (coq, agda, lean, idris, ..) are like this.

The problem being that if you can reduce a problem to being well ordered on the naturals it is already in the computable set.

Note how the limits on recursion as given by the original paper apply to the fibonacci sequence, but restricted to the Natural numbers to avoid the -2 -1 1 0 1,1 2 portion that would break total ordering.

Any problem that you can map to von Neumann ordinals will be computable. Same thing with the Cantor diagonalization example below.

Basically if you can reduce your problem to a monoid, you can typically compute it easily.

But as a group has to be a magma with inverse, the recursive example provided couldn't be used in a case that function needed to be applied to algebras, rings, fields etc....

Note that as Cantor diagonalization was used as a counterexample to Laplacian causal determinism, showing that no two computational device can completely predict each other when defined by external behavior, there are further constraints.

For me, an easier lens to see if there is a P solution to a typically NP problem is looking at Schaefer's dichotomy theorem. Total Functional Programing is exactly equivalent to #3,

1) all relations which are not constantly false are true when all its arguments are true; 2) all relations which are not constantly false are true when all its arguments are false; 3) all relations are equivalent to a conjunction of binary clauses; 4) all relations are equivalent to a conjunction of Horn clauses; 5) all relations are equivalent to a conjunction of dual-Horn clauses; 6) all relations are equivalent to a conjunction of affine formulae.

The mapping to the Natural numbers is a leaky abstraction, as the Natural numbers are a non-empty totally ordered set with no upper bound.

Any function that takes finitely many natural numbers as arguments and produce a value which is a single natural number are by definition computable. That restricted problem will always be computable no matter if the more generalized problem is in NP or not.

https://ncatlab.org/ufias2012/files/turner.pdf

Decision tables [1] have that property. They have a finite number of states and you can test all of them.

If "smart contracts" in crypto land were written as decision tables, it might have helped a bit.

[1] https://en.wikipedia.org/wiki/Decision_table

This already exists: Coq, Idris, Agda, LEAN etc.

linear programming is not NP-hard. Integer linear programming is, but that's a different problem

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

> 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."

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

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.

Reply on news.ycombinator.com