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, ...
- 36.9k
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 ...
- 27.3k
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,595
13
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.9k
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 ...
- 27.3k
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,310
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 ...
- 11.7k
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,772
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,500
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.9k
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 ...
- 36.9k
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
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,256
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 ...
- 28.3k
8
votes
Accepted
Is Circuit Minimization $P$-hard under logspace reductions?
The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this ...
- 1,761
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,...
- 36.9k
7
votes
Accepted
Is iszero of the untyped lambda calculus sound and complete?
No, iszero does not have to test whether two functions are equal. It only has to detect a difference between them, i.e., extract enough information to tell whether ...
- 28.3k
7
votes
Polynomial-time reductions between undecidable languages
Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a ...
- 2,295
7
votes
Calculus of Constructions: compress expression to its smallest form
As Andrej has said, the problem is undecidable if you allow replacing one term by another, extensionally equal one. However, you might be interested in optimal sharing of expressions, in the following ...
- 13.7k
7
votes
Accepted
Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?
I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (...
- 18.1k
7
votes
Reductions in Descriptive Complexity
Standard notions of reduction used in Descriptive Complexity are first-order reduction and the weaker first-order projection. Definitions of both these notions are found in Immerman's book on ...
- 4,631
7
votes
Accepted
Complexity of reachability in directed rooted forests
The problem is L-complete.
It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that ...
- 16.9k
6
votes
Limited number of variable occurrences in 1-in-3 SAT
(I understand this must be a late answer; i am writing for future readers)
There is an evern stronger result in the literature.
Cubic Planar Positive 1-in-3 Satisfiability is proved NP-complete in ...
- 1,723
6
votes
Accepted
$\mathsf{TC^0}$-completeness and reductions
For question #1: If there is a complete problem for uniform TC$^0$ under uniform AC$^0$ m-reductions, then the counting hierarchy collapses. I don't know if this qualifies as "bad".
For ...
- 1,761
6
votes
Calculus of Constructions: compress expression to its smallest form
Let me insist on the viewpoint touched upon by cody's answer.
As far a see it, the question of finding a smallest $\lambda$-term equivalent to another $\lambda$-term is not really interesting, even ...
- 5,273
6
votes
Accepted
Reducing 3-XOR-SAT to HORN-SAT
The question is not very clear, as equisatisfiability of individual clauses does not imply equisatisfiability of the whole formulas.
However, if you mean a construction where each XOR clause is ...
- 16.9k
6
votes
Accepted
Proving not NP-complete by non-existence of gadget
First, I agree w/ Ludwik & other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time ...
- 36.9k
5
votes
Accepted
Complexity of permanent modulo prime
First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied ...
- 16.9k
Only top scored, non community-wiki answers of a minimum length are eligible