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
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.