Technical Report CS0699

Authors: S. Ben-David and S. Halevi
PDF - RevisedCS0699.revised.pdf
Abstract: We investigate the possibility that the current failure to resolve basic complexity theoretic questions stems from the independence of these questions with respect to the formal theories underlying our mathematical reasoning. We show that any question in the field of computational complexity, that can be shown to be independent of the axioms of Peano Arithmetic is `practically insignificant'. If, using any known mathematical paradigm, $P \neq NP$ can be shown to be independent of Peano Arithmetic, then $NP$ has extremely-close-to-polynomial deterministic time upper bounds. In particular, in such a case, there is a {\em DTIME}$(n^{log \ast (n)})$ algorithm that computes {\em SAT} correctly on infinitely many huge intervals of input lengths. We provide a complete characterization of the worst case behavior of languages whose location in the complexity hierarchy is independent (with respect to sufficiently strong proof systems). Such languages are, on one hand, easily computable for long stretches of inputs, and, on the other hand, they are complex infinitely often. (We also define an explicit example of such a language). Our results hold for both the Turing Machine and the Non-Uniform Circuit complexity models.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion