400 views

### Algorithm to determine if given algorithm runs in polynomial time [duplicate]

In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding ...
55 views

### Algorithmically compute a reasonable bound on the runtime of an algorithm [duplicate]

Possible Duplicate: Are runtime bounds in P decidable? (answer: no) Originally asked on SO: https://stackoverflow.com/questions/13371025 I have seen many questions asking if this computation is ...
9k views

### A simple decision problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
3k views

### Using lambda calculus to derive time complexity?

Are there any benefits to calculating the time complexity of an algorithm using lambda calculus? Or is there another system designed for this purpose? Any references would be appreciated.
2k views

### Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)

Five linked questions are asked, and a single integrated answer is hoped-for: Q1: Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime ...
1k views

### To what extent can an algorithm predict the time complexity an arbitrary input program?

The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs. I can, however, certainly write a program that can ...
1k views

### Are there decidable problems for which for no algorithm we can give time bounds?

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance? I arrived at this question because I was ...
1k views

### Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

Update #6: Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No. Emanuele's answer illuminates (for me) Luca Trevisan's ...
1k views

### Does P contain incomprehensible languages? (TCS community wiki)

Answer: not known Many thanks to all who helped refine this question and the definitions associated to it. The definitions of this wiki provided the starting point for the more recent TCS wiki "...
436 views

### Can one automate algorithmic analysis?

Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a ...