user avatar
user avatar
user avatar
Ben
  • Member for 10 years, 5 months
  • Last seen this week
3 votes

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

3 votes

Automatic Downcasting by Inferring the Type

8 votes

Proving the regularity of a certain language

5 votes
Accepted

What is the amount of programs for which we can solve the halting problem?

2 votes

Undecidability of the following language

4 votes
Accepted

NP-complete reductions

2 votes

Input to make worst case on big O not possible?

1 vote

Difference between reductions in algebraic problems versus reductions in computational intractability

3 votes

Length of the certificate in complexity classes

7 votes

What approaches are most useful when proving uncomputability of a given function?

18 votes
Accepted

Infinite alphabet Turing Machine

7 votes

Can all languages have semantic and logical errors?

3 votes
Accepted

A concrete example about string w and string x used in the proof of Rice's Theorem

4 votes

Length of mid part of the string in Pumping Lemma

9 votes

Can constraint satisfaction problems be solved with Prolog?

12 votes

How do you check if two algorithms return the same result for any input?

2 votes

Is there an undecidable finite language of finite words?

11 votes
Accepted

Why isn't this undecidable problem in NP?

4 votes

What is meant by interrupts in the context of operating systems?

10 votes

Can a dynamic language like Ruby/Python reach C/C++ like performance?

3 votes
Accepted

Non-trivial tractable properties of triples

8 votes

Is interaction more powerful than algorithms?

3 votes

What is the significance of context-sensitive (Type 1) languages?