# All Questions

11,311 questions
Filter by
Sorted by
Tagged with
1k views

### Complexity of testing for a value versus computing a function

In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example: Evaluating the ...
2k views

1k views

### $BQP$ vs $QMA$?

The central problem of complexity theory is arguably $P$ vs $NP$. However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a ...
2k views

### Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "...
1k views

### NP-Completeness of the decision problem for the generalized 15-puzzle

I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block). Now the ...
2k views

### Hardness jumps in computational complexity?

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path ...
3k views

### Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
11k views

### Alan Turing's Contributions to Computer Science

Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...
6k views

### Book on Probability

While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability. It seems that the authors of ...
2k views

### Approximation algorithms for problems in P

One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for ...
6k views

### NEXP-complete problems

There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
3k views

### Efficient and simple randomized algorithms where determinism is difficult

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
4k views

### Concepts in theoretical CS that would be approachable ages 8-14

Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.
7k views

In my academic career, I've read quite a few academic papers on various computer science topics. Many of which involve an implementation and some assessment of that implementation, yet I have found ...
3k views

### Reference for NP-hardness of 3-colouring?

I have a historical question. I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard. The tempting answer ...
1k views