Acwruecmp.92
net.misc,net.math
utzoo!decvax!cwruecmp!decot
Fri Apr 30 22:05:26 1982
NP decidability verification decidability


A problem for you whizzes:

       A) Show that the problem of deciding whether or not NP = P is
          intractable,
or
       B) Show that verifying any solution to part A is an NP-complete
          problem,
or
       C) Show that the languages of the problems in parts A & B are
          not recursively enumerable,
or
       D) Show that there is no algorithm for determining whether parts
          A, B, or C have any solution,
or
       E) Give an algorithm for discovering which of parts A, B, or C
          are intractable.

(Extra Credit:  Prove that a non-deterministic Turing Machine cannot do
               any of these parts.)

                               (heehee)
                               - Dave Decot

-----------------------------------------------------------------
gopher://quux.org/ conversion by John Goerzen <[email protected]>
of http://communication.ucsd.edu/A-News/


This Usenet Oldnews Archive
article may be copied and distributed freely, provided:

1. There is no money collected for the text(s) of the articles.

2. The following notice remains appended to each copy:

The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996
Bruce Jones, Henry Spencer, David Wiseman.

You are viewing proxied material from infinitelyremote.com. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.