LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 343-345 of 486

    • Definability in Dynamic Logic 

      Meyer, Albert R.; Parikh, Rohit (1980-02)
      We study the expressive power of various versions of Dynamic Logic and compare them with each other as well as with standard languages in the logical literature. One version of Dynamic Logic is equivalent to the infinitary ...

    • Covering Graphs by Simple Circuits 

      Atai, Alon; Lipton, Richard J.; Papadimitriou, Christos H.; Rodeh, M. (1980-02)

    • On Linear Characterizations of Combinatorial Optimization Problems 

      Karp, Richard M. Papadimitriou, Christos H. (1980-02)
      We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP=co-NP -- a very unlikely event. We ...