# Tag Info

### Easy problems with hard counting versions

A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph. The decision version is easy (... and the Seven Bridges of Königsberg problem has ...

### Easy problems with hard counting versions

One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at ...
• 6,985
Accepted

### Easy problems with hard counting versions

Here's a truly excellent example (I may be biased). Given a partially ordered set: a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets ...
• 342

### Easy problems with hard counting versions

Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to ...
• 2,174

### Lower bound on the element distinctness problem

This was also done, independently, by Lubiw and Racz in 1991. See http://www.sciencedirect.com/science/article/pii/089054019190034Y .
• 6,985
Accepted

### Lower bound on the element distinctness problem

Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals: A. C.-C. Yao, Lower Bounds for Algebraic Computation Trees of Functions ...
• 37.8k

### Easy problems with hard counting versions

From [Kayal, CCC 2009]: Explicitly evaluating annihilating polynomials at some point From the abstract: This is the only natural computational problem where determining the existence of an object (...
• 6,011
Accepted

### Complexity of constructing minimum depth decision trees

I think I can see a fairly easy reduction from 3DM. Let $B=\{0^J\}$, i.e., it is a singleton set with the only zero element. The points of $A$ correspond to the points of the 3DM that are to be ...
• 14.1k

### Lower bound for sorting without using a decision tree model

If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of ...
• 37.8k
Accepted

### Finding the maximum no. of people who get along in a group

Convert your array to a zero-one array where $a_{ij}=1$ if persons $i,j$ get along, else it is zero. Let this be the adjacency matrix of an undirected graph $G$ where the vertices are the persons in ...
• 2,070

### Lower bound for sorting without using a decision tree model

The paper "Sorting and Element Distinctness on One-Way Turing Machines" by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.
• 4,630
Accepted

### Binary Trees for Nearest Neighbor Search

This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed ...
• 9,626
1 vote
Accepted

### If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl

Observe that if a $k$-CNF $\Phi$ is equivalent to an $l$-DNF $\Psi$, then every term of $\Psi$ implies every clause of $\Phi$, i.e., they share a literal. If the Boolean function is not constant, pick ...
• 18.2k

Only top scored, non community-wiki answers of a minimum length are eligible