22

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls. First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node....


17

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 no solution :-) The counting version is #P-hard: Graham R. Brightwell, Peter Winkler: Counting Eulerian Circuits is #P-Complete. ALENEX/ANALCO 2005: 259-262


17

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 https://dx.doi.org/10.1002%2Fcpa.3160390713), and if I remember correctly, there is now even a deterministic polynomial-time solution. But counting the number ...


16

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$. A similar result can be deived from a later algorithm of Meiser for point location in hyperplane arrangements. Of course the problem is NP-hard.


9

I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A \mapsto g(f(A))$ can be computed in polynomial time, so in particular, $|g(f(A))|$ is $\text{poly}(|A|)$. But if we take $B$ to be a minimal BDT equivalent to $...


8

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 have at least one linear extension b) How many does it have? #P-complete to determine this (Brightwell and Winkler, Counting Linear Extensions, Order, 1991) c) ...


7

This question has been resolved! A few days ago Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs uploaded a preprint showing the existence of a total function $f$ which satisfies $R_0(f) = \tilde{\Omega}(R_2(f)^{2})$ and even $R_0(f) = \tilde{\Omega}(R_1(f)^{2})$, where $R_1(f)$ denotes 1-sided ...


7

As far as I know, this is still open. A very recent paper that mentions these quantities and some bounds is Aaronson et al: Weak parity (see http://arxiv.org/abs/1312.0036). You can also see chapter 14 of Jukna: Boolean funcions and the 1999 (still beats 1998!) survey by Buhrman and de Wolf. Another very recent paper about randomized decision tree complexity ...


6

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


6

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 with Finite Domains, SIAM J. Comput., 20(4), 655–668. Rather, Yao has to re-prove the Milnor-Thom-Oleinik-Petrovski bound on the number of connected components of ...


6

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 check if your formula is empty or not) but the counting problem is #P-hard. Even approximating the number of satisfying assignments of such formula is hard (see ...


5

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 (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard.'' Let $\mathbb{F}$ be a field and $\...


5

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 matched. If a triple is matchable, then there is a coordinate where these 3 points are 1, while all other points are 0. The equivalence is straightforward. I think ...


5

If you have an oracle for $f$, you can compute the optimal decision tree for $f$ in $O(3^nn)$ time and $O(3^n)$ space. Consider a function $g$ that takes as input a partition of the variables into three sets $T$, $F$, $S$ and outputs the size of the smallest decision tree for $f$ when the variables in $T$ are restricted to $1$ and the ones in $F$ are ...


5

I found a partial solution. The problem is in L. The negation of $A \leftrightarrow B$ is equivalent to $(\bar A \land B) \lor (A \land \bar{B})$ which is equivalent to $False$ iff both $(\bar A \land B)$ and $(A \land \bar{B})$ are. The read-once decision tree for $\bar{A}$ can be obtained from the read-once decision tree for $A$ by switching $True$ and $...


4

Here is an example of a trivial gap between decision-tree and algorithmic complexity. The randomized decision tree complexity of local sorting (orienting a vertex-weighted graph) is $O(n\log(\frac{m+n}{n}))$ whereas the size of the input is $\Theta(n+m)$. Any algorithm needs to read the input, so there's a separation whenever $m=\omega(n)$. See Goddard, ...


3

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 available to each player when it is their turn. Consider the left-hand side of your first example: writing this in matrix form, each player gets to choose ...


3

Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.


2

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 your formulation. What you are asking about is how to find the maximal cliques (maximal connected subgraphs) of $G.$ This is in general a very difficult ...


2

From a ITE formula $\phi$, you can compute polynomially a reduced assignment list to describe all valuations which makes it true. To do that, just look at your formula as a tree with nodes labeled by variables and leaves by $0$ and $1$. Left branches are the "then" part setting the variable to true and right branches are the "else" part setting it to false. ...


2

Any algorithm would need $\Omega(\log n)$ queries. To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$. Notice that in these notations we are looking to bound $f(\...


1

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$. However, $D(f) \geq s(f)$ and $R_{1/4}(f) \geq \frac{s(f)}{3}$... There are other interesting results concerning symmetric functions in this survey (see ...


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