Linked Questions
12 questions linked to/from Are runtime bounds in P decidable? (answer: no)
-2
votes
1
answer
987
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 ...
0
votes
0
answers
59
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 ...
- 127
103
votes
15
answers
11k
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 ...
- 11.9k
44
votes
7
answers
5k
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.
- 2,233
20
votes
4
answers
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 ...
23
votes
2
answers
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 ...
- 363
12
votes
5
answers
2k
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 ...
- 129
6
votes
2
answers
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 ...
- 1,506
11
votes
3
answers
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 "...
9
votes
3
answers
487
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 ...
- 341
3
votes
2
answers
274
views
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 ...
- 147
1
vote
1
answer
238
views
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 ...
- 113