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
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
20.1k4 gold badges55 silver badges139 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.
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 one ...
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
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 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
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 ...
13
You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious.
For the record, here's a sketch of a reduction that is parsimonious.
It is obtained by composing parsimonious reductions from 3-SAT to 1-in-3-SAT, from 1-in-3-SAT to a problem we call 1+3DM, and from 1+3DM to 3DM. We sketch each of these next.
Lemma 1. There is a ...
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
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
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 ...
12
I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding Hamiltonian cycles through a specified edge in a cubic bipartite graph — replace the specified edge by two leaves.)
To reduce from Hamiltonian paths to graphic ...
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 ...
11
I did this very thing — computer-assisted NP-completeness proof — in my bachelor thesis!
The bad part - it's in Russian and wasn't translated to English.
http://is.ifmo.ru/diploma-theses/_dvorkin_bachelor.pdf
I worked with logical gates in 2D problems. The plan is:
Manually design what a "wire" looks like in your problem.
Use very smart and optimized ...
11
You can find two different proofs in:
Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)
In Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications it is presented as an exercise (with a hint on how to solve it that is credited to P. ...
11
I don't know the answer to your specific question (it seems related to the question of whether W1=W[2]).
But the algorithm you give in your question is subsumed by several other results. Using your definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the paper by Wahlstrom (link goes to a google scholar page of papers that cite it)....
11
Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 and proven by Cai and Sivakumar in 1995. See this paper.
Hartmanis also conjectured that if there is a sparse $\mathbf{NL}$-complete set under log-space many-...
10
The techniques depend on the model and the type of resource
we want to get a lower bound on.
Note that to prove a lower bound on the complexity of a problem
we have to first fix a mathematical model of computation:
a lower bound for a problem states is that
no algorithm using some amount of resources can solve the problem, i.e.
we are quantifying universally ...
10
The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.
Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.
The type of reductions you'd need ...
Only top voted, non community-wiki answers of a minimum length are eligible
