LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 370-372 of 486

    • Minimum Register Allocation is Complete in Polynomial Space 

      Loui, Michael C. (1979-03)
      The Minimum Register Allocation Problem is to determine the minimum number of registers required to evaluate an arithmetic expression. A pebble game on directed acyclic graphs is used to prove that this is complete is ...

    • A Network Traffic Generator for Decent 

      Strazdas, Richard J. (1979-03)
      Computer network traffic generators provide a means for supplying benchmark results and for measuring computer network performance at all levels. Eventually they will also aid in fault diagnosis. The network traffic generator ...

    • With what Frequency are Apparently Intractable Problems Difficult? 

      Meyer, A.R.; Paterson, M.S. (1979-02)
      An algorithm is almost polynomial-time (apt) iff there is a polynomial p such that for all n, the algorithm halts within p(n) steps on all by at most p(n) inputs of size at most n. It is nown that for NP-complete and ...