Text File

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 <jgoerzen@complete.org> 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.