Linked Questions

-2 votes
1 answer

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 ...
Elliot Gorokhovsky's user avatar
0 votes
0 answers

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: I have seen many questions asking if this computation is ...
singpolyma's user avatar
104 votes
15 answers

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 ...
Lev Reyzin's user avatar
  • 12k
43 votes
7 answers

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.
Shane's user avatar
  • 2,233
21 votes
4 answers

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 ...
23 votes
2 answers

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 ...
Hooked's user avatar
  • 365
12 votes
5 answers

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 ...
Hermann's user avatar
  • 129
6 votes
2 answers

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 ...
John Sidles's user avatar
  • 1,536
11 votes
3 answers

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 "...
9 votes
3 answers

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 ...
manoj's user avatar
  • 341
8 votes
1 answer

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

The question: Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM? I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} ...
Neal Young's user avatar
  • 10.8k
3 votes
2 answers

Runtime of a TM enumerator

Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)? For simplicity let's say the string ...
fy_iceworld's user avatar
1 vote
1 answer

Clarification: Are runtime bounds in P decidable?

In Emanuele Viola's much upvoted answer to the question, "Are runtime bounds in P decidable?" he uses the following proof: The problem is undecidable. Specifically, you can reduce the ...
Kittsil's user avatar
  • 113