We know that Kurt Gödel, unhappy with having only completeness and incompleteness theorems named after him, also essentially invented the P vs NP question in a 1956 letter to John Von Neumann. Unfortunately, there were no blogs back then, so we had to wait until the 1980s to read it, and Cook, Karp & co. [...]
Archive for the ‘Complexity’ category
Nash beats Gödel: On the history of complexity and cryptography
17 February 2012Do waterfalls play chess? and other stories
13 August 2011I finally took the time to read Scott Aaronson’s new paper Why philosophers should care about computational complexity (there’s a post about it with lots of comments on his blog). Summary: Aaronson, knowing that I’m writing my thesis at the moment, took the liberty of preparing an introduction for me. Thanks! I’m going to include [...]
Time is unpredictable
19 February 2011This post is inspired by the question Are runtime bounds in P decidable? asked by John Sidles on the CSTheory website, and the answer given by Emanuele Viola. Is there an automatic procedure to determine whether a given Turing machine, known to be halting, operates within time bound O(f) (assuming f is a computable function)? [...]
Undecidability in terms of complexity
13 December 2010In his classic book Computational Complexity, Papadimitriou writes (page 59) that Undecidability is in some sense the most lethal form of complexity. I’ve just come across a paper with a very interesting remark along the same lines: Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination by A. Carbone and S. Semmes, [...]
On a philosophical quest
2 December 2010This was originally posted as an answer to the question Why go to theoretical computer science/research? on the Theoretical Computer Science Stack Exchange website. One of the main reasons why I find the theory of computation (“my” branch of theoretical computer science) fascinating and worth studying is the following one: it provides us with a [...]
Developments in Language Theory 2010: Where tetration has lease
15 August 2010Tomorrow I’m leaving for Canada, to attend the 14th International Conference on Developments in Language Theory, held at University of Western Ontario, London. You can find the programme here. Our DLT 2010 paper, authored by yours truly, Alberto Leporati and Claudio Zandron, is titled On a powerful class of non-universal P systems with active membranes. [...]
A relatively serious proof that P ≠ NP?
9 August 2010Note: I’ve stopped updating this post, now that I’ve collected quite a lot of comments. For the latest news, I suggest checking my tweets and, in particular, the Polymath wiki page (edited by more people than just yours truly). Maybe I’ll have another post in the next few days, if something shocking happens. The news [...]
How I learned to stop worrying about Turing completeness and love primitive recursion
11 July 2010The primitive recursive functions are a class of computable arithmetic functions with a reasonably natural definition. They do not exhaust all computable functions (e.g., Ackermann’s function grows faster than any PR function). Here is a list of reasons to like them anyway. The PR functions are exactly the functions that can be computed by using [...]
Solving PP-complete problems using P systems
5 July 2010Today we submitted the final version of our paper P systems with elementary active membranes: Beyond NP and coNP, which has been accepted for the Eleventh International Conference on Membrane Computing, taking place on 24–27 August. The venue of CMC11 is Friedrich-Schiller-Universität in Jena, Germany. This university has some slightly notable alumni, such as Rudolf [...]
