user avatar
user avatar
user avatar
chazisop
  • Member for 11 years, 10 months
  • Last seen more than a week ago
32 votes
Accepted

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

31 votes

Common false beliefs in theoretical computer science

17 votes
Accepted

Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

13 votes

Best known deterministic time complexity lower bound for a natural problem in NP

12 votes

Problems that are decidable but cannot be verified in polynomial time

12 votes

Are research papers hard to read?

11 votes
Accepted

Resources to learn about the P vs. NP problem

11 votes

if I were to define a new complexity class how should I start?

10 votes

The unreasonable power of non-uniformity

8 votes

Complex analysis in theoretical computer science

8 votes

How do models of hypercomputation overcome the Halting Problem?

7 votes
Accepted

What relation is between constraint satisfaction problems and constraint programming?

5 votes

Why is it important to prove that a problem is NP-complete?

5 votes
Accepted

Justification of log f in DTIME hierarchy theorem

5 votes

Uncertainties in GCT program

4 votes
Accepted

Popular Journals for Theoretical CS

4 votes

Funding opportunities for non-european people going to Europe for a PhD in TCS

4 votes

Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

4 votes

What happens if we improve the time hierarchy theorems?

4 votes

What do we know about provably correct programs?

4 votes

Is there an alternative proof of the TM Halting Problem other than the "standard" one?

4 votes

Intractability of NP-complete problems as a principle of physics?

3 votes
Accepted

Is there a name for "physical things out of which one can build a Turing machine"?

3 votes

Is there an additive time hierarchy theorem?

3 votes
Accepted

Can an oracle allowing errors be non-relativizing?

3 votes
Accepted

List of complexity classes closed under complement

2 votes

Efficiently converting an ascending sequence to a sorted sequence one at a time

2 votes

Method of Algorithm Study

2 votes

Which algorithms are used most often in practice?

2 votes

Mathematical background needed for pursuing a PhD in TCS