28

These problems are polynomially equivalent. Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are. Attach a clique of size $n+1$ to an arbitrary vertex of each graph. Test whether the resulting graphs are isomorphic or not. If they are, then we can conclude that there's an isomorphism ...


22

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: (¬x1 ∨ ¬x3 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4) ∧ (x1 ∨ ¬x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧ (¬x1 ∨ x2 ∨ ¬x3) Or, in table form with each row being a 3-clause, x meaning "this variable false", o ...


17

More specific to Babai's algorithm: yes, the algorithm not only finds an isomorphism, it finds generators of the automorphism group (and therefore effectively finds all isomorphisms) as part of the algorithm, that is, without the reduction of domotorp's answer. In terms of deciding existence of an isomorphism (resp., unknotting) vs actually finding one, the ...


16

Given a satisfiable 2-CNF $\phi$, you can compute a particular satisfying assignment $e$ by an NL-function (that is, there is an NL-predicate $P(\phi,i)$ that tells you whether $e(x_i)$ is true). One way to do that is described below. I will freely use the fact that NL is closed under $\mathrm{AC}^0$-reductions, hence NL-functions are closed under ...


14

If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$. (This follows from the definition, in terms of number of accepting paths of an NP verifier.) This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case ...


14

Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries". It seems that the existence of a polynomial time algorithm is still open. Schmulevich et al. prove that "Almost all ...


10

This problem has been shown to be NP-complete in the following paper: S. Fortune, J. Hopcroft, J. Wyllie: "The directed subgraph homeomorphism problem" Theoretical Computer Science 10 (1980), pp. 111-121


8

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.


7

In their paper Every Poset Has a Central Element, Linial and Saks show (Theorem 1) that the number of queries required to solve the ideal identification problem in a poset $X$ is at most $K_0 \log_2 i(X)$, where $K_0 = 1/(2 - \log_2(1 + \log_2 5))$ and $i(X)$ is the number of ideals of $X$. What they call an "ideal" is actually a lower set and there is an ...


7

This is not a complete answer, but it's too long to be a comment. I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight. Consider the following poset. The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable. (The Hasse diagram is a $4$-cycle). ...


7

Here is a writeup following up on Tsuyoshi's pointer to use DP. Given $p(x)$, we can write any (decent, deterministic) algorithm as a binary decision tree with nodes weighted by $p(x)$. The root of the tree is the first node the algorithm selects to test; the left child of each $x$ is the next node to test if $f(x)$ is zero and the right node is the next to ...


7

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions. If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then ...


7

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (in the sense Goldreich uses it), but rather about Cook reductions being inherent to this notion, in the sense that they cannot be replaced by Karp reductions. ...


5

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices). The norm in the second question is ...


5

For the Boolean n-cube $(\{0, 1\}^n, \leq)$ (or, equivalently, for the poset $(2^S, \subseteq)$ of all subsets of an n-element set), the answer is given by Korobkov and Hansel's theorems (from 1963 and 1966, respectively). Hansel's theorem [1] states that an unknown monotone Boolean function (i.e., an unknown monotone predicate on this poset) can be learned ...


5

For the problem of finding all the maximal elements of $P$ over the lattice of subsets $2^{[n]}$, this amounts to exact inference of a positive boolean function of $n$ boolean variables. If you only care about the number of evaluations of $P$ (not the computational complexity), you can find a survey in Data Mining and Knowledge Discovery via Logic-Based ...


5

For total UP the answer is yes, because the question "Is the i'th bit of the solution 1?" is in $NP \cap co-NP$.


4

I assume that P, NP, and coNP in the question are classes of languages, not classes of promise problems. I use the same convention in this answer. (Just in case, if you are talking about classes of promise problems, then the answer is affirmative because P = NP∩coNP as classes of promise problems is equivalent to P = NP.) Then the answer is negative in a ...


4

Please see the comments below by Emil Jeřábek, so I am not that sure anymore that the problem is harder. No, it is not known but it is harder than PPP :) Here I focus on the $M=2N+1$ case, so $t=3$, that is, we want $3$ inputs that map to the same output. In Papadimitriou's seminal paper "On the Complexity of the Parity Argument" he defined PPA-3 similarly ...


4

The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender.


4

This is an interesting question, and I can only give a partial answer. It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case MANY ENDS OF THE LINE (MEOL): Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ ...


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

In addition to the accepted answer, here is a recent paper (December '14) on the complexity of counting certain restricted models of Linear-time Temporal Logic. Higher, and more esoteric, complexity classes are present in the results shown: variants of the problem are $\#PSPACE$-complete, $\#EXPTIME$-complete, etc. The Complexity of Counting Models of ...


3

I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful difference between “BPP-like”, “RP-like”, or “ZPP-like” randomized polynomial-time algorithms, as we can check the correctness of any purported solution in ...


3

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example. Take a simplex in $\mathbb{R}^{k-1}$, and put $k$ points at each of the $k$ vertices, for a total of $k^2$ points. Note that between each pair of vertices of the simplex the distance is 1. The optimal ...


2

This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ of multiplicative order exceeding $D$, then we cannot have $f(\omega^i, \dots, \omega^i)=0$ for $i=0,1,\dots,2T-1$ by Prony's method / BCH decoding / Ben-Or ...


2

The linked PDF, "Handout 2 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems": Decision problems Search problems Optimization problems Counting problems As the document notes at the beginning, it focuses on the first two: decision and search problems. In this course we will deal with four types of ...


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