LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 352-354 of 486

    • A T=0(2^n/2), S=0(2^n/4) Algorithm for Certain NP-Complete Problems 

      Schroeppel, Richard; Shamir, Adi (1980-01)
      In this paper we develop a general prupose algorithm that can solve a number of NP-complete problems in time T=0(2^n/2) and space S=0(2^n/4). The algorithm can be generalized to a family of algorithms whose time and space ...

    • A Machine Language Instruction Set for a Data Flow Processor 

      Aoki, Donald J. (1979-12)
      A data flow processor is a computer in which instructions are data driven and enabled for execution by the arrival of their operands. Data flow processors execute data flow programs, normally represented as program graphs, ...

    • A Space Bound for One-tape Multidimensional Turing Machines 

      Loui, Michael C. (1979-11)
      Let L be a language recognized by a nondeterministic Turing machine with one d-dimensional worktape of time complexity T(n). Then L can be recognized by a deterministic Turing machine of space complexity (T(n)logT(n))^d/d+1. ...