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, ...
- 35.6k
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.5k
16
votes
Should reductions make us more or less optimistic for the tractability of a problem?
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 ...
- 3,211
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.2k
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
Should reductions make us more or less optimistic for the tractability of a problem?
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 ...
- 11.3k
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.3k
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,556
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,267
13
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 ...
- 8,133
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.3k
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.2k
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.3k
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.2k
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,733
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.3k
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,584
9
votes
Should reductions make us more or less optimistic for the tractability of a problem?
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 ...
- 21.3k
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
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.2k
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,470
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,712
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.2k
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 ...
- 35.6k
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,161
Only top scored, non community-wiki answers of a minimum length are eligible