Wanted: Nondeterministic Turing Machine of Polynomial Time Complexity

From: Thomas A. Li (tli_at_corporola.com)
Date: 10/27/04

  • Next message: LK: "Problem creating a regular expression." 
    Date: Wed, 27 Oct 2004 10:58:17 -0400

    Hi, All,

    I'm interested in Computability Theory and having difficulty in finding some
    concrete examples of Nondeterministic Turing Machine (NDTM) of Polynomial
    Time Complexity to use in my research.

    So, I will set up a website to provide NDTM examples for public access after
    I have 5 examples.

    For this purpose, I'm collecting Nondeterministic Turing Machine (NDTM) of
    Polynomial Time Complexity, especially NP-complete NDTMs. Only complete and
    correct ones will be considered for publishing and their providers will be
    acknowledged.

    A submission of or a reference to such a NDTM is welcomed.

    Thank you for help in advance.

    Thomas Li
    Ottawa, Canada

  • Next message: LK: "Problem creating a regular expression."