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.3k4 gold badges56 silver badges143 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.
18
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 ...
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 ...
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
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
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
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 ...
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
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-...
11
You might check the FO2 solver by Tomer Kotek et. al (ICDT 2017): https://forsyte.at/alumni/kotek/fo2-solver/
as well as an FO2 solver by Tony Tan and his students (LICS 2021):
https://arxiv.org/abs/2104.10621
Answering the question, the authors implemented an improved version of Scott Normal Form, called therein "Skolemized Scott Normal Form". All ...
10
I think we can just start with some base language $L$, then take $L_0 = L$ and $L_{s+1} = L_s \cup \{0,1\}^{s+1}$.
That is, each $L_s$ is the union of $L$ with all strings of length up to $s$. Each $L_s$ is at least as hard as $L$ but is no harder (in an asymptotic sense), assuming we can count to $s$.
I also thought about the opposite "limit", so each $L_{...
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 ...
10
You can express $k$-clique as a SAT instance with $O(nk)$ variables and $O(nk^2)$ clauses. For fixed $k$, this is linear in $n$.
Let $x_{iv}=1$ if $v$ is the $i$th vertex in the clique (by lexicographically sorted order). In other words, $x_i$ is a "one-hot" encoding of the $i$th vertex in the clique (it is the characteristic vector for a set with one ...
9
Algebraic decision trees
This is not a recent technique, but one that is quite powerful for certain problems.
The algebraic decision tree model is a powerful generalization of comparison trees. In this model, an algorithm is modeled as a non-uniform family of decision trees, one for each input size $n$. Specifically, a $d$th-order algebraic decision tree ...
9
It is not true that we always look at reduction theorems as hardness statements.
For example, in algorithms we often reduce a problem to LP and SDP to solve them.
These are not interpreted as hardness results but algorithmic results.
However, although they are technically reductions
we often don't refer to these as such.
What we mean by a reduction is ...
9
If I understand correctly your questions are answered in
Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of Reductions
Gap Theorem - Any set that is NP-complete under $AC^0$ reductions is NP-complete under $NC^0$ reductions.
Stop Gap Theorem - There is a set that is NP-complete under $AC^0[\!\!\mod 2]$
reductions, but not under $...
Only top voted, non community-wiki answers of a minimum length are eligible
