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