27
votes
Accepted
Does Karp reducibility yield a total order?
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, ...
- 36k
22
votes
Accepted
Curious about computer-assisted NP-completeness proofs
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-...
- 20.7k
16
votes
Accepted
Is ALogTime != PH hard to prove (and unknown)?
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 ...
- 26.6k
15
votes
Curious about computer-assisted NP-completeness proofs
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 ...
- 1,968
14
votes
Accepted
Are there subexponential algorithms for PLANAR SAT known?
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 ...
- 9,576
14
votes
Curious about computer-assisted NP-completeness proofs
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 ...
- 22.4k
14
votes
Accepted
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
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 ...
- 9,024
13
votes
How to prove that USTCONN requires logarithmic space?
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$...
- 2,289
12
votes
Accepted
Limited number of variable occurrences in 1-in-3 SAT
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 ...
- 22.4k
12
votes
Accepted
Is intersection of $k \ge 3$ graphic matroids in P?
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 ...
- 50.5k
11
votes
Curious about computer-assisted NP-completeness proofs
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/...
- 111
11
votes
Accepted
Proof for Kolmogorov complexity is uncomputable using reductions
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, ...
- 22.4k
11
votes
On reducing the hardness of CNF-SAT to k-Clique
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 ...
- 26.6k
11
votes
Accepted
On sparse complete sets and P vs L
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 ...
- 1,743
11
votes
Accepted
Existing implementation of Scott's reduction?
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/...
- 1,110
10
votes
Accepted
Improving Cook's generic reduction for Clique to SAT?
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 ...
- 10.8k
9
votes
Accepted
Reducing sorting to max-flow
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 ...
- 50.5k
9
votes
Accepted
The relationship between completeness and strength of reductions
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^...
9
votes
Reduction SAT to a problem on a planar graph with as few vertices as possible
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; ...
- 4,604
9
votes
Accepted
Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?
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 ...
- 881
9
votes
Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT
The conjunction of the first two clauses, $(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ is equisatisfiable to the original clause, as can be easily checked (any ...
- 2,480
9
votes
Accepted
Validity of exponentiation in a polynomial time reduction
The proof as presented in the paper is not conclusive.
However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of ...
- 5,742
9
votes
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. ...
- 50.5k
8
votes
Accepted
#P- vs PP-Completeness
Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for ...
- 250
8
votes
Accepted
Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis
First of all, Mahaney's Theorem says that merely assuming $\mathsf{P} \neq \mathsf{NP}$, there are no sparse $\mathsf{NP}$-complete sets. (Historically, Mahaney was motivated to study this precisely ...
- 36k
8
votes
Accepted
Reductions between languages of different densities?
Let $A$ be any language not in $L$, such that $A$ has density $2^{o(n)}$, and define
$$B = \{s \circ 1 | s \in \{0,1\}^*\} \cup \{s \circ 0 | s \in A\}.$$
Here $\circ$ is concatenation. The language $...
- 3,236
8
votes
Is intersection of $k \ge 3$ graphic matroids in P?
How about using the fact that 3-d matching is NP complete to show NP Completeness of this problem. We can easily write 3-d matching as intersection of 3 partition matroids, and a partition matroid is ...
- 81
8
votes
Accepted
Calculus of Constructions: compress expression to its smallest form
There's a bit of freedom in what we considre "the same value". Let me show that there is no such algorithm if "the same value" means "observationally equivalent". I will use a fragment of the Calculus ...
- 26.9k
8
votes
Accepted
Is solving the following system of boolean equations NP-hard?
[Now that the question's been clarified I'll post my previous comment as an answer.]
It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone,...
- 36k
Only top scored, non community-wiki answers of a minimum length are eligible