## Top new questions this week:

### Are there any natural $\Pi_2^P$-complete problems?

I know that the quantified Boolean formula problem for a formula $$\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi$$ where $\phi$ contains no quantifiers and only the ...

complexity-classes

### What type of algorithms are faster with a quantum computer?

I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that ...

algorithms quantum-computing

### Efficient algorithm for this optimization problem? Dynamic programming?

I've created a diagram that depicts what I'm trying to accomplish. Full-size Image In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to ...

algorithms dynamic-programming

### Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...

complexity-theory np-complete np polynomials

### PAC learning model definition

The probably approximately correct (PAC) learning model is defined as: A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such ...

machine-learning

### How do garbage collectors avoid stack overflow?

So I was thinking about how garbage collectors work and I thought of an interesting issue. Presumably garbage collectors have to traverse all structures in the same way. They can't know weather they ...

programming-languages memory-management garbage-collection

### Relativization results in class separation

We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal. Is there natural complexity classes that has been shown to be ...

complexity-theory

## Greatest hits from previous weeks:

### Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 -- Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...

algorithms algorithm-analysis heaps priority-queues

### Definition of the state of an object in OOP

I need a concise definition of the "state of an object" in object-oriented programming (for a paper). For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find ...

terminology reference-request programming-languages object-oriented

### How do IR researchers evaluate the ranks of documents?

I am developing a new IR system in a specialized context. I understand that a traditional IR system (like a search engine) should rank documents in terms of their relevance for a query. The most ...

natural-lang-processing information-retrieval

### Oracle for an inverse function

A. Let $F$ be a monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite ...

time-complexity
 asked by Erel Segal-Halevi 1 vote

### Complexity of clustering lattice points


algorithms reference-request computational-geometry