Data Structures and Algorithms

   

Constructive Proof of Kannan’s Theorem Based Upon a Much Simpler Construction

Authors: Sunny Daniels

I appreciate the acknowledgement by Fortnow[1] of my, historically significant, I believe, first ever constructive proof of Kannan’s theorem[2], which I think was acknowledged as "folklore" (I thank Watanabe for this) in Watanabe[3] (I don’t think I currently have access to any university library system so I don’t think I currently have access to the full text of this). If I am not mistaken, I now have a much simpler construction (I thought of this years ago if I remember rightly but was a bit too busy with an IT job unrelated to complexity theory until recently to have the time to publish it) giving a constructive proof of Kannan’s theorem, based upon a particular type of universal Turing machine. The fact that this construction (if I am not mistaken) works is an easy consequence of either my earlier constructive proof[2] or Watanabe’s later proof of the same result as discussed by Fortnow[1]. (I know that my presentations here of this construction and proof are quite sketchy at present; I would appreciate some feedback from others before attempting to write up more detailed versions of them). Also, I think it can be used as the basis of a much simpler constructive proof of Kannan’s theorem: I also discuss this here.

Comments: 5 Pages. "Complexity Theory" would almost certainly be the best arXiv category for this paper, but there doesn't seem to be any corresponding viXra category.

Download: PDF

Submission history

[v1] 2023-07-07 03:24:16

Unique-IP document downloads: 198 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus