On Sun, Jan 17, 2016 at 12:45:51PM +0100, Nils Dagsson Moskopp wrote: > Do you want a global library of superoptimizer results?
https://en.wikipedia.org/wiki/Optimizing_compiler It has been shown that some code optimization problems are NP-complete, or even undecidable. In practice, factors such as the programmer's willingness to wait for the compiler to complete its task place upper limits on the optimizations that a compiler implementor might provide. (Optimization is generally a very CPU- and memory-intensive process.) In the past, computer memory limitations were also a major factor in limiting which optimizations could be performed. Because of all these factors, optimization rarely produces "optimal" output in any sense, and in fact an "optimization" may impede performance in some cases; rather, they are heuristic methods for improving resource usage in typical programs. ... The problem of determining an optimal set of macros that minimizes the space required by a given code segment is known to be NP-complete. https://en.wikipedia.org/wiki/Register_allocation Through liveness analysis, compilers can determine which sets of variables are live at the same time, as well as variables which are involved in move instructions. Using this information, the compiler can construct a graph such that every vertex represents a unique variable in the program. Interference edges connect pairs of vertices which are live at the same time, and preference edges connect pairs of vertices which are involved in move instructions. Register allocation can then be reduced to the problem of K-coloring the resulting graph, where K is the number of registers available on the target architecture. No two vertices sharing an interference edge may be assigned the same color, and vertices sharing a preference edge should be assigned the same color if possible. Some of the vertices may be precolored to begin with, representing variables which must be kept in certain registers due to calling conventions or communication between modules. As graph coloring in general is NP-complete, so is register allocation. However, good algorithms exist which balance performance with quality of compiled code. Contraint satisfaction is usually some subtype of SAT https://en.wikipedia.org/wiki/Boolean_satisfiability_problem Since the SAT problem is NP-complete, only algorithms with exponential worst-case complexity are known for it. In spite of this state of the art in complexity theory, efficient and scalable algorithms for SAT were developed over the last decade and have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints (i.e. clauses). Examples of such problems in electronic design automation (EDA) include formal equivalence checking, model checking, formal verification of pipelined microprocessors, automatic test pattern generation, routing of FPGAs, planning, and scheduling problems, and so on. A SAT-solving engine is now considered to be an essential component in the EDA toolbox. So, by enumering answers to one NPC problem, such as SAT, and storing them for efficient retrieval, you solve every isomorphic instance in the same domain, and every other NP problem that is isomporphic to it. As a happy result of coin mining proof-of-work efforts, and block chain replication/storage. It would also reward research into SAT solvers and other NP-complete problem solvers, but still allow for inefficient brute forcing. I'm sorry I hijacked your thread; I sent my ideas to the cryptography mlist last night. -- http://www.subspacefield.org/~travis/ | if spammer then j...@subspacefield.org "Computer crime, the glamor crime of the 1970s, will become in the 1980s one of the greatest sources of preventable business loss." John M. Carroll, "Computer Security", first edition cover flap, 1977 _______________________________________________ langsec-discuss mailing list langsec-discuss@mail.langsec.org https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
