It's a homework assignment, we were asked to read, understand, and present to our colleagues a short paper/article (suggested 4-6 pages) for our Computability, Decidability or Complexity class.The articles I was able to find in the past couple days using google scholar a way over what we were taught, plus, 50-100+ pages is way over the scope of my assignment. In class, we were provided with an introduction to the three topics, complexity classes, relations between them, and (mostly informal) proofs for the most representative problems from each class by modelling them using all kinds of Turing Machines.Any possible solutions? It's the first time in my life I'm touching anything related to research, I can barely understand even the scope of most papers I find.. I guess any advice would be welcome.
Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity?
complexity theory;computability;turing machines;research
By definition recent research papers usually contain non-trivial results and they often (always?) require a deep knowledge of the argument in order to be well understood, so if you pick a paper at random you'll probably find a bunch of obscure signs in your hands :-)So my suggestion is to look at old research papers (but not too old):pick a particular argument/theorem that you think you have understood informally (or an argument that intrigues you);read more about it on a theory of computation book or on Internet (for example start from Wikipedia and look at the references at the bottom, or search it on Google adding the keywords introduction or lecture notes);finally search the paper in which that argument/theorem was originally published and read it;For example one of the fundamental basic results in computational complexity is the (deterministic) Time Hierarchy theorem. Very informally the theorem says that given more time, a Turing machine can solve more problems. You can start reading the Wikipedia article, then pick a lecture note with a more formal proof Googling around (for example pick this one by Arora). Finally when you think that you've understood the proof well download and read the original paper R. Stearns and J. Hartmanis paper On the computational complexity of algorithms, 1965. You'll find that it contains even more details and is more formal.