3 ms·
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 pr
by 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 agoHmm, 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 agoRight, 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 agoA 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 agoYeah 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 agosorry, really genuinely interested in the structure here, reference?
- Kranar 4y agoSure, 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 agoThe go-to example for something like that is Datalog.
- lapinot 4y agoBasically 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.
- nyrikki 4y agoThe 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 https://ncatlab.org/ufias2012/files/turner.pdf
- Ar-Curunir 4y agolinear programming is not NP-hard. Integer linear programming is, but that's a different problem