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.4k4 gold badges57 silver badges144 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 ...
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
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 ...
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
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
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
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
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
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 $...
9
You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; such algorithms exist for many graph problems). If you could get $|V(G)| = o(m^2)$ in the reduction you mention, this would imply that the Exponential Time ...
9
Let me clarify the question a bit first:
Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input distribution. The reductions in FGKP06 are for the uniform distribution and to the best of my knowledge there is no similar result for general distributions.
But ...
9
It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are ...
Only top voted, non community-wiki answers of a minimum length are eligible