17 votes

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 ...
Marzio De Biasi's user avatar
17 votes

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 ...
Jeffrey Shallit's user avatar
9 votes
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 ...
Gara Pruesse's user avatar
6 votes

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 .
Jeffrey Shallit's user avatar
6 votes
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 ...
Joshua Grochow's user avatar
6 votes

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 ...
holf's user avatar
  • 2,174
5 votes
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 ...
domotorp's user avatar
  • 13.8k
5 votes

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 (...
Daniel Apon's user avatar
  • 6,001
3 votes
Accepted

Minmax vs Maxmin

First of all, there is a lot of information in this related question: Max Min of function less than Min max of function. That said, the source of your problem is a confusion about which choices are ...
Klaus Draeger's user avatar
3 votes

decision tree complexity and query complexity

Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.
Kumar's user avatar
  • 2,014
3 votes

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 ...
Joshua Grochow's user avatar
2 votes

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.
Jan Johannsen's user avatar
2 votes
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 ...
Sariel Har-Peled's user avatar
2 votes
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 ...
kodlu's user avatar
  • 2,070
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 ...
Emil Jeřábek's user avatar
1 vote
Accepted

Randomized and deterministic query complexity of symmetric functions

Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. ...
permanganate's user avatar

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