# Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

1,534 questions
Filter by
Sorted by
Tagged with
46 votes
4 answers
4k views

### Generalized Ladner's Theorem

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
• 18.7k
5 votes
2 answers
934 views

### Handbook of Logic in Computer Science - is it worth it?

I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to ...
15 votes
1 answer
366 views

### Triangulating a Planar Polygon

Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
• 5,973
18 votes
1 answer
1k views

### Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
• 1,925
19 votes
3 answers
973 views

### What algorithms are known for computing Craig interpolants?

Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the ...
• 4,746
38 votes
2 answers
2k views

4 votes
3 answers
548 views

### What applications of Cantor space are there?

Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic? John Tucker's page Computation on Topological ...
• 4,276
14 votes
2 answers
1k views

### Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions). In the same paper, Immerman state that the ...
• 1,521
12 votes
3 answers
642 views

• 1,459
20 votes
2 answers
1k views

### Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
• 5,963
24 votes
3 answers
1k views

### Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
• 31.7k
21 votes
1 answer
324 views

### A comparison of extractors in terms of tradeoffs between time, randomness and space ?

Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
• 31.7k
17 votes
3 answers
758 views

### Are there any known implementations for quantum computing constructs?

Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...
• 2,213