28
First, let me comment on the specific case of the Valiant-Vazirani reduction; this will, I hope, help clarify the general situation.
The Valiant-Vazirani reduction can be viewed/defined in several ways. This reduction is "trying" to map a satisfiable Boolean formula $F$ to a uniquely-satisfiable $F'$, and an unsatisfiable $F$ to an unsatisfiable $F'$. All ...
27
Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq_p$, even if we only consider those degrees in between two given fixed languages (K. Ambos-Spies, Sublattices of the polynomial time degrees, Inform. & Control 65(1):63-84, 1985).
22
Just for reference, I stumbled across this really interesting paper today, which gives evidence that a deterministic reduction is unlikely:
Dell, H., Kabanets, V., Watanabe, O., & van Melkebeek, D. (2012). Is the Valiant-Vazirani Isolation Lemma Improvable? ECCC TR11-151
They argue that this is not possible unless NP is contained in P/poly.
22
As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant.
Erickson and Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-complete. They gave a polynomial time reduction from planar 3-SAT to tatami domino covering. A SAT-solver (Minisat) was used to automate gadgets discovery in ...
answered Jan 31 '15 at 16:19
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
20
Integer Programming.
Showing that if there is an integer solution then there is a polynomial size integer solution is quite involved. See
Christos Papadimitriou, "On the Complexity of Integer Programming", JACM, 1981.
19
A "gadget" is a small specialized device for some particular task. In NP-hardness proofs, when doing a reduction from problem A to problem B, the colloquial term "gadget" refers to small (partial) instances of problem B that are used to "simulate" certain objects in problem A. For example, when reducing 3SAT to 3-COLORING, clause gadgets are small graphs ...
18
This type of problem has been the subject of quite a bit of study. You can find references by googling random self-reducibility, and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.
17
Lower bounds for algebraic circuits
In the setting of algebraic circuits, where a lower bound on circuit size is analogous to a lower bound on time, many results are known, but there are only a few core techniques in the more modern results. I know you asked for time lower bounds, but I think in many cases the hope is that the algebraic lower bounds will ...
17
While the problem "is the crossing number of a graph at most $k$?" is trivially in NP,
the NP-membership of the related problems for the rectilinear crossing number and
the pair crossing number are highly not obvious;
cf. Bienstock, Some probably hard crossing number problems, Discrete Comput. Geometry 6 (1991) 443-459, and
Schaefer et al., Recognizing ...
16
What is missing from the analogy is some notion of the relative distances involved. Let's replace Alaska in our analogy with the moon:
You're an explorer, searching for a bridge between the North American and Asian continents. For many months you have tried and failed to find a land bridge from the mainland United States area to Asia. Then you discover ...
16
Not sure why Fortnow says there's "no meaningful model where $L$ and $NP$ collapse"... it seems to me that QBF should make them collapse, under the usual Ruzzo-Simon-Tompa oracle model (and the link you included agrees). Note this oracle model also has its quirks: we have $L = NL$ if and only if $L^A = NL^A$ for every oracle $A$, so any oracle witnessing a ...
15
Given a graph $G$ and a number $k$, such that you want to know whether $G$ contains a $k$-clique, let n be the number of vertices in $G$. We construct another graph $H$, such that $H$ is $n$-colorable if and only if $G$ has a $k$-clique, as follows:
(1) For each vertex $v$ in $G$, make an $n$-clique of vertices $(v,i)$ in $H$, where $i$ ranges from $1$ to $...
15
Let me please post another solution similar to Ratchel's but somewhat different. This is directly taken from chapter 9 of the 2nd Edition of "The Algorithm Design Manual" by Steven Skiena
If the clause has only one literal C={z1}, then create two new variables v1 and v2 and four new 3-literal clauses: {v1, v2, z1}, {!v1, v2, z1}, {v1, !v2, z1} and {!v1, !v2,...
15
The Wikipedia entry that Peter linked to mentions a few important examples of problems that have worst-case to average case reductions, like the permanent. Shortest vector problem (as well as related lattice problems) is another important example, see Ajtai's paper and what came after it (works by Regev, Micciancio, Peikert,...).
One of the only general ...
15
Yes, there are such sets, take any $\mathsf{NP}$-intermediate set (any set that is provably $\mathsf{NP}$-intermediate assuming $\mathsf{P}\neq\mathsf{NP}$), e.g. construct one from SAT using Ladner's theorem.
Note that your $L$ needs to considered an $\mathsf{NP}$-intermediate problem, since it is in $\mathsf{NP}$ but not complete for it. Note also that ...
15
In this paper, I showed that if for some $k\geq 3$ there is a graph with maximum degree $k$ and chromatic edge strength strictly greater than $k$, then it is $\Theta_2^p$-complete to decide if chromatic edge strength is at most $k$. Such graphs were known for $k>3$ and I did a computer search to find a suitable $12$-vertex graph for $k=3$.
The complexity ...
14
I assume that you are asking about the relation between a complexity class having a complete problem under a certain notion of reducibility and the same complexity class being closed under the same notion of reducibility. It is a common misunderstanding that these two notions are related. They are not!
For example, SAT is an NP-complete problem under ...
14
I think this is a very good question. To answer it we need to realise that:
not all reductions are alike,
to feel optimistic, we need to learn something genuinely helpful.
Typically, whenever we discover a nontrivial reduction $A \to B$, it falls in one of the following categories:
We learned something helpful about problem A (and nothing about problem B)....
14
Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O(\sqrt{n})}$, where $n$ is the number of vertices in the graph. The idea being that you try all possible assignments for the variable vertices on the separator, and all variables mentioned in clauses in the separator (assuming each clause has a ...
13
A formal definition of Gadgets for NP optimization reductions appears here:
L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson. Gadgets, Approximation, and Linear Programming. SIAM J. on Computing, 29(6):2074-2097, 2000
13
In the oracle world, it is easy to give examples where randomness gives us much more power. Consider, for example, the problem of finding a zero of a balanced Boolean function. A randomized algorithm accomplishes that using $O(1)$ queries with constant success probability, while any deterministic algorithm requires at least $n/2$ queries.
Here is another ...
13
My favourite example is a classic 1977 result of Ashok Chandra and Philip Merlin. They showed that the query containment problem was decidable for conjunctive queries. The conjunctive query containment problem turns out to be equivalent to deciding whether there is a homomorphism between the two input queries. This rephrases a semantics problem, involving ...
13
From the comment above:
I used the Choco Java library for Constraint programming to check the correct behaviour of the gadgets used to prove the NP-completeness of the following puzzles:
Binary Puzzle, Tents, Rolling cube puzzle without free cells, Net.
I didn't have the time to publish them, yet, but the draft papers are available on my blog.
The ...
13
The paper Counting Quantifiers, Successor Relations and Logarithmic Space, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$ in an outdegree one graph $G$, that is promised to be a path) is $\mathsf{L}$-hard under quantifier free projections.
The problem $\mathbf{ORD}$ can be seen ...
12
You may be interested in the $k$-creative sets, invented in [1] as a conjectured counterexample to the Berman-Hartmanis conjecture that all NP-complete sets are isomorphic to SAT.
"Isomorphic" is different from a Turing reduction (significantly weaker in fact), but these sets were shown to be NP-hard directly and as far as I know there's no known reduction ...
12
One reason why it might seem strange to you, that we seem to think there is more apparent (or conjectured) power in the randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$ than the comparable one from $\mathsf{BPP}$ to $\mathsf P$, is because you may be tempted to think of randomness as something which is either powerful (or not powerful) independently ...
12
Kaveh has gently suggested in his answer that I should say something. I don't have much else to contribute to this nicely comprehensive list of answers. I can add a few generic words about how "structural complexity" lower bounds have evolved over the past ten years or so. (I use the name "structural complexity" simply to distinguish from algebraic, ...
12
Up to my knowledge the current "limits" have been settled in:
Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw:
XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics 167: 1-14 (2014)
See also Schmidt's Thesis: Computational Complexity of SAT, XSAT and NAE-SAT for linear and mixed Horn CNF formulas
Theorem 29. XSAT ...
11
For undirected graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that
$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N-N^c$.
Karger Motwani Ramkumar 1997
For directed graphs, you ...
Only top voted, non community-wiki answers of a minimum length are eligible
