Abstract

Title: Completeness in the Polyonmial Time Hierarchy
Published: July 2001
Authors: Marcus Schaefer
Abstract: We are trying to compile a list of problems that reside in the polynomial hieararchy above the second level. The current list is incomplete: it does not contain some recent results (such as Stockmeyer and Modha's results on block-coding), nor does it list any of the results on petri-nets, non-monotonic logics, and databases (to mention some areas not included so far). It should also be pointed out that the results themselves have not been verified for the purposes of this report.
Full Paper: [postscript]